EE6902 Computer Communication Networks Qn. Paper

Subject: EE6902 Computer Communication Networks
Department: ECE Dept, NUS
Semester I, AY 2009-10 Question Paper

I wanted to do this from last semester onwards. There are some modules for which the previous question papers are not released by the department. I wanted to write down the questions and publish them. Maybe it will help someone in the coming semesters. Since I had back to back exams last semester, I was not able to do it. This semester, I have taken the module called computer communication networks which comprises mainly the fundamentals and concepts. The previous year question papers were not released and I and my friends wondered how to prepare for the exams or how the pattern of the questions may be. That’s when I decided this year I am going to write down and publish the questions as I remember them. I and my friend made small notes of the questions after the exam itself and now I made it to a better form.

If you are reading this for your exams, all the best and perform well. If you have attended this exam and know the missing questions or if there is anything to add to this blog, please do so by leaving a comment. If you find this ‘venture’ helpful, do leave a comment. After all, it feels good to know that I have helped someone. Special thanks to my ‘friend’, who helped me a lot for my exams, without whom I would not have made this blog possible or even study well for the exam.





Some Notes:
1. There is no guarantee for any of these questions to be exactly the same as seen in the question paper. I simply wrote down what I remember after the exams.
2. Even though I answered most of the questions, I am not sure about the answers and also I am too lazy to write down the answers. As our professor says, give it a try.
3. I am publishing this the next day of my exams and so I don’t know the results, yet.
4. In the end of the questions, the symbol © doesn’t mean copyright. All copyrights are with the professor or the university (or with whomever it is). It just means ‘courtesy’. ;)

Google: The real Skynet?

I wouldn’t be surprised if one day I hear Google has taken over the world or is going to be the ‘Skynet’ or the ‘Supreme Chancellor Palpatine’ of earth. I have heard stories about identity thefts or conspiracy theories like the CIA tapping personal information like bank accounts, phone records and not to mention the number of movies on this theme. Till recently I believed this is possible only for a high profile security agency or for an expert hacker. Only till I saw Google dashboard.
I read about Google Dashboard in a technical article two days back. It says “I already knew that I use a ton of Google services and they know a lot about me, so seeing it all in one place was more entertaining than scary”. I too didn’t expect it to be this scary. When visited the page, I felt like discovering me all over again and found out many thing which I never noticed doing before. Dashboard contain all the information about my Google account, Gmail account, Blogger account, calendar, contacts, docs, finance, social networking, latitude, search/web history, wave and the list goes on and on. Any person who can log in to my Google dashboard can easily get to know me, even more than I know about myself, like my account details , my schedule, my contacts, the documents I was working on, my financial portfolio, my friends, my location and even I do daily in the internet.

Video about Google Dashboard

I also knew that Google ‘knew’ many things about me. But seeing all of it in one location is scary. I know people who store confidential data like their bank account numbers, passwords etc in their Gmail account because they ‘know’ it’s safe and globally accessible. But, all one need is a simple password for your Google account and the consequences can be disastrous. The extra level of protection offered by Google is asking your password, one more time.
On the positive side (for Google lovers), dashboard is one big help. There is now a single place where you can manage all your Google accounts with easiness. Also, it provides a simple solution to find out what we are doing in the internet.
No matter whether you think this is a boon or a curse, it really made me think how much personal information I can safely put in the internet, if I am concerned about my privacy.
Links
http://googleblog.blogspot.com/2009/11/transparency-choice-and-control-now.html
http://www.google.com/dashboard

Designing a logo

I do bits and pieces of painting/drawing once in a while and I love almost everything that had anything to do with computer graphics. Electronic games are my weakness, but that’s mainly from a user point of view. Other interests are graphics programming, designing etc. Creativity has its own advantages. You can create, destroy or modify almost anything you want. More than that, I like playing God. So I jumped right in to the opportunity to design a new logo for our organization and my logo is selected as the new official logo.
Our organization - ARL - was on the process of revamping its website and the employees were given the choice of coming up with a new logo. We were free to come up with anything. No bounds were there. But it had to be agreeable to others in the lab. The main factors I had to keep in mind when designing a logo was that it should be easily printed on paper (in color, gray scale and black & white) as well as clothes (embroidery), stationery items like mugs, pens, plastic etc. Also the colors should stand the test of time and space (stretching, different media etc).
In the beginning, I was not sure whether I could do it. Finding the starting point was my main challenge. I had to formulate and idea and then start off from there. I kept thinking about it for some time and decided that I will start from where my predecessor stopped - the old logo. My plan was to rebuild the old logo first, may be with minor modifications in phase 1 and then add any new ideas as it comes along my way.

Old Logo

I looked at the old logo and asked myself, what are the key elements in there and what can I do to make them look better. After some thought and discussion with my professor, I decided to concentrate mainly on the following.
1. Make a new earth with glossy surface and a good reflection (inspiration: windows vista aero interface)
2. Make the bubbles, bubblier.
3. Decide whether to retain the waves or not. If retaining, try a different look. (The shell & waves are adaptation from the TMSI (Tropical Marine Science Institute) logo, to which ARL is affiliated to.)
4. New fonts for ‘ARL’.
I started with the earth part. The only tool I have used for the whole process is Adobe Photoshop. (Both ver. 7 and CS4). I searched the net for tutorials for a glossy globe and found this one.
http://www.denisdesigns.com/blog/2009/06/create-a-glowing-globe-icon-in-photoshop/
And that’s from where I started. The result of my first experiment looked like this.
Ok, now that I have a place to start from, I started playing with other factors like the bubbles, fonts, waves etc. Some of the tutorials I have used are given in the reference section. I downloaded custom brushes, fonts etc. My reconstructed logo, with new bubbles and font, but without the waves looked like this.
Ok, phase 1 is over. Now for the next phase, I wanted ideas, something that everyone will notice from the previous logo, at the same time, retaining the key elements of the old logo. That’s when I noticed the color combo of NUS website. Orange, blue and white. That’s from where I got the idea of using different colors. Ok, orange and blue, one of my favorite combos and at the same time, a theme which goes along with NUS website theme also. I had to start the logo all over again. The result looked much better than the green one (from my point of view).
I also had to create the ripples that originate Singapore. For that I found many methods/tutorials, but none was getting close to what I wanted. Then my professor sent me a link to try and voila! It worked. Also it was he who suggested keeping a simple font.
The result of my earlier experiments looked like this.
Another of my experiment with waves and without ripples resulted the following.
I ignored the idea of waves in the beginning itself as I was not able to do a nice work and it’s a bit difficult job and I was too lazy for that.
The above logos were used to collect feedback. Some of the main feedbacks received were, the ‘ARL’ text is not proportionate to the size of the globe, the gradient color scheme is difficult to do embroidery on t-shirts, the ripples are too small, since the ripples are there in the land, it given an impression of tsunami (We wanted the ripples to represent acoustic waves - showing the relation to our research domain) etc.
I redesigned again and came up with the final logo with bigger ripples explicit to the blue region (water) and a bigger single color ‘ARL’.

Final Logo

And that’s how this logo was born. Different versions of logo were made with different sizes, background (alpha channel), color/gray scale etc.
I never thought I will end up with this logo when I started. But when looking back, I feel great about this project. Special thanks for my professor who helped me from the starting point till I finished this project, with valuable advices and suggestions.
Along with the logo, I have also designed a simple map to reach our facility which you can find in the ‘contact’ page in our website. It was real fun making it.

References and tutorials which helped me in designing the logo
Glossy Globe
Bubbles
Text Effects
Ripples

Additional references and tips
Layer Masks
Custom Brushes
ARL
http://arl.nus.edu.sg/twiki/bin/view/ARL/Contact
http://arl.nus.edu.sg/twiki/bin/view/ARL/People
I am not an expert in photoshop, but drop in a comment if you think I can help you with photoshop.

CHOKe - A stateless active queue management scheme for approximating fair bandwidth allocation

I had to do a literature/paper review as part of one of my courses (EE6902 Computer Communication Networks). I selected a queue management algorithm for internet routers which is R. Pan, B. Prabhakar and K. Psounis, “CHOKe: A stateless active queue management scheme for approximating fair bandwidth allocation”, IEEE Infocom 2000. It is a very interesting paper considering the fact that it was published nearly a decade ago. This is one of the very few ideas I have come across and thought, "Why haven't I thought about this before?" I am not attaching the whole paper here (it’s around 20 pages), but the summary part of my paper review. In a nutshell, I my review is “This is an excellent research paper in all aspects such as the organization of the contents, quality and quantity of the content. One can easily deduce both by reading the paper and by looking at the later works that are based on this paper, that this paper is the result of an extensive and painstaking research and also an important milestone in this field.”

1. Introduction
Congestion control has always been a topic of interest among network designers and engineers. This paper proposes a simple and elegant method of implementing congestion control in internet routers which incorporates both fairness and simplicity. The main motivation behind this work is the need for a simple stateless algorithm that can achieve flow isolation and/or approximate fair bandwidth allocation for internet routers.
The authors start off by presenting the difference between responsive and unresponsive flows and different models for congestion control. During the time of congestion in a router, a responsive flow (TCP based) adjusts its rate automatically where an unresponsive flow (UDP or a bad TCP implementation), will be impassive to the conditions in the router and aggressively use up more bandwidth than responsive flows. This shows the need for fairness while choosing a packet to keep/drop during the time of congestion.
The models for congestion control fall broadly in to two categories. 1. Scheduling algorithms and 2. Queue management algorithms. The scheduling algorithms drop packets depending on the state information of each flow stored locally and therefore results in a fairer bandwidth allocation. But they are expensive to implement in terms of computational complexity and storage required and naturally doesn’t scale well. Various implementations are Fair Queue (FQ), Core Stateless Fair Queuing (CSFQ), and Stochastic Fair Queuing (SFQ). The queue management algorithms are stateless and are simple to implement at the expense of fairness. The main algorithm in this category is Random Early Detection (RED) [2]. Even if RED solves some of the issues with drop tail mechanism, it doesn’t provide fairness among responsive and unresponsive flows. Other variations are RED with penalty box, Flow RED (FRED) etc which requires partial state information and Stabilized RED (SRED) which identified misbehaving flows but doesn’t provide a mechanism to penalize them.
CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for unresponsive flows) proposed here incorporates fairness similar to that of scheduling algorithms while keeping the simplicity of a queue management algorithms. When a packet arrives at a congested router, CHOKe draws a packet at random from the queue and compares it with the arriving packet. If they both belong to the same flow, both are dropped, else the randomly chosen packet is left intact and the arriving packet is admitted in to buffer with a probability of p (calculated in the same way as in RED). 2 main ideas drive the usage of this technique. 1. The likelihood of the randomly chosen packet belonging to a misbehaving flow is high. 2. A packet belonging to a misbehaving flow is more likely to trigger a comparison since they arrive more frequently.

2. CHOKe Algorithm
CHOke marks two thresholds in the FIFO buffer, minth and maxth. The algorithm is self-explanatory from figure 1.

Figure 1: The CHOKe algorithm

In general, one can randomly choose any number of packets from the buffer (drop candidate) for the comparison (m ≥ 1). CHOKe’s performance will increase as m increases especially when there are multiple malicious flows. The selection of value of m can be automated by having any number of intermediate thresholds and choosing different value for m depending on threshold (linearly).
The implementation details are also discussed and showed verbally that only a small overhead is associated in implementing CHOKe as compared to RED.

3. Simulation Results
A standard network configuration is used to test the performance of CHOKe and compare it with RED and Drop Tail mechanisms as their complexities are close to that of CHOKE. The simulation results are presented in 3 parts: single congested link, multiple congested links and multiple congested flows.
As expected, CHOKe outperforms RED and Drop Tail in UDP throughput comparison where the latter 2 doesn’t discriminates against unresponsive flows. The throughput per flow of CHOKe is also shown where the TCP throughput reaches near the ideal fairness values. Other simulation results presented include performance under different traffic loads and queue distribution under different loadings. Similar simulation results are presented for other 2 parts.

4. Analytical Models
In this section, the authors analyze 3 different versions of CHOKe. 1. Original CHOKe, 2. Front CHOKe (drop candidate is always the packet at the head of the queue) and 3. Back CHOKe (drop candidate is always the packet at the tail of the queue). The second and third variations are used because of the difficulty of analysis of the original model.
Both the models assume independent Poisson arrivals and independent exponential service times with a FIFO queuing discipline. The models depend on the PASTA property to arrive at the results. In the case of front CHOKe, the throughput with 1, 2 and 3 flows are calculated from the analytical models and are presented along with the simulation results which are almost identical. In the case of back CHOKe, they use Markov chains to find the stationary distribution, πi. The throughput for various flows calculated from the mathematical model is presented.

5. Conclusion
The paper proposes a packet dropping scheme which is simple to implement and also maintains fair queuing among responsive and unresponsive flows. Simulation and analytical models and results are also presented to support the claims.

6. Reference
[1] R. Pan, B. Prabhakar and K. Psounis, “CHOKe: A stateless active queue management scheme for approximating fair bandwidth allocation”, IEEE Infocom 2000

Airline Maintenance

Here is a nice old joke I dug up from my funny mail forwards collection. I was searching for some old mails and saw this. Couldn’t stop laughing.

Qantas is an airline company based in Australia. After every flight, Qantas pilots fill out a form called a gripe sheet, which conveys to the mechanics problems encountered with the aircraft during the flight that need repair or correction. The engineers read and correct the problem, and then respond in writing on the lower half of the form what remedial action was taken, and the pilot reviews the gripe sheets before the next flight. Never let it be said that ground crews and engineers lack a sense of humor. Here are some actual logged maintenance complaints and problems as submitted by Qantas pilots and the solution recorded by maintenance engineers. By the way, Qantas is the only major airline that has never had an accident.

(P = the problem logged by the pilot)
(S = the solution and action taken by the engineers)

P: Left inside main tire almost needs replacement.
S: Almost replaced left inside main tire.

P: Test flight OK, except auto-land very rough.
S: Auto-land not installed on this aircraft.

P: Something loose in cockpit.
S: Something tightened in cockpit

P: Autopilot in altitude-hold mode produces a 200 feet per minute descent.
S: Cannot reproduce problem on ground.

P: Evidence of leak on right main landing gear.
S: Evidence removed.

P: DME volume unbelievably loud.
S: DME volume set to more believable level.

P: Friction locks cause throttle levers to stick.
S: That's what they're there for.

P: IFF inoperative.
S: IFF always inoperative in OFF mode.

P: Suspected crack in windshield.
S: Suspect you're right.

P: Number 3 engine missing.
S: Engine found on right wing after brief search.

P: Aircraft handles funny.
S: Aircraft warned to straighten up, fly right, and be serious.

P: Target radar hums.
S: Reprogrammed target radar with lyrics.

P: Mouse in cockpit.
S: Cat installed.

P: Noise coming from under instrument panel. Sounds like a midget pounding on something with a hammer.
S: Took hammer away from midget.