Wednesday, December 21, 2005

Why Google Will Falter in 2006?

Web search

David Kirkpatrick thinks so, and I strongly agree with him. Yahoo's recent acquisitions of Flickr and, and the remark that "Yahoo understands the importance of social search", and the latest rumors on community based search, all point towards this. There was an article on /. a long time back on why Amazon and Google should partner up, but it looks like Google very well ignored that. I won't be surprised at all if tomorrow Amazon and Yahoo pool in their user profile data and recommendation systems, and unleash the full power of the global brain upon the world. Surprisingly, the idea of the global brain was first proposed by Douglas Adams in Chapter 29 of the HitchHiker's Guide to the Galaxy, and corroborated by Scott Adams in God's Debris, and even tried to be put into practice by a handful of companies which unfortunately went bust around the dot com bubble. Just try googling for it. Internet stalwarts had conveniently ignored it so far, but it's only now with the Web 2.0 wave that things are moving towards how they should be.

But there are gaps with what Yahoo, Amazon, and everybody else are thinking about with search. Search is not everything. The vision of the global brain goes beyond that. But I was definitely surprised when I realized yesterday how the global brain tied in with my ideas of an ideal democratic political system.

Anyways, let's examine other points about the article.


I will not give up so easily on Google though! Nobody can! We're all in love with it! I haven't followed up very closely on Microsoft's Vista, mainly because there is a lot of activity going on otherwise with the Tenor active desktop in KDE, ReiserFS, Flamenco from UC Berkeley, and most important of all, Google Desktop. Google surely knows that they can take over the entire desktop from Microsoft. Let's see what you need a desktop for anyways. It's just for saving and retrieving files locally, right? Google Desktop's philosophy is, save for all you care, and we will help you retrieve it. The active desktop concept only makes it better with tagging and context awareness, and it can be easily implemented through AJAX components in the web browser that talk to Google Desktop about everything they do! This is what Jason Kottke's vision of the Web OS is all about, and Google might be just implementing it today. My vision is of a single active desktop that will be the Internet browser, email client, file explorer, iTunes store, with Konfabulator like icons to make it look prettier, and VmWare virtualization to package and unpackage your desktop as you move from one endpoint to another. Heck, maybe you won't even have different endpoints 10 years from now - it'll all be thin clients if network bandwidths and computation capabilities keep up with Moore's Law! Maybe this is why Google does not care too much about Yahoo and Amazon. They are already gathering user profile data for personalized search, and now they have google base and the web accelerator for centralization of information too - Go Google Go!


Correct again! Please read Keshav's paper on why cellphones (also read, PDAs) are the future of the Internet, and my earlier blog on the future of the Internet. Cisco has been making acquisitions left, right, and center. Their vision is to turn the cable providers into wireless ISPs through WiFi meshes, and make video broadcasting and on-demand video even more cheaper with Scientific-Atlanta settop boxes plugged into wireless APs. I wonder where this will leave TiVo... On the other hand, cellular providers are trying the opposite route with EvDO, UMTS, and WiMax coverage to provide video and other content based services. Both the cellular providers and cable providers are pitted in a battle against each other - let's see where it goes. The WiFi gang seems to have a lead in terms of deployment time for sure, but their life is not going to be so easy with the management of thousands of APs, which is where the cellular providers have an upper hand with the larger footprint of their base stations.

Wednesday, December 07, 2005


Another wonderful addition to social software, this time from nobody other than my dear buddy Shashank. Behold Krawler[x]. It's a desktop application through which you can upload content and share it on the network, coupled with a social network of friends and communities. The interface is really cool. And it even has an integrated IM.

The best part is content creation, especially for educational purposes. You can create quizzes, assignments, and lessons, and have full pedagogic control through which you can shuffle chapters or questions back and forth. You can even have programmble rules for automatically controling the sequence and difficulty of questions. Clearly a boon for online learning.

It's in beta stage for now, but the lackings will soon be addressed. Try it out! Download here.

The possibilities are endless given all the stuff going with Web 2.0, but I wonder if they can live up to the expectations in time. I was disappointed that they chose to create a new desktop application to achieve the same goals that could have been achieved by a web-based system instead, especially when the whole world is anyways moving towards the web.

Friday, November 11, 2005

Congestion in cellular networks

During the WWRG meeting today, Kamran mentioned a problem about congestion in the cellphone networks in crowded places. It is indeed a valid problem because each cell can only accomodate a maximum number of users and the provisioning is always done for an average load.

I suggested that one way to get around this would be through the use of cellular relays. Most cellphones now have WiFi and Bluetooth that can form an adhoc network to transport messages or push-to-talk packets out of a congested cell into a neighboring vacant cell. This solution is well known, but the problems with implementation are incentives on why should somebody forward messages from an unknown person at the expense of his battery, and how to handle security in this case where possibily neither cellphone can connect directly to the outside network.

Incentives can be built through a notion of long term fairness using brownie points. Each time somebody forwards somebody else's messages, he earns points. He can encash these points later when he is in a situation where he needs to use the same (or a different) service from another person. How to ensure security in this so that tokens for brownie points cannot be impersonated, cannot be replayed, and cannot be stolen? My paper with Keshav on Practical Security for Disconnected Nodes is perfect in this situation. Slides about the protocol details are also available.

Message secrecy can also be ensured using the techniques outlined in our paper.

Tuesday, November 08, 2005

Ultra cool social software

Go check out the following - they're all super cool: is going to use user-defined tags and ranking for web search, clustering, and disambiguation. They also have a notion of sharing where you can share your tag-set, or a cluster of links associated with each other. is kind of similar, except that the focus is more on blogs and comments, rather than search. is a blog website with communities, mainly meant for teanagers to share their daily diary. lets you write about places you have been to, and places you want to go, and hook up with other people with similar interests. And there are sister websites for 43 things and 43 consuming. plugs into winamp, and reports back what kind of songs you like, and then let's you discover radio stations with similar songs. gives an integrated management interface that allows you to handle blogger, 43 places, livejournal, digg, and lots more from a single console.

Google Deskbar: A replacement of the Windows Taskbar?

Is that what it is going to be? Well, it almost is already! It can launch applications, it can show you your IMs, your emails, and ofcourse, much much more. The day is not far, Microsoft beware!

Tuesday, November 01, 2005

Tim Bray's talk

Fill this in...

Al Javed's talk

Fill this in...

Friday, October 28, 2005

Time gap between research and commercialization

Fill this in...

Friday, September 23, 2005

Vehicular networks for driver safety, by Raif Herrtwich, Daimler Chrysler. At Mobicom 2005, Cologne, Germany.

The presentation was certainly an eye-opener on the developments happening in this area. Surprisingly, a significant amount of progress has already been made towards deployment. The 802.11p working group is standardizing the PHY/MAC for vehicle-to-vehicle and vehicle-to-infrastructure communication. The IEEE 1609.x group is working on application layer standardization. The FCC has allocated 75Mhz in the 5.9Ghz band for this as well.

Broadly, the ideas are that onboard equipment on vehicles will be equipped with GPS and tied in together with the safety belts, steering to prevent skidding, and warning alerts; cars will be able to warn each other and propagate warning back and forth. The onboard equipment will also be able to communicate with the roadside infrastructure that can conduct electronic payments, monitor traffic, send updates, and switch traffic signals. A large number of interesting use-cases were highlighted.

Keywords: DSRC, 802.11p, VII (Vehicle Infrastructure Integration), VANET (Vehicular Ad Hoc Networks)

Proposed research areas: (a) Security – Problem in security for adhoc networks is the absence of a third party certification agency, and hence identity becomes a problem. This is probably not true for VANETs because the onboard equipment can always be pre-provisioned with certified public keys. (b) Routing – Assume GPS availability, road mobility patterns. (c) Mobility models for road traffic in different parts of a city.

Questions: What seemed impractical was the initiative to create a completely separate infrastructure for driver safety, and to not use the existing cellular infrastructure. The cellular providers will definitely be interested in provided QoS guarantees for emergency traffic, and they are already thinking in terms of sensor networks from homes, cars, farms, everywhere, talking to the Internet core via the cellular networks.

The future of the Internet

Different endpoints will access services deployed in the Internet core through heterogeneous access networks. Huge developments are taking place today on each of the three fronts:

1. Internet core

Services deployed in the core can be categorized as follows.

a. Computation and storage: Data is getting centralized, and following Moore’s Law, data centers are getting cheaper to deploy. Force 10 recently announced 10Gbps Ethernet switches to connect server racks directly to IP backbones. Orion released a 96-node supercomputer small enough to fit under a computer desk. With better server virtualization technology, it will not be long before users will be able to own slices on their personal blade servers to store huge amounts of data and offload heavy computation from thin endpoint devices to centralized resources.

b. Policy control: The IMS (IP Multimedia Subsystem) creates a control plane that unifies wired and wireless ISPs to provide users with seamless roaming access to different services through a federated authentication/billing framework. IMS also enables a basic infrastructure for pushing alerts to endpoints, acquisition of location and presence information, and other features, that allow application providers to deploy new applications and services easily. It is expected to hit full-fledged deployment by 2010.

2. Access networks

A whole plethora of wireless and wired technologies are being deployed, and this will lead to a highly heterogeneous access infrastructure because each technology complements the others, and is best suited for its own set of applications.

a. Fixed broadband: Huge investments are being made by Verizon for FTTH and by SBC for FTTP which promise to deliver IP based video content and broadband Internet access to homes. Even cable companies like Comcast are laying out extra fiber to enhance their network capacities. At the same time, there is growing interest in fixed wireless broadband services through WiMax 802.16d CPEs (Customer Premise Equipment) because a wireless infrastructure is cheaper to deploy. Furthermore, attachments of WiFi access points to each fixed network connection will not only allow high-speed wireless access inside homes and offices, but it will also provide better backhaul mechanisms for WiFi mesh networks described next.

b. Mobile broadband: We consider technologies like 3G EvDO and UMTS, WiFi meshes, WiMax 802.16e as competing with each other for mobile broadband Internet access. Although their respective network characteristics and costs differ widely, they will continue to coexist and overlap for a number of years, driven by different providers who support different technologies.

c. Mobile video: Infrastructure is just beginning to get deployed for delivery of video on wireless to mobile devices. DVB-H and Qualcomm’s MediaFLO are suited for video broadcast and require their own terrestrial broadcast infrastructure, while BCMCS and MBMS are better for multicast on CDMA and UMTS networks respectively. Newer technologies like DRM are able to achieve video transmission on AM as well, and are likely to come into the mainstream as well.

3. Devices

Endpoints are becoming more and more powerful. Not only are computation and storage on the devices getting faster and better, even battery life is increasing manifold with recent developments on fuel-cell research. Samsung now markets laptops with hybrid flash and hard-disk persistent storage that reduce the battery consumption even further. The fastest growth has however been on the cellphone front with more than 1.8 billion devices in the market today, and it is projected that cellphones (or docked cellphones ) will be the dominant form-factor for accessing the Internet in the future. Different devices can be categorized in terms of their mobility, and this determines the kind of access networks that they will use. For example, TiVo set-top DVR boxes converged with computer desktops will rely on the fixed broadband network infrastructure, whereas cellphones will generally use EvDO/UMTS and MediaFLO kind of technologies, and laptops will mostly use WiFi inside buildings and wireless broadband when on the move. Since each device can potentially connect to different networks in different circumstances, most mobile devices are now capable of interfacing with multiple technologies.

The other kind of devices is sensors. In the next couple of years sensors will become ubiquitous in homes, in cars, in farms, with the aggregate information backhauled over wireless networks. Eventually each electronic device will have sensors embedded in it, and this will have a tremendous impact on our civilization.

All these technologies will enable a lot of new applications. Imagine being able to download soccer highlights on your cellphone, watch television on your laptop, stream music from your desktop at home to your iPod, do a high bandwidth upload of pictures and videos from your cellphone to a data center, synchronize your office desktop to your tablet PC, download large email attachments on WiFi and just the email bodies on GPRS, monitor real time what is going on in your home, and many more things. It is very likely that a lot of you might have heard of such descriptions for future architecture in the Internet, but it is difficult to see through this maze of technological developments and recognize the missing pieces that are required to realize the final vision. This is what research should focus on these days.

Enabling opportunistic communication in sensors for better power conservation

Imagine that you have temperature or pollution sensors sprayed along river beds or ponds, and you fly a plane overhead or row past in a boat to pick up information from these sensors. You need opportunistic communication here so that the sensors can somehow detect that an information aggregation resource is close by, wake up, send the data, and then again go off to sleep. This will be more power efficient than to have sensors wake up every now and then to detect a wireless signal.

The Rf-Id wakeup idea becomes applicable here. You just have to transmit energy from the plane to wake up the devices. And not just that, but optimizations can also be made in the way such sensors are designed. Consider this:

1. The radio wakes up through a RFID like circuitry on detecting a flood of wireless energy in the medium
2. Sets up the connection
3. Wakes up the processor and boots a small OS from a flash memory or ROM
4. Receives or transmits whatever data it needs to
5. Again powers down the processor
6. Periodically wakes up the processor and boots the full fledged OS to do whatever local processing it needs to

I am not aware of the state-of-the-art in sensor research, and it is likely that such work for design of sensors might have been done already. But there are some MAC layer problems for Rf-Id wakeup in such cases. A flood of energy is not just going to wake up one sensor, but many sensors. If all start transmitting at the same time, there is bound to be interference. Maybe, just an initial random backoff might suffice in this case.

Radio wakeup using Rf-Id: New MAC for opportunistic communication

The wireless chipsets in the market today have a mindset to conserve power by switching OFF most circuits during sleep (or idle) mode, and they just keep the radio amplifier and some minimal DSP active to recognize the presense of a signal, and then wake up the rest of the radio. However, if you look at the Rf-Id design, they power up using the energy in the wireless medium itself, and the passive Rf-Id chips do not need any external power source at all. Broadly, the idea is to use this kind of a Rf-Id circuit to wake up the entire radio whenever there is some energy in the medium. This idea of hierarchical radios is not entirely new. Have a look at the following papers:

Reconsidering wireless systems with multiple radios. P Bahl, A Adya, J Padhye, A Wolman.
Turducken: Hierarchical power management for mobile devices. J Sorber, N Banerjee, M Corner, S Rollins

However, what is interesting is that such a model completely changes the MAC design as well. For example, now you don't have to do Inquiry/Paging in Bluetooth, and you don't need careful time synchronization for Zigbee, and no backoff timers for WiFi.

A number of further optimizations are possible. This is paper from Mobicom 2005.

Challenges: Communication through silence in wireless sensor networks. Y Zhu, R Sivakumar

Their basic idea is to go back to morse code telegrahy from 150 years ago by transmitting information in pulses to save on power. We can use it for communicating low bandwidth control information. For example, a node can send its identity in pulses and only the correct receiver needs to wake up then. Scheduling information can also be sent out similarly. We will need to take care of contention in the control channel though - maybe have a FDD scheme for it. The electronic design should not be complicated at all - just a timing circuit and a bunch of shift registers strung togteher - and it should be possible to achieve zero-power scheduled and intelligent wakeup this way.

We should find out what is the bandwidth in which a Rf-Id tag can differentiate between frequencies. And what is the relation between the transmit power needed to wake up a Rf-Id tag, and the distance to that tag. This will tell us more about the sanity of the idea.

Direct cellphone to cellphone communication via a thin relay

You must be aware of research efforts made for cellular ad hoc relay systems which suggested a slightly modified (or an extra) radio on cellphones that could enable ad hoc communication directly between cellphones, or from a cellphone to a thin relay.
Integrated Cellular and Ad Hoc Relay (iCAR) Systems: Pushing the Performance Limits of Conventional Wireless Networks

The reason why a radio modification is required for such systems is that the chipsets on cellphones are hardwired to communicate to the infrastructure only. Dual mode cellphones can however get around this problem by enabling ad hoc communication on the WiFi interface instead.
UCAN: A Unified Cellular and Ad Hoc Relay Architecture

If all this works, you can have all your old camera phones plugged in different rooms as security cameras, or for medical survelliance, or just to enable the digital home vision in a cheap way. The problem however is that hardly any phones discarded today have WiFi on them. Some do have bluetooth radios but the range is very small. Hardware hacks inside phones will be needed to increase the range.
Recyclying a billion cellphones

I was however thinking that low bandwidth ad hoc communication might still be possible on current dat unmodified cellphones on the cellular GPRS/CDMA interface by using a low cost relay acting as a fake base station. All that this relay will have to do is as follows:

1. Listen to the pilot channel of the network that is giving cellular coverage to the area, and infer what channels are free for low power communication to nearby cellphones. This is purely to avoid interference with the actual cellular network.
2. Start broadcasting paging channel and access channel parameters on its own pilot channel at a low power.
3. Receive SMSes from the cellphones on the access channel (which is unencrypted) for uplink communication.
4. Forward SMSes to the cellphones on the paging channel (which is also unencrypted) for downlink communication.

Thus, the paging and access channels can be used with SMS as a transport layer. SIM cards will not be needed, and no communication with the infrastructure will be required. I agree that high bandwidths will not be possible, but this will suffice for the kind of applications that do a lot of local processing and do not have huge amounts of data to transmit.

With all the work available on SDRs, designing such a relay should not be too difficult. The idea here is to have some cheap device that just understands 3 channels, can be plugged anywhere inside homes, and can link together old cellphones that do not even have a SIM card. On the device side, most cellphones support a J2ME or BREW virtual machine with downloadable apps, and that is all that is needed on cellphones to enable this solution. In fact, this was a major reason to use simple out-of-the-box mechanisms because the J2ME or BREW app on cellphones only needs to send and receive SMSes now.

There are companies like Clariton that tie up with cable modem ISPs and provide a celluar RF to fibre conversion at the modems, and a reconversion to RF at tap points closer to cellular base stations. This helps alleviate the problem of poor cellular coverage inside buildings. The SDR relay could simply be integrated with their solution.

I will hasten to add that putting this SDR relay inside homes may not be the best application at all. What might instead be feasible is to include relay functionality in the cellphones itself. This will be a move towards cognitive radio where cellphones will sense the environment so as not to create any interference, and yet be able to communicate with peer cellphones directly. What seemed cool to me was that such relayed communication was indeed possible.