Mesh Networking Summit 2004



Mesh Networking Summit 2004 is a two-day intensive mindswap event between industrial and university researchers to discuss wireless mesh networking, ad-hoc networking, community networking, and residential broadband access. The goal of this summit is to determine how academia and industry can come together to make mesh networking mainstream. The attendees include established researchers with expertise in areas that cover the entire OSI stack including: smart antennas, PHY communications, medium access control, multi-hop routing, QoS, network management, Internet protocols etc. The meeting will be interactive with a healthy dose of information exchange as the researchers collectively identify open problems and impediments to deployment. It is the hope of the organizers that at the end of this meeting, all attendees will have a better understanding of the state of the art and the key set of open research problems. The meeting will help identify areas for potential collaborations among the participants.


  • Victor Bahl, Microsoft Research
  • Nitin H. Vaidya, University of Illinois Urbana Champaign

Non-Microsoft Participants

  • William A. Arbaugh (University of Maryland)
  • Elizabeth Belding-Royer (University of California Santa Barbara)
  • Scott Burke (PacketHop Networks)
  • Samir Das (State University of New York Stony Brook)
  • Jim Freebersyser (Honeywell)
  • J.J. Garcia-Luna-Aceves (University of California Santa Cruz)
  • Admela Jukan (National Science Foundation)
  • Kerry Haley (SkyPilot)
  • Jean-Pierre Hubaux (The Swiss Federal Institute of Technology Lausanne)
  • David Johnson (Rice University)
  • P. R. Kumar (University of Illinois Urbana Champaign)
  • Jim Kurose (University of Massachusetts)
  • Lakshman Krishnamurthy (Intel CAL)
  • Robert Morris (Massachusetts Institute of Technology)
  • Ali M. Niknejad (University of California Berkeley / BRWC)
  • Jason Redi (BBN Technologies)
  • Ashutosh Sabharwal (Rice University)
  • Stefan Savage (University of California San Diego)
  • Scott Shenker (International Computer Science Institute)
  • Devabhaktuni “Sri” Srikrishna (Tropos Networks)
  • Mani Srivatsava (University of California Los Angeles)
  • Peter Stanforth (Meshnetworks)
  • Ion Stoica (University of California Berkeley)
  • Nitin Vaidya (University of Illinois Urbana Champaign)
  • Xudong Wang (Kiyon Inc.)
  • David Wetherall (University of Washington)

Technical Program

Sponsored by Microsoft Research & Microsoft’s Advanced Strategy Group

Click here to download a PDF version of the Technical Program.

Wednesday, June 23, 2004

7:30 – 8:30 Breakfast with Craig Mundie (Falls Terrace)
8:45 – 9:15 Welcome Remarks (Salish Ballroom)

Rick Rashid, Senior Vice President, Microsoft Research

9:15 – 9:30 Opening Remarks – Summit Goals

Victor Bahl, Summit Organizer/Senior Researcher, Microsoft Research
PPT (1,775 Kbytes) | Video

9:30 – 10:30 Keynote: A Global Perspective on Mesh Networking,

Craig Mundie, Chief Technology Officer, Senior Vice President, Advanced Strategy & Policy, Microsoft
PPT (15,077 Kbytes) | Video

10:30 – 10:45 Morning Break – Snacks & Mingling
10:45 – 12:15 Session 1: Architectures & Techniques for Large-scale Wireless Meshes

Session Chair: Alec Wolman

  • SENSE: Scalable and Efficient Networking of Sensor Elements, J.J Garcia-Luna-Aceves (University of California Santa Cruz)
    PPT (718 Kbytes) | Video
  • Making Radios More Like Human Ears: Alternative MAC Techniques and Innovative Platforms to enable large-scale Meshes, Lakshman Krishnamurthy (Intel Communications Architecture Lab)
    PPT (10,253 Kbytes) | Video
  • Exploiting Diversity in Mesh Networks, Nitin Vaidya (University of Illinios Urbana Champaign)
    PPT (251 Kbytes) | Video
  • Microsoft’s Mesh Networking Research, Victor Bahl (Microsoft Research)
    PDF (3,554 Kbytes) | Video
12:15 – 13:15 Lunch (Falls Terrace)
13:15 – 14:45 Session 2: Understanding and Increasing Mesh Capacity

Session Chair: Venkat Padmanabhan

  • Capacity, Architecture, and Protocols for Wireless Networks, P. R. Kumar (University of Illinois Urbana Champaign)
    PPT (754 Kbytes) | Video
  • Capacity and Fairness in Multihop Wireless Backhaul Networks, Ashutosh Sabharwal (Rice University)
    PPT (580 Kbytes) | Video
  • New Opportunities in Wireless Communications, Ali M Niknejad (University of California Berkeley)
    PPT (647 Kbytes) | Video
  • Commodity class Phased Array Antennas, Jim Kajiya (Microsoft Research)
    PPT (5,800 Kbytes) | Video
14:45 – 15:30 Research Demos, Posters, Snacks, and Mingling

Session Organizer: Atul Adya
Location: Falls Terrace
Demo/Poster Descriptions

  • Mesh Monitor and Diagnostic Tool
  • Preview of Native WiFi
  • MultiNet: Connecting to Multiple Wireless Networks
  • Routing in Multi-Radio Multi-Hop Wireless Mesh Networks
  • Slotted Seeded Channel Hopping
  • Longhorn Location Platform
  • Quality Windows Audio Video Experience (qWave)
  • Investigating Outdoor 802.11 Performance
  • Secure Routing in Open Networks with secure traceroute
15:30 – 17:15 Session 3: Path Selection and Testbed Studies

Session Chair: Jitu Padhye

  • Stony Brook Mesh Router: Architecting Multi-Radio, Multihop Wireless LANs, Samir Das (Stony Brook University)
    PPT (798 Kbytes) | Video
  • Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking, David B. Johnson (Rice University)
    PPT (783 Kbytes) | Video
  • MIT Roofnet Performance, Robert Morris (Massachusetts Institute of Technology)
    PPT (2,958 Kbytes) | Video
  • Distributed Monitoring of Mesh Networks, Elizabeth Belding-Royer (University of California Santa Barbara)
    PPT (292 Kbytes) | Video
  • Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks, Richard Draves (Microsoft Research)
    PPT (905 Kbytes) | Video
17:15 – 17:30 Break
17:30 – 19:00 Session 4: Self Management and Security

Session Chair: John Dunagan

  • Security Challenges for Mesh Networks, Jean-Pierre Hubaux (EPFL)
    PPT (1,305 Kbytes) | Video
  • Encouraging Cooperation in Multi-Hop Wireless Networks, David Wetherall (University of Washington)
  • Low-cost 802.11 Wireless Infrastructure Networks, Stefan Savage (University of California San Diego)
    PPT (4,367 Kbytes) | Video
  • Troubleshooting a Wireless Multihop Mesh Network, Lili Qiu (Microsoft Research)
    PPT (212 Kbytes) | Video
19:30 p.m. Dinner (Falls Terrace)

Host: Dan Ling, Vice President, Microsoft Research

Thursday, June 24, 2004

8:00 – 8:30 Breakfast (Falls Terrace)
9:00 – 10:00 Keynote: Pervasive Collaborative Wireless Networking

Jawad Khaki, Vice President, Windows Networking Division

10:00 – 10:30 Morning Break – Snacks and Mingling
10:30 – 12:00 Panel: The Commercial Applications and Applicability of Mesh Technology

Moderator: Jeff Erwin (Microsoft)

Panelists: Scott Burke (PacketHop Networks), Devabhaktuni “Sri” Srikrishna (Tropos Networks), Jim Freebersyser (Honeywell), Peter Stanforth (MeshNetworks), Mani Srivatsava (University of California Los Angeles), Kerry Haley (SkyPilot)
Jim’s PPT (997 Kbytes) | Video

12:00 – 1:30 Lunch (Salish Ballroom)
13:30 – 13:45 Discussion Framework and Deliverables,

Nitin H. Vaidya, University of Illinios Urbana Champaign

13:45 – 15:30 Working Group Breakout Discussions

Mesh Capacity WG (Ballroom)
– Lead: Nitin H. Vaidya (University of Illinois Urbana Champaign)
Mesh Connectivity WG (Falls Terrice)
– Lead: Dave B. Johnson (Rice University)
Mesh Security & Management WG (Vintage)
– Lead: David Wetherall (University of Washington)
Mesh Distributed Services WG (Atrium)
– Lead: Ion Stoica (University of California Berkeley)

15:30 – 16:00 Coffee, Cookie & Soda Break
16:00 – 17:20 Working Group Reports

16:00 – 16:20 Mesh Capacity WG Video
16:20 – 16:40 Mesh Connectivity WG Video
16:40 – 16:00 Mesh Security & Management WG Video
16:40 – 17:20 Mesh Distributed Services WG Video

17:30 – 18:00 Impressions – Jim Kurose (University of Massachusetts) (Video) and Scott Shenker (International Computer Science Institute)

Summary & Closing Remarks – Victor Bahl, MSR

18:00 Meeting Adjourns

Program Notes

Meeting Goals

Over two decades of research has yielded many conferences, workshops and meetings focused on multi-hop wireless networks. Around the globe, hundreds of papers are published every year – there is so much research, yet so few products. While the interest in the research community continues to rise, fueled by the funding available from DARPA and NSF, the industry remains lukewarm in pursuing opportunities in multi-hop wireless networking. Researchers motivate their work using the now cliché’ disaster-emergency response, battle theatre communications, and space/planet explorations applications. Start-ups have identified a few commertial applications, however, these too are in vertical markets.

We believe there are two applications that can make mesh networking mainstream. These are: Inter-home mesh networking or Community Mesh Networking and intra-home mesh networking.

There are several advantages to enabling community mesh networks. For example, when neighbors cooperate and forward each other’s packets, they can together share faster, cost-effective Internet access via gateways distributed in their neighborhood; they can cooperatively deploy backup technology that securely and privately distributes their data in the neighborhood so users never have to worry about losing precious information due to a catastrophic disk failure; Community meshes allow bits created locally, to be used locally without having to go through a service provider and the Internet. Neighborhood networks allow faster and easier dissemination of cached information that is relevant to the local community.

Mesh Networking Summit 2004 will address the research challenges in widescale deployment and acceptance of mesh networking. Researchers with expertise in different areas will share notes and discuss remaining impediments in core technologies that need to be overcome. It is the goal of the organizers to provide researchers a set of presentations and meeting notes that articulate the future research agenda for making community mesh networking popular. We hope to stimulate future research initiatives and collaborations between university and industry researchers as we collectively strive to make mesh networking mainstream.

Reading Materials

Working Group Topics and Participant Assignment

Mesh Capacity WG

Meeting Room: Ballroom

Topics: Directional antennas, MAC & PHY design, interference management, multi-radio systems, channel management, link estimation, cognitive radio, power management, capacity estimation, 60 GHz wireless etc.

Group Leader: Nitin Vaidya (UIUC)

Participants: Kumar (UIUC), Kajiya (MSR), Niknejad (UCB), Wolman (MSR), Freebresyser (Honeywell), Krishnamurthy (Intel), Bahl (MSR), Sabharwal (Rice), Yao (MSR Asia), Redi (BBN), Ferrell (MS-Venice Team), Popoff (MS-Venice Team)

Mesh Connectivity WG

Meeting Room: Falls Terrice

Topics: Routing, metrics, topology control

Group Leader: David Johnson (Rice)

Participants: Garcia-Luna-Aceves (UCSC), Morris (MIT), Das (SUNY), Belding-Royer (UCSB), Srivatsava (UCLA), Draves (MSR), Zill (MSR), Padhye (MSR)

Mesh Self Management & Security WG

Meeting Room: Vintage

Topics: Information distribution, fault detection, isolation, diagnosis and management, incentives, security

Group Leader: David Wetherall (University of Washington)

Participants: Arbaugh (UMaryland), Savage (UCSD), Qiu (MSR), Adya (MSR), Jukan (NSF), Hubaux (EPFL), Kelly (MS-Venice), Burgess (MS-Venice)

Mesh Distributed Services & IP Networking WG

Meeting Room: Atrium

Topics: Clock synchronization, distributed naming services, address assignment/auto-configuration, P2P, fairness, quality of service

Group Leader: Ion Stoica (Berkeley)

Participants: Shenker (Berkeley), Kurose (UMASS), Padmanabhan (MSR), Erwin (MS), Stewart (MSR Cambridge), Ginchereau (MS-Venice)

Abstracts & Bios

Session 1: Architectures for Large-scale Wireless Meshes

10:45 – 12:15, Wednesday, June 23, 2004

SENSE: Scalable and Efficient Networking of Sensor Elements


Jose Joaquin Garcia-Luna-Aceves | University of California Santa Cruz


Networks of sensors can be used to instrument and monitor systems and phenomena in more efficient and affordable ways than using sets of individual sensors acting in isolation. However, this requires the nodes of a sensor network to communicate untetherly with other nodes nearby, to self organize into a network consisting of arbitrarily large numbers of nodes, and to process information related to the system or phenomena locally before forwarding it to an intended destination.

In this talk I discuss the need for: (a) understanding the limits of opportunistic cooperation, with which sensor nodes collaborate with one another across mutliple protocol layers; (b) understanding the impact of the physical layer on the link-layer using analytical models; and (c) exploiting protocol modularity to bridge the gap between applications and hardware platforms of sensor networks. Several of these same issues apply to large-scale ad hoc networks in general.


J.J. Garcia-Luna-Aceves received the M.S. and Ph.D. degrees in electrical engineering from the University of Hawaii, Honolulu, HI, in 1980 and 1983, respectively. He is the Baskin Professor of Computer Engineering at the University of California, Santa Cruz (UCSC). Dr. Garcia-Luna-Aceves directs the Computer Communication Research Group (CCRG). He has been a Visiting Professor at Sun Laboratories and a consultant on protocol design for Nokia. Prior to joining UCSC in 1993, he was a Center Director at SRI International (SRI) in Menlo Park, California.

Dr. Garcia-Luna-Aceves has published a book and more than 250 refereed papers and three U.S patents, and has directed 20 Ph.D theses and 17 M.S. theses at UCSC. He has been Program Co-Chair of ACM MobiHoc 2002 and ACM Mobicom 2000; Chair of the ACM SIG Multimedia; General Chair of ACM Multimedia ’93 and ACM SIGCOMM ’88; and Program Chair of IEEE MULTIMEDIA ’92, ACM SIGCOMM ’87, and ACM SIGCOMM ’86. He has served in the IEEE Internet Technology Award Committee, the IEEE Richard W. Hamming Medal Committee, and the National Research Council Panel on Digitization and Communications Science of the Army Research Laboratory Technical Assessment Board. HE has been on the editorial boards of the IEEE/ACM Transactions on Networking, the Multimedia Systems Journal, and the Journal of High Speed Networks. He received the SRI International Exceptional-Achievement Award in 1985 and 1989, and is a senior member of the IEEE.

Making Radios More Like Human Ears: Alternative MAC Techniques and Innovative Platforms to enable large-scale Meshes


Lakshman Krishnamurthy | Intel’s Communications and Architecture Laboratory


Lakshman is a Principal Engineer at Intel Corporation in the communications technology lab, where he manages Intel’s mesh networking program. He leads research efforts into new wireless mesh protocols, techniques to provide ease of use and improve performance of wireless networks. He is also the principal investigator of EcoSense wireless sensor network project at Intel Research. As part of the EcoSense project, Lakshman is driving wireless sensing into Intel fabs by piloting a preventative maintenance application. Currently, he serves on the program committees of the ACM SenSyS and IEEE SECOM conferences.

Lakshman received a Ph.D in computer science from the University of Kentucky and a BE in instrumentation technology from the University of Mysore, India.

Exploiting Diversity in Mesh Networks


Nitin H. Vaidya | University of Illinois Urbana Champaign


This presentation will focus on the various forms of diversities available in wireless multi-hop networks. Directional antennas, multi-channel environments, and multi-rate radios give rise to the diversities of interest. The talk will identify a subset of problems that need to be addressed to be able to design protocols that exploit such diversities.


Nitin Vaidya received Ph.D. from the University of Massachusetts at Amherst. He is presently an Associate Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign (UIUC). He has held visiting positions at Microsoft Research, Sun Microsystems and the Indian Institute of Technology-Bombay. His current research is in the areas of wireless networking and mobile computing. His research has been funded by various agencies, including the National Science Foundation, DARPA, BBN Technologies, Microsoft Research and Sun Microsystems. Nitin Vaidya is a recipient of a CAREER award from the National Science Foundation. Nitin has served on the program committees of several conferences and workshops, and served as program co-chair for the 2003 ACM MobiCom. He has served as editor for several journals, and presently serves on the IEEE Transactions on Mobile Computing editorial board, and as editor-in-chief or ACM SIGMOBILE periodical MC2R. He is a senior member of IEEE Computer Society and a member of the ACM.

Microsoft's Mesh Networking Research


Victor Bahl | Microsoft Research


Microsoft Research and Microsoft’s Advanced Strategy & Policy group are engaged in creating wireless technologies that allow neighbors to connect their home networks to form a community mesh network. Compared to DSL and cable modem system that are centrally managed and under the control of a single provider, community meshes grow organically. Participants contribute network resources and cooperate for the good of the community. By enabling such connectivity, communities are able to cost-effectively share Internet gateways, and the problem of providing residential broadband Internet access in rural areas becomes a bit more tangible. New applications such as: neighborhood backup systems, neighborhood security systems, neighborhood broadcast systems for live streaming of locally relevant sports and social events, neighborhood caching systems, and neighborhood auction (garage sale) systems emerge.

To realize the dream, we have to solve many challenging problems including capacity and range enhancement, self management, privacy and security, resource fairness, QoS etc. Success also depends on wise spectrum management and business economics. In this talk we will outline the technical problems that continue to challenge us despite several decades of research in packet radio networks. We will describe our approach to handling these problems and discuss a new capacity enhancing scheme that we have recently designed.


Victor Bahl is a Senior Researcher and Manager of the Networking Research Group at Microsoft Research. Since joining Microsoft in 1997, he has worked on making high-speed wireless networking a mainstream technology. His seminal research in this area includes: WiLIB, a general purpose programming interface for wireless network cards; RADAR, a signal strength based indoor user-location determination system; CHOICE, a wireless edge-server based public area hot-spot network, and UCOM, a multiple-radio wireless LAN system. More recently, Bahl is leading MESH, a community wireless networking and residential broadband access network and contributing to NetHealth, an enterprise and home network inference and diagnostic system. Several of Bahl’s ideas have found their way into Microsoft’s core Windows Operating System product. In addition to building systems, Bahl has authored over 65 scientific papers, 45 issued and pending patent applications, and a book chapter. He has contributed to standards bodies including the IEEE, Bluetooth, HomeRF, and spectrum regulatory bodies. Before joining Microsoft, he was with Digital Equipment Corporation where he shipped several seminal products including JVIDEO, FULLVIDEO, and SLIB, the computer industry’s first hardware and software desktop platforms for audio-video compression and rendering.

Bahl is the founder and Chairman of the ACM Special Interest Group in Mobility (SIGMOBILE); the founder and past Editor-in-Chief of ACM Mobile Computing and Communications Review (1996-2001), and the founder of ACM/USENIX Mobile Systems Conference; he has served on the editorial board of the IEEE Journal on Selected Areas in Communications, and is currently serving on the editorial boards of Elsevier’s Adhoc Networking Journal, Kulwer’s Telecommunications Systems Journal, and ACM’s Wireless Networking Journal. He has served as a guest editor for several IEEE and ACM journals and on networking research-funding panels organized by the National Science Foundation (NSF), the National Research Council (NRC) and European Union’s COST. He has served as the General Chairman and Program Chair of ACM & IEEE conference and serves on the Steering Committee of ACM MobiSys, ACM SenSys and ACM MobiCom. Over the last seven years he has served on the Technical Program Committee of over 40 international conferences and workshops. He is the recipient of ACM SIGMOBILE’s Distinguished Service Award and Digital’s Doctoral Engineering Award. He is an ACM Fellow, an IEEE senior member, and past president of the electrical engineering honor society Eta Kappa Nu-Zeta Pi. Bahl received his Ph. D in Computer Systems Engineering from the University of Massachusetts Amherst.

Session 2: Understanding and Increasing Mesh Capacity

13:15 – 14:45, Wednesday, June 23, 2004

Capacity, Architecture, and Protocols for Wireless Networks


P.R. Kumar | University of Illinois Urbana Champaign


We characterize the capacity of wireless networks, and the corresponding architecture for information transport. Then we describe some new protocols that are designed to improve their performance.


P. R. Kumar is the Franklin Woeltge Professor of Electrical and Computer Engineering, and a Research Professor in the Coordinated Science Laboratory.

Professor Kumar was the recipient of the Donald P. Eckman Award of the American Automatic Control Council in 1985. He is a Fellow of the IEEE.

He has presented plenary lectures at INFORMS Telecommunication Conference, IEEE TENCON, IPSN, WiOpt’03, Mediterranean Conference on Control and Automation, German Open Conference on Probability and Statistics, SIAM Annual Meetings, International Conference on Stochastic Processes in Cochin, IMS Workshop on Applied Probability, Third Annual Semiconductor Manufacturing, Control, and Optimization Workshop, Eleventh Brazilian Automatic Control Congress, IEEE/IAS International Conference on Industrial Automation and Control, , the IEEE Conference on Decision and Control, SIAM Conference on Optimization, and SIAM Conference on Control in the 90’s. His current research interests include wireless networks, protocol development, sensor networks, the convergence of control with communication and computing, wafer fabrication plants, manufacturing systems, and machine learning.

Capacity and Fairness in Multihop Wireless Backhaul Networks


Ashutosh Sabharwal | Rice University


Almost all current wireless networks (3G, WiFi) suffer from a combination of poor coverage, low data rates and high costs. Analyzing the dominant costs of a wireless network, a multihop wireless backhaul architecture emerges as a natural solution for a deployable, high performance wireless network which can also enable demand-based growth. However, the multihop architecture presents several new challenges, such as reduced capacity due to multiple wireless hops, and spatial bias among flows when using off-the-shelf medium access and transport protocols.

In this talk, we will discuss methods to address both capacity- and fairness-related challenges by exploiting the static nature of the wireless network. Our common design philosophy for the new methods is control and adaptation based on feedback information at multiple time-scales. To illustrate, we will discuss the design of a new multiple-antenna physical layer based on fast channel feedback, and a layer-2 protocol to ensure spatial fairness while aiming to maximize network throughput.


Ashutosh Sabharwal received his B.Tech degree in Electrical Engineering from Indian Institute of Technology, New Delhi, India in 1993. He received his M.S. and Ph.D. degrees in Electrical Engineering in 1995 and 1999, respectively, from The Ohio State University, Columbus, OH. He is currently a Research Faculty member at Rice University, Houston, TX, and the Research Director of Center for Multimedia Communications (CMC). His major research focus is wireless networking and information theory.

New Opportunities in Wireless Communication


Ali M. Niknejad | University of California Berkeley


Wireless communication has become an integral part of our lives. We rely on several wireless technologies to provide voice and data at home and on the road. Today there are various competing and complementary standards for voice and data, and new products with wireless capability appear every day. The radio front-end circuitry is a key component in such systems, converting electromagnetic energy incident on the device to bits of data processed by the baseband circuitry. The design and manufacturing of these radios is currently time-consuming and expensive.

In the first part of this talk we will explore utilization of the frequency band at 60 GHz that provides 7 GHz of unlicensed spectrum. We believe that a CMOS radio with multiple antennas can utilize this spectrum for Gb/s wireless LAN connectivity. In the second part of the talk, we will explore new cognitive radio architectures that utilize the spectrum in a more intelligent manner. Agility and dynamic operation allow the radio to operate under extreme conditions without incurring large average power dissipation. These architectures exploit deep sub-micron CMOS that will ultimately result in a dramatic improvement in the level of integration. .


Ali M. Niknejad received the B.S.E.E. degree from the University of California, Los Angeles, in 1994, and his Mastes’s and Ph.D. degrees in electrical engineering from the University of California, Berkeley, in 1997 and 2000. After graduation from Berkeley he spent two years in industry designing analog RF integrated circuits and devices for wireless communication applications. Presently he is an assistant professor in the EECS department at UC Berkeley. He is an associate editor for the Journal of Solid-State Circuits. Prof. Niknejad is a BWRC faculty member and co-directory of the BSIM project.

His current research interests lie within the area of circuits for wireless and broadband communications. This includes implementation of integrated communication systems in silicon, device compact modeling, computer-aided design and optimization of such systems, and numerical techniques in electromagnetics particularly as applied to the analysis and modeling of active and passive devices at microwave frequencies.

Commodity class Phased Array Antenna


Jim Kajiya | Microsoft Research


Mesh networks making use of software-steerable directional antennas enjoy several advantages over those based on omnidirectional antennas. But until recently, the cost of an electronically steered antenna has been too high for widespread adoption. This talk will discuss a design for a very low cost antenna based on a novel RF phase shifting device.

Session 3: Path Selection and Testbed Studies

15:30 – 17:15, Wednesday, June 23, 2004

Stony Brook Mesh Router: Architecting Multi-Radio, Multihop Wireless LANs


Samir Das | Stony Brook University


In this talk, I will describe the Stony Brook Mesh Router Project where we are developing architecture and protocols for multihop wireless LANs. The goal is to use a traditional infrastructure mode, 802.11-based wireless LAN set up, where client devices associate to access points. However, the access points now also act as mesh routers and are connected in a multihop wireless distribution system with routing autonomously managed with a link state-based dynamic routing protocol. The client devices are unaware of the routing infrastructure and do not need any special protocol or set up. Client mobility is handled automatically by link-layer handoffs which in turn triggers appropriate route changes. For improved capacity, the mesh routers are equipped with multiple 802.11-based radio interfaces operating in different bands and different channels within such bands. A distributed channel assignment algorithm assigns channels to interfaces such that the requisite network topology is maintained and throughput is maximized. The talk will describe the architectural choices, routing and channel assignment protocols, and performance results in the initial hardware prototype.


Samir R. Das is currently an Associate Professor in the Computer Science Department at Stony Brook University, SUNY. He received his Ph.D. degree in computer science from the Georgia Institute of Technology, Atlanta, in 1994. His research interests include mobile/wireless networking, performance evaluation and parallel discrete event simulation. Samir Das received the NSF Faculty Early CAREER award in 1998. He has a speaker in the Distinguished Visitor program of the IEEE Computer Society. He has co-chaired the Technical Program Committee for the 2001 ACM MobiHoC Symposium and 2004 ACM MobiCom Conference. He is also on the editorial board of the Ad Hoc Networks Journal.

Self-Organizing Hierarchical Routing for Scalable Ad Hoc Networking


David B. Johnson | Rice University


As devices with wireless networking become more pervasive, mobile ad hoc networks are becoming increasingly important, motivating the development of potentially very large ad hoc networks. The Safari project at Rice University is developing a scalable ad hoc networking architecture based on a self-organizing network hierarcy and scalable ad hoc network routing, providing self-organizing network services and integration with traditional Internet infractructure and services where available. Safari leverages and integrates research in both ad hoc networking and peer-to-peer networking. In this talk, I will describe the design and initial evaluation of the network organization and routing components of the Safari architecutre. Our self-organizing network hierarchy formation protocol recursively forms the nodes of the ad hoc network into an adaptive, proximity-based hierarchy of cells. Utilizing this hierarchy, the routing protocol within Safari is a hybrid of proactive and reactive routing that has very low, scalable overhead. We have evaluated this design through analysis and simulations, under increasing network size, increasing fraction of mobile nodes, and increasing offered traffic load. Our analysis is well matched by our simulations, and our results demonstrate the protocol’s scalability.


David B. Johnson is an Associate Professor of Computer Science and Electrical and Computer Engineering at Rice University. Prior to joining the faculty at Rice in 2000, he was an Associate Professor of Computer Science at Carnegie Mellon University, where he had been on the faculty for eight years. Professor Johnson is leading the Monarch Project, developing adaptive networking protocols and architectures to allow truly seamless wireless and mobile networking. He has also been very active for more than 10 years in the Internet Engineering Task Force (IETF), the principal protocol standards development body for the Internet, were he was one of the main designers of the IETF Mobile IP standards for both IPv4 and IPv6. He was the General Chair for MobiCom 2003 and Program Chair for MobiHoc 2002 and MobiCom 1997, has served as a member of the Technical Program Committee for over 30 international conferences and workshops, and has been an editor for several international journals. He is currently an Executive Committee member and the Treasurer for ACM SIGMOBILE, the Special Interest Group on Mobility of Systems, Users, Data, and Computing, and is a member of the ACM, IEEE, IEEE Computer Society, IEEE Communications Society, USENIX, and Sigma Xi.



Robert Morris | Massachusetts Institute of Technology


Robert Morris is an Associate Professor in MIT’s EECS department and a member of the Laboratory for Computer Science. Along with his students, he is building data networking infrastructure that’s easy to configure and control. The Click toolkit, for example, brings a new level of flexibility to network configuration by viewing routers as compositions of packet processing modules. The Grid routing protocol lets collections of radio-equipped nodes automatically configure their own cooperative network, without relying on any pre-installed infrastructure; Roofnet is an experimental deployment of Grid. The Resilient Overlay Networks project allows end-system control over Internet routing, so that applications can choose their own tradeoffs among qualities such as delay, bandwidth, and reliability. Chord and DHash provide a peer-to-peer distributed data lookup and storage system, which Ivy uses to build a shared read/write file system. (Links to all these projects are included on Robert’s home page). Before joining MIT, Robert helped design and build an ARPA-funded ATM switch with per-circuit hop-by-hop flow control. He led a mobile communication project which won a best student paper award from USENIX and he co-founded Viaweb, an e-commerce hosting service. He received his PhD from Harvard University for work on modeling and controlling networks with a large numbers of competing connections.

Distributed Monitoring of Mesh Networks


Elizabeth Belding-Royer | University of California Santa Barabara


Network monitoring enable operators to gain value insight into network behavior, usage and performance. With the advent of small form-factor devices, falling prices, and robust protocol implementations, mesh networks are witnessing widespread deployment. The monitoring of such networks is crucial for their robust operation. In this talk, we will describe Damon, a Distributed Architecture for Monitoring Mobile Networks. Damon relies on agents within the network to actively monitor network behavior and send this information to data repositories. Damon’s generic architecture supports the monitoring of any protocol, device, or network parameter. As proof-of-concept, we have implemented Damon agents that collect statistics about data traffic and the Ad hoc On-demand Distance Vector (AODV) routing protocol. We have utilized our implementation to monitor an ad hoc network at the 58th Internet Engineering Task Force (IETF) meeting held in Minneapolis, MN. In this talk, we describe the architecture of Damon and report on the performance of the IETF network based on monitoring information collected by Damon.


Elizabeth M. Belding-Royer is an Assistant Professor in the Department of Computer Science at the University of California, Santa Barbara. She completed her Ph.D. in Electrical and Computer Engineering at UC Santa Barbara in 2000. Elizabeth’s research focuses on mobile networking, specifically routing protocols, multimedia, monitoring, and advanced service support. Elizabeth is the author of numerous papers related to ad hoc networking and has served on many program committees for networking conferences. Elizabeth is currently the co-chair of the IRTF Ad hoc Network Scalability (ANS) Research Group and is also on the editorial board for the Elsevier Science Ad hoc Networks Journal, as well as for Mobile Computing and Communications Review (MC2R). Elizabeth is also the recipient of a 2002 Technology Review 100 award, awarded to the world’s top young investigators. She a member of the IEEE, IEEE Communications Society, ACM, and ACM SIGMOBILE.

Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks


Richard Draves | Microsoft Research


We present a new protocol for routing in multi-radio, multi-hop wireless networks. Our protocol, Multi-Radio Link-Quality Source Routing, is designed for wireless networks with stationary nodes, where each node is equipped with multiple independent radios.

The goal of the protocol is to choose a high-throughput path between a source and a destination. Our protocol assigns a weight to each individual link, and then combines the link metrics into a path metric that explicitly accounts for the interference among links that use the same channel. The path metric calculation can be tuned to either maximize throughput of the given flow or to minimize its impact on other flows.

We studied the performance of our protocol by implementing it in a wireless testbed consisting of 23 nodes, each equipped with two 802.11 wireless cards. We used combinations of 802.11a, 802.11b and 802.11g radios in each node to explore the performance of our protocol.

We find that our protocol significantly improves throughput by judicious use of a second radio. We also show that our protocol significantly outperforms previously-proposed routing protocols in a multi-radio environment.


As a Senior Researcher at Microsoft Research in Redmond, Richard Draves leads the Systems and Networking research group. Rich’s group works in the areas of distributed systems, operating systems, and computer networking. Most recently Rich has been working on mesh networking. Previously Rich worked on IPv6 for five years, first developing a prototype IPv6 network stack and working with the IETF on IPv6 standards and then working with Windows Networking to ship the stack in Windows XP, .NET Server, and CE .NET.

Rich joined Microsoft in June 1992 from graduate school as one of the early members of Microsoft Research. Way back before the Internet tidal wave, Rich worked for a year as a development lead in Microsoft’s ITV organization, productizing his research work with the MMOSA operating system. Rich holds a PhD in Computer Science from Carnegie Mellon and a Master of Computer Science and Bachelors of Mathematics from Harvard. He was a Fannie and John Hertz Foundation Fellow and is a past member of the Defense Science Study Group. In his spare time, Rich enjoys mountain climbing. In a recent trip to the Alps, he summitted Mt Blanc, the Matterhorn, and assorted other 4000m peaks. Rich also enjoys skiing, windsurfing, table tennis, contract bridge, and spending time with his wife and two young children.

Session 4: Self Management and Security

17:30 – 19:00, Wednesday, June 23, 2004

Security Challenges for Mesh Networks


Jean-Pierre Hubaux | Ecole Polytechnique Federale De Lausanne (EPFL)


Mesh networks raise a number of security concerns, and it is of crucial importance to design efficient protection mechanisms. In this talk, we will address some of the major threats, including greedy behavior exploiting the vulnerabilities of the MAC layer, location-based attacks, and lack of cooperation between the nodes. For each of them, we will discuss appropriate (published and unpublished) counter-measures.


Jean-Pierre Hubaux joined the faculty of EPFL in 1990; he was promoted to full professor in 1996. His research activity is focused on mobile networking and computing, with a special interest in fully self-organized wireless ad hoc networks. In particular, he has performed research on cooperation aspects, security, power efficiency, and distributed algorithms for ad hoc and sensor networks.

During the last few years, he has been strongly involved in the definition and launching phases of a new National Competence Center in Research named “Mobile Information and Communication Systems” (NCCR/MICS), see Terminodes. Within his first year at EPFL, he defined the first curriculum in Communication Systems. From October 1999 until September 2001, he was the first chairman of the Communication Systems Department.

He served as the general chair for the Third ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2002), held on the EPFL campus. He is an Associate Editor of IEEE Transactions on Mobile Computing and of the Elsevier Journal on Ad Hoc Networks.

He has held visiting positions at the IBM T.J. Watson Research Center and at the University of California at Berkeley.

In a former life, he spent 10 years in France with Alcatel, where he was involved in R&D activities, mostly in the area of switching systems architecture and software.

An early beneficiary of European integration, he was born in Belgium, but spent most of his childhood and youth in Northern Italy. He received his laurea/Dr-Eng. degree from Politecnico di Milano.

Encouraging Cooperation in Multi-Hop Wireless Networks


David Wetherall | University of Washington


In this talk, I will describe a systems effort we have started in the area of multi-hop wireless networks. I will focus on one of the first problems we have looked at: how to encourage cooperative routing and forwarding when nodes that are controlled by different parties come together to form a network. These nodes compete for scarce bandwidth and energy resources, and it is simple for some of them to cheat by avoiding packet forwarding. Existing routing protocols assume this will not happen but have no mechanisms to encourage cooperation or detect cheating if it occurs. Our solution to this problem, CATCH, uses a novel technique based on anonymous messages. Compared to earlier work, CATCH aims to significantly increase the difficulty of cheating without being caught when there is a backdrop of cooperation, rather than preclude it in a world where all nodes are selfish. The benefit of this formulation is that we are able to design CATCH to impose minimal requirements and overheads on the rest of the system and be broadly applicable across routing protocols. We have built and evaluated CATCH on an in-building 802.11 testbed as well as via simulation.


David Wetherall is an Assistant Professor in the Department of Computer Science and Engineering at the University of Washington. He joined the faculty in 1999 after receiving his Ph.D. in computer science from MIT. His thesis research pioneered active networks, an architecture in which new network services can be introduced rapidly using mobile code. He received his B.E. in electrical engineering from the University of Western Australia in 1989. Wetherall received an NSF CAREER award in 2002 and became a Sloan Fellow in 2004. His research interests are focused on how to best design network protocols and distributed systems, especially robustness, understanding system operation via measurement, and support for evolution.



Stefan Savage | University of California San Diego


Stefan Savage is an Assistant Professor in the Computer Science and Engineering Department at U.C. San Diego. He received his PhD in 2001 from the University of Washington and previously was a research staff member at Carnegie Mellon University. In 2004, he was named a Sloan fellow. Stefan’s research interests are both broad and trendy: he used to focus on operating systems issues, only to find himself identified as a networking researcher, but since embracing networking he’s been labeled a computer security person. In reality, Stefan is a dabbler — learning enough to make trouble for others. When not visiting workshops, he attends committees and participates in study groups. He is slowly learning how to say “no” with increased frequency.

Troubleshooting a Wireless Multihop Mesh Network


Lili Qiu | Microsoft Research


Effective network troubleshooting is critical for maintaining efficient and reliable network operations. Troubleshooting is especially challenging in multi-hop wireless networks, because the behavior of such networks depends on complicated interactions among various factors that are often dynamic and unpredictable. In this talk, we discuss a new direction for research on fault diagnosis and management in wireless networks. We apply our approach to diagnose performance problems caused by packet dropping, link congestion, MAC misbehavior, and external noise. In addition, we will show that our approach can be used to evaluate alternative network configurations to improve network performance. Our framework is general enough in that it can be applied to diagnosing faults in infrastructure wireless and wireline networks.


Lili Qiu is a researcher at System & Networking Group in Microsoft Research. Her research interests are wireless networks, overlay networks, network measurement, and Web performance. She received MS and PhD degrees in computer science from Cornell University in 1999 and 2001, respectively.

Posters & Demos

Mesh Monitor and Diagnostic Tool

The Venice team and Microsoft Research have developed a mesh monitor and diagnostic tool on the Windows XP platform. The tool comprises two components: a data collection agent and a console. To ease configuration and maintenance, we use peer-to-peer framework for generating and consuming management data in a mesh network. Every mesh node running an agent feeds data into the P2P transport; any mesh node running a console automatically receive data from the different agents to construct a comprehensive view of the network topology and provide network information at various protocol layers. We also demonstrate the capability of detecting network congestion and random packet dropping using the tool.

Presenter: Ananth Rao

Ananth Rao is a PhD student at UC Berkeley, working under the advice of Ion Stoica. His research interests focus on wireless networking.

Preview of Native WiFi

Native WiFi is a wireless LAN framework that incorporates the IEEE 802.11 upper MAC functionality, lower MAC and PHY management and additional value adds in the Windows Operating System. The components of Native WiFi include: (1) a Native WiFi Mobile Station (STA), which can either be in infrastructure or ad hoc mode, and (2) a Native WiFi Access Point (AP), which is always in a infrastructure mode.

Native WiFi provides a unified infrastructure that allows for dynamic AP or STA configuration as long as the vendor provided thin miniport driver and hardware supports Native WiFi interfaces. The switching between AP to STA mode and vice-versa is handled via a quick software reset.

Native WiFi is an effort to effectively drive WiFi ubiquity and accelerate WiFi innovation on Windows. Further more it is targeted to improve WiFi end user experience, lower WiFi device and infrastructure deployments costs, and provide richer differentiated functionality in Windows by enhancing features like security, diagnostics, power management, roaming, load balancing, QoS and location awareness.

Presenters: Hui Shen, Jiandong Ruan

Hui Shen has worked with Microsoft since 2001 in networking areas, including Native WiFi, wireless network configuration and security, network diagnostics, and performance. He received a M.S. in Computer Science from Washington University St. Louis in 2001 and a Master in Computer Engineering from Chinese Academy of Sciences in 1999. He received his B.S. in Computer Science from Wuhan University, China in 1996

Jiandong Ruan has worked with Microsoft since 2000 in networking areas, including native WiFi, DHCP, NetBT and IPsec. He received a M.S. in Computer Science from Peking University in 1996 and a B.S in Chemical Engineering from Tsinghua University in 1993.

MultiNet: Connecting to Multiple Wireless Networks using a Single Radio

There are a number of scenarios where it is desirable to have a wireless device connect to multiple networks simultaneously. Currently, this is possible only by using multiple wireless network cards in the device. Unfortunately, using multiple wireless cards causes excessive energy drain and consequent reduction of lifetime in battery operated devices. In this paper, we propose a software based approach, called MultiNet, which facilitates simultaneous connections to multiple networks by virtualizing a single wireless card. The wireless card is virtualized by introducing an intermediate layer below IP, which continuously switches the card across multiple networks. The goal of the switching algorithm is to be transparent to the user who sees her machine as being connected to multiple networks. Our MultiNet system has been operational for over twelve months, it is agnostic of the upper layer protocols, and works well over popular IEEE 802.11 wireless LAN cards.

Presenter: Ranveer Chandra

Ranveer Chandra is a PhD student in Computer Science at Cornell University. His research interests include wireless networking and distributed systems. He has received his B.Tech. in Computer Science and Engineering from IIT Kharagpur, and his M.S. in Computer Science from Cornell University. During the course of his PhD he has received the Microsoft Research Graduate Fellowship, and the Sage Fellowship for academic excellence at Cornell University.

SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Networks

Capacity improvement is one of the principal challenges in wireless networking. We present a link-layer protocol called Slotted Seeded Channel Hopping, or SSCH, for increasing the capacity of an IEEE 802.11 network by exploiting frequency diversity. SSCH can be implemented in software over an IEEE 802.11-compliant wireless card. Each node using SSCH switches across channels in such a manner that nodes desiring to communicate overlap, while disjoint communications do not overlap, and hence do not interfere with each other. To achieve this, SSCH uses a novel scheme for distributed rendezvous and synchronization. Simulation results show that SSCH significantly increases network capacity in several multi-hop and single-hop wireless networking scenarios.

Presenter: Ranveer Chandra, John Dunagan

Ranveer Chandra is a PhD student in Computer Science at Cornell University. (see above)

John Dunagan received both his BS and PhD from MIT. His career at Microsoft Research has spanned the Theory Group, the Systems and Networking Group, and most recently the Systems Management Group. His current research is focused on improving the manageability of today’s deployed systems.

Longhorn Location Platform

The Location Platform is a new feature in the future Windows Operating System, code named Longhorn. The platform includes a Windows system service that provides applications with the physical location of the computer. It is built with several levels of extensibility including: (1) a location schema, which can be extended to cover any representation of a physical location, and (2) a plugin layer that IHVs and ISVs can build upon in order to inject location data into the service and thus to extend the capabilities of the location determination process.

We are going to showcase the value of the Location platform in a classic roaming scenario: moving between Home and Office locations.

Presenters: Tracey Yao and Florin Teodorescu

Tracey Yao is a Program Manager in the Windows Networking Product Division. Her current projects include the Longhorn location service and Network location awareness. She recieved a BSc Honors in Mathematics from Victoria University of Wellington, New Zealand in 2001 and a BSc. in Computer Science also from the Victoria University of Wellington, New Zealand in 2000

Florin Teodorescu: Graduated from Politehnical University of Bucharest, Romania in 1993. He received a M.S. from ENSIMAG France (Ecole Nationale Suprieure dInformatique et de Mathmatiques Appliques de Grenoble) in 1994. His research interested include performance evaluation and deterministic re-execution of distributed programs. He has been working for Microsoft since 1998 in various projects including network management, name resolution and more recently wireless networking and location.

Quality Windows Audio Video Experience (qWave)

We show an integrated set of features for network QoS on Wireless 802.11 networks to support distributed audio-video scenarios. Our system includes host and client components designed to offer admission control, network monitoring and application adaptation for multiple high definitions streams simultaneously sharing home IP networks, especially wireless IEEE 802.11 networks.

Presenters: Tarek Elabbady

Tarek Elabbady is a lead program manager with Windows Networking group. He received his PhD from Purdue University in 1994 in electrical engineering. Hejoined Microsoft in 2000 to focus on Audio Video Home networking related initiatives. Tarek has co-authored several patents in the content sharing/access over IP home networks. He is currently managing a project to deliver networking technologies supporting distributed AV scenarios in the next release of Windows.

Investigating Outdoor 802.11 Performance

We present an investigation into the performance of 802.11 when deployed in outdoor long range environments such as found in community network projects. We have studied the performance of the MAC through simulation and have deployed monitors in an outdoor production network in the Cambridge area. Our results highlight the impact of the hidden node problem in these networks when directional antennae are employed to increase range. As a solution we propose a simple modification to the 802.11 DCF protocol that improves throughput and fairness.

Presenter: Neil Stratford

Neil Stratford is a Researcher in the Networks & Performance group at Microsoft Research Cambridge. His research interests are in the area of improving wireless quality of service, bandwidth management and multiservice operating system resource management.

Securing Routing in Open Networks Using Secure Traceroute

We consider the threat imposed on network routing in “open” networks such as community wireless networks. The key characteristic of such networks is that it is relatively easy for users (and attackers) to add routers, establish (possibly wireless) links, and advertise routes. We argue that the traditional focus on securing the routing protocol is insufficient to address the threats arising in this environment. It is also important to secure packet forwarding. To this end, we apply a secure traceroute protocol to detect and localize faulty packet forwarding, which can aid problem resolution either via automatic rerouting or via human action. We present a security analysis of the protocol, discuss our implementation of it in a community wireless network testbed, and show that secure traceroute imposes a negligible overhead on performance.

Presenter: Venkat Padmanabhan

Venkat Padmanabhan is a Researcher in the Systems and Networking group at Microsoft Research. His research interests include wide-area and wireless networking, Internet performance, and mobile computing. His recent work has focused on peer-to-peer content distribution, wireless mesh networks, and network measurement & inference. Venkat serves on the editorial boards of the IEEE/ACM ToN and the IEEE TMC journals, is Program Co-Chair for ACM NOSSDAV 2004, was Tutorials Co-Chair for ACM Mobicom 2000, and has served on the program committees of several conferences including Sigcomm, Mobicom, Infocom, and Sigmetrics. He also holds affiliate faculty appointments in the CS and EE departments at the University of Washington, where he has taught and served on student thesis committees.

Summit Photos