No more rush hours: An introduction to vehicular networks

Imagine doing a 70 on a highway on your convertible and imagine the loud music blaring through the wind. Imagine a sunny saturday when you are making your way to the beach, when suddenly your car tells you to slow down. There has been an accident ahead of you and the traffic is going to get to a crawl. As it turns out, some other car in front of you told your car that the traffic is going to slow down and that car came to know from another car ahead it and so on. Imagine cars talking to one another.

A vehicular network is an ad-hoc wireless networking technology that can be used to form a mobile network between cars and other vehicles, mobile or stationary; and between the vehicles and roadside access points. When I say ad-hoc wireless network, I mean the kind of network that is formed on the spur and the constituent nodes can route information between one another. One can call Vehicular Networks as VANET, and the vehicle-to-vehicle communication as V2V. Vehicle to infrastructure communication is called V2I. Add some brains to a vehicle, it can do a lot of stuff. Add networking and it opens up an amazing range of applications.

The brains here refers to having a computer or a processor that can run a few set of programs. Consider the following example. Attach an accelerometer and a GPS to a car. When the vehicle lands into a pothole, the accelerometer fires and this can be recorded along with the GPS coordinates. Its now not hard to see that multiple cars will have recorded a spike in the accelerometer readings at about the same GPS coordinates. So if I have access to all these data, I can infer sitting at my desk that there is a pothole at a particular GPS coordinate. This is precisely what MIT Pothole Patrol project accomplishes (associated paper).

You may ask why do we need vehicular networks?

Let me ask that to you - do we really want to invest time and money in getting cars to talk to one another? Do we really care if a car can figure out that there is another can coming very fast towards the intersection even though it is red? Do we want to have a technology that can potentially save thousands of lives per year? If you are like me, I assume your answer to these questions is an yes.

When do you think they may be available, you may ask. I don’t know. May be in five years, or in ten years. The automotive industry is slow to respond to innovation, partly because the lives of millions are at stake. And partly because the culture is different.

There are many safety applications possible. For example, detecting fast approaching vehicles at intersections, broadcasting traffic information to other vehicles behind and so on. Furthermore, there can be many other non-safety based application possible - such as detecting potholes and sending back the information to a central server.

Another rising star in the vehicular domain is the Autonomous vehicle - a self-driving car. Such cars do hold a lot of promise - not only in decreasing the accidents, but also in decreasing the congestion in the roads. For one, a family may not need multiple cars, since for example, the car can leave a person to his office and come back to help the spouse. This means less vehicles on the roads, and consequently less congestion. Cars can also communicate with each other to figure out when to accelerate and when to decelerate, and to keep close distance to minimize congestion (for example when the signal turns green the cars can start accelerating faster than if a human were driving so the congestion clears out faster).

Such applications not just require autonomous driving capabilities - but also the vehicular network. You can think of all sorts of crazy applications now - swarms of cars going together to minimize the wind resistance, thereby getting better fuel economy and so on.

Autonomous cars, if they become a reality will open up a slew of new applications, and if these cars can talk with one another, will change how humans move around. But for now, I must drink coffee so I don’t fall asleep behind the wheel.

via MIND. IS BLOWN http://mindisblown.com/blog/2012/11/29/no-more-rush-hours-an-introduction-to-vehicular-networks/

Finding Good Quotes

When you grow

Surfing analogy for startups

There was an interesting talk a few days back in USC by Michael Sheha (his bio at the end of the post).

One of the analogies he gave was how startups were like surfing waves. The market is the wave and one needs to choose a big wave, a really big one. Otherwise there is no fun and no revenue. And the wave is something you can’t control. Its simply there and will come gushing. You cannot try to control it or tell it to move in another direction. You will have to ride along and ride skillfully.

Another analogy he gave was that a big company is like a warship or a tanker, they cannot change direction immediately, whereas you as a startup are like a PT boat - you are nimble, agile, fast and can change direction immediately (if you are not then you are doomed, pretty much).

One of the proverbs that really caught my attention:

The road to someday leads to the town of nowhere.

Here are other things that he talked about: * Customers really provide feedback when they PAY for something. * Keep costs low, really really low. You will never know when you will need the money. You should not repent that you could have saved earlier now that your funding got delayed. * Message matters - refine it a thousand times.

Here is his bio:

Michael Sheha is currently in-between startups. Previously he co-founded Networks In Motion (NIM) in 2000, which provided Location Based Services (LBS) to the world’s wireless carriers as a private labeled application and cloud-based solution, such as wireless personal navigation for mobile devices. NIM was started in 2000 and grew to over 300 employees internationally and to over $75m/yr in revenue. In 2009 NIM received the Southern California LAVA Award for the Best Exit in Internet & Technology when it was acquired by a public company. Prior to co-founding NIM, he worked at the California Institute of Technology Jet Propulsion Laboratory’s wireless communication systems and research section responsible for the design and development of digital and radio frequency communication systems, military GPS tracking systems, and the R&D in communication link and propagation studies. Michael graduated from University of Southern California (USC) with a MSEE in 2000, and Rensselaer Polytechnic Institute (RPI) with a BSEE in 1995. He is currently living in Southern California, CA with his wife and four children.

via MIND. IS BLOWN http://mindisblown.com/blog/2012/10/13/surfing-analogy-for-startups/

liveblogging osdi 2012 tuesday

There are four main sessions today. Looking forward to the Google talk on Spanner.

Distributed Systems and Networking

DJoin: Differentially Private Join Queries over Distributed Databases

Lots of data accumulated everywhere - social networks, hospitals, airlines..

Idea 1: give all data to a trusted party - but this may not exist. Idea 2: use secure multiparty computation but may talk long Idea 3: Use Differential Privacy.

Security

Improving Integer Security for Systems with KINT

Because the integers in C don’t have unlimited precision, it is possible for them overflow. For example 2³⁰ * 2² = 0. This can be exploited by attackers. One of the famous examples is that of the iPhone jailbreak. Another is the example of logical bugs in linux kernel. There is an OOM killer which assigns scores to processes based on memory usage and then kills the processes with the highest score. This can be exploited by malicious code that can take a lot of memory but still not be detected (because by overflow their scores can get evaluated to 0).

It is in fact hard to prevent integer overflows, even if you have unlimited precision (there could be other bugs or it is difficult).

Contributions of KINT:

• a case study of 114 bugs in the linux kernel


• KINT: a static analysis tool for C programs used to find the 114 bugs.

Case study: Linux kernel. The 114 bugs have been confirmed and fixed by developers. Most are memory and logical bugs.

Writing correct checks is non-trivial.

KINT has the following modules:

• Bound check insertion


• Taint analysis


• Range analysis

Advocates the use of NaN (instead of 0 when overflow occurs).

Details at http://pdos.csail.mit.edu/kint/

Dissent in Numbers: Making Strong Anonymity Scale

via MIND. IS BLOWN http://mindisblown.com/blog/2012/10/09/liveblogging-osdi-2012-tuesday/

Liveblogging OSDI2012

I am attending OSDI 2012 here at Hollywood, CA. Lots of interesting papers here and I will try to blog about this event. In particular I am excited about attending Google’s spanner talk scheduled for tomorrow afternoon (Tuesday).

The day didn’t begin too well, because I happened to witness a roadside accident. I was on the bus going to the Loews hotel (where the conference is going on), and the bus was waiting on red. It turned green and even before the bus moved ahead, a white Toyota Prius sped to turn left. Another car came dashing on the right of the bus lane because clearly it was green for it and before anybody noticed, there was a boom and a woman shouting - the Prius was hit on its right passenger side door. From what I figured out there was no injury of anybody. Other people were busy and my bus moved on. While this was a stupid accident that could have been avoided, I wish Vehicular Networks were mainstream now. If the Prius had alerted the driver about a car coming towards it, hopefully it wouldn’t have turned left prematurely. But more than vehicular networks, I wish

Keynote

The keynote is on cancer genomics. The speaker is David Haussler from UCSC. Here is the abstract:

Cancer is a complex condition—patients present with thousands of subtypes involving different combinations of DNA mutations. Understanding cancer will require aggregating DNA data from many thousands of cancer genomes, facilitating the statistical power to distinguish patterns in the mutations. The rapidly plummeting cost of DNA sequencing will soon make cancer genome sequencing a widespread clinical practice. To anticipate this, UCSC has built a 5-petabyte database for tumor genomes that will be sequenced through National Cancer Institute projects—the Cancer Genomics Hub—and is tackling the significant computational challenges posed by storing, serving, and interpreting cancer genomics data.

Some of the questions/points raised:

• there is an enormous opportunity to bring big data techniques to cancer genomics.


• how do we find out mutations from these gene data.


• how to map these mutations to the pathways that lead us to cancer, which should help us prevent these cancers.

Flat Datacenter Storage

• FDS is simple, scalable blob storage


• distributed metadata management


• Built on a CLOS network with distributed scheduling.


• High read/write performance


• fast failure recovery


• high application performance.

Data is organized as blobs, and each blob has multiple tracts.

Consists of: - Tractserver: sits between raw disk and network. - Metadataserver: - Client

GFS/Hadoop have the following problems: - Centralized metadata server - critical path of reads/writes - large (coarsely striped) writes

DHTs: - multiple hops to find data - slow recovery

FDS tries to position itself in between.

There is a tract location table, that maps for each locator the disks it has to read.

CLOS:

Generally we have this tree structure for the DC architecture. FDS provisions as much bandwidth as each disk requires. Full bisection bandwidth is only stochastic. Long flows are bad for load balancing. FDS generates a large number of short flows are going to diverse desitnations But TCP likes long flows. FDS creates “circuits” usign RTS/CTS.

via MIND. IS BLOWN http://mindisblown.com/blog/2012/10/08/liveblogging-osdi2012/

LaTeX Tips and Tricks

Difference between that and which

The Feynman Algorithm

If you are really stuck with a problem, then try the following Feynman Algorithm. It is guaranteed to work.

1. Write down the problem.

2. Think real hard.

3. Write down the solution.

Sounds very legit, isn’t it?

via Mind. Is Blown http://mindisblown.com/blog/2012/08/03/the-feynman-algorithm/

Life as an MDP

On one particular day when I was working on a deadline, I had done two things effectively - lots of simulations on Markov Decision Processes and a debate with my friend about life. And when I was having dinner, it dawned upon me that navigating life is very much like solving a Markov Decision Process (MDP).

First a disclaimer: I am not going to teach you MDP, nor am I going to model your life as an MDP and solve it. And I am not attempting to teach you how to live your life, like my friend did today.

States of life

First off, what is an MDP? I have been wanting to write a ‘dummies guide to Markov decision processes’ (like this one), but haven’t been able to sit down to do so. I will do it, but meanwhile, take a look at the wiki page if you are not familiar. Or better, I will explain it in layman terms (which will be imprecise). The general idea is that there are what are called states of an MDP and at each state you are presented with a set of possible actions. So you want to choose the best action that is good for you in the long run. For example, you may be in a restaurant (state) and you may have the option of going for the pizza or the salad. One option may look pretty good in the short term but not in the long term, and another option may actually be good in the long run even though not so attractive in the short term. Which one would you choose?

Utility

In the MDP I was working on, there were a few states that were ‘good’ and I had to backtrack and figure out what action to take so that I will most likely reach one of those states (this statement is imprecise but you get the idea what I am trying to say). But the problem was that it was not very clear how to characterize a state as good or bad and there were a few ‘meh’ states. So we started assigning numbers to states that will measure how good a state was. And this assignment was done by something called an utility function. We had come up with a utility function and thought it did a fairly good job, but after a few simulations, I started seeing strange behavior. Some of the actions that I thought should be taken, were not being taken.

So coming back to the topic of life, as I said before, I had a discussion with my good friend about it, or about the lack of it in my case (according to him). He insisted that he was living life well and that I must learn from him. I am always at a struggle with life - to grow, to learn new things and do this and that. I always tend to swim against the current. He is always at ease, and goes along the flow and swims with the current. To me, his life looked mundane and to him my life looked awful.

Your mileage may vary

Life is very much like an MDP problem. You have a deadline to live and you start out at zero state. Along the way going from the zero to the last state, at whatever state you are in, you want to choose actions that are best suited for you. What I noticed in the MDP was that the entire course of the path from zero to the last state depended on what utility I assign to the seemingly good states. A slight change and the entire course changed. An action that was optimal before was no more optimal. I just realized that my utility was different from his and that made all the difference. So as long as you choose an utility that will make you happy at the end of it all, your way of life is the right way for you.

via Mind. Is Blown http://mindisblown.com/blog/2012/07/31/life-as-an-mdp/

Failure and the Future

Failures can be debilitating. You got badly injured while skiing and now you do not want to skii again. Your past venture into a startup was a failure and you are scared of starting anything new again. I really wanted to share an excerpt from a book called Sleight of Mouth, that essentially blew my mind off:

My grandfather taught me how to drive. He told me that I could drive safely looking only in the rear view mirror, providing the road ahead is exactly the same as the road behind.

So do you assume that the road in front of you is going to be the same as the one before?

via Mind. Is Blown http://mindisblown.com/blog/2012/07/27/failure-and-the-future/

These flowers will blow your mind

The Beauty of Flowers (Красота цветов) from VOROBYOFF PRODUCTION on Vimeo.

Pretty Against Pink