Asymmetric Wireless Networking
| Introduction | Future Plans
Performance Analysis Experiments |
|
Asymmetric Wireless Networking
|
When I arrived at Carnegie Mellon in January, 1994, I learned that some graduate students had established a high-speed wireless network connecting their homes in Oakland with the university campus. I decided, "I've got to have that." One of the students, Tom Warfel, offered to set up a connection for me if I would make a contribution to W3VC, the Carnegie Tech Radio Club, and help with the work.
I had no idea how much work lay ahead of us. Tom's plan was to replace the hardware that he already had in place with an "industrial strength" installation, including my new connection, that would last for ten years. Much of the work went into providing adequate protection from lightning strikes. On the campus end, the antennas are mounted on the tower above Hammerschlag Hall. This tower is the highest point on campus, and it looks out over a cliff on one side, so lightning is a real threat. I certainly didn't want to be remembered as the faculty member who directed a lighting strike into the campus internet! Incidentally, there's a beautiful lighted poster advertising Carnegie Mellon on display at the airport. It shows the Hammerschlag tower lit up at night with the moon in the background. Sadly, they've airbrushed my antennas out of the picture! The photograph of the tower on Carnegie Mellon identification cards seems to have been taken before the antennas went up.
 |
In the end we spliced three layers of lightning arrestors into the cables leading from the antennas down to the computers in the W3VC "shack" on the fourth floor of Hammerschlag Hall. To reduce signal attenuation, we used thick and inflexible "hardline" coaxial cables. This made routing the cables from the tower down to the shack difficult because the cables had to pass through a narrow shaft approximately 75 feet long with a ninety-degree turn at the bottom. We began by dropping a string down the shaft, then pulled down a wire, then a heavier wire, and finally the actual cables. It took so much effort to reach the point where we could route a single cable that we decided to route as many as we could fit in the shaft: four. Since each cable was spliced in three places, we had to solder a total of 24 high-quality connectors to the ends of the cables. I hadn't done this before, and it still takes me half an hour per connector.
 |
At home I placed a directional antenna on a tripod inside a room on the third floor and pointed it towards campus. The antennas were driven by off-the-shelf WaveLAN brand wireless ethernet transceivers. This product implements 2 megabits/sec (mb/s) wireless ethernet using a 915MHz spread-spectrum signal (902MHz - 928MHz). Operating at such a high frequency usually requires clear line-of-site between the antennas on each end of a connection; 915MHz corresponds to a wavelength of only 33cm. I can't see Hammerschlag from my house, but somehow it works anyway!
We turned the new system on, and were gratified to see that it worked. I was relieved, because the cost of the project had ballooned from an original estimate of about $2000 to more than $8000. (But it's better to err on the side of safety.) I had intended to pay for the materials with start up money that the department had provided when I arrived at Carnegie Mellon, but I didn't have enough. Satya generously offered to cover half of the expense.
Much to my dismay, within a few weeks, the performance of this system began to degrade. This coincided with the deployment of the "Wireless Andrew" network on campus. Unfortunately for me, the designers of Wireless Andrew had chosen to use the exact same wireless networking product. A set of repeater stations were placed all over campus, and soon laptop users began roaming the campus with their PCMCIA (PC Card) WaveLAN transceivers. As a consequence, there was suddenly a lot more radio-frequency noise on campus. The repeater stations and the mobile transceivers use short-range omni-directional antennas. Because they are so much closer to my receiver on the campus end, however, the faint signals arriving from my home in Shadyside approximately one mile away can not be heard when a transmission takes place simultaneously on campus. At the other end of my connection, the situtation is different. There is not much 915MHz noise in Shadyside, so packets transmitted from campus to home are only very rarely lost.
Normally the WaveLAN product uses a "carrier sense multiple access/collision avoidance" (CSMA/CA) media access mechanism to reduce the likelyhood of simultaneous conflicting transmissions. The idea is that the WaveLAN transceiver listens for other transmissions before making its own transmission. Once the coast is clear, it then waits for a randomly chosen additional amount of time, and then makes its transmission. This differs from the carrier sense multiple access/collision detection (CSMA/CD) mechanism used by "wired" ethernet in one important respect: an ethernet transceiver can detect a collision with its own transmission, while WaveLAN transceivers cannot. The reason for this difference is that once a WaveLAN transceiver begins a transmission, its own signal is perceived as so strong relative to that of any remote transmitters that a collision cannot be detected. The WaveLAN CSMA/CA protocol works well when all transceivers have roughly equal access to the shared 915MHz "medium", e.g., when all of the transceivers are located within the same building. But it doesn't work well when some signals are so weak that they can't be detected by all parties sharing the medium. The transmissions traveling from my home to campus could be picked up by the directional antenna mounted above Hammerschlag Hall, but they were too weak to be detected by the omnidirectional antennas used by the Wireless Andrew network. (An interesting fact about antennas is that they are almost always symmetric, i.e., if an antenna focuses energy in one direction during a transmission, providing "gain" in that direction over an omnidirectional transmission, then it will also provide the same gain when receiving a transmission from that direction.) As a result, the Wireless Andrew transceivers went ahead with their transmissions happily oblivious to the fact that they were colliding with mine.
In my network the standard IP routing protocol is layered above the wireless ethernet, and the TCP protocol is layered above IP. The TCP protocol includes an acknowledgement mechanism to ensure that all packets are eventually delivered from sender to receiver. The protocol does not work well, however, when there are many packet losses. TCP interprets the loss of packets as a sign that there is severe congestion in the network, a rare but serious problem. Rather than resending a lost packet right away, it waits for a random amount of time before sending another copy. With each loss, the expected amount of time between retransmissions grows by a constant factor. This approach is called exponential backoff. Once packet losses approach 10%, a typical TCP implementation backs off so much that it effectively shuts down altogether. Exponential backoff makes sense when all parties employ the same mechanism and have equal access to the shared transmission medium, but it's not very fair when only one party is losing its packets.
My first approach to solving this problem was to tinker with the software. I decided that I would implement my own acknowledgements mechanism by adding a networking layer between TCP and IP. My intent was to moderate the exponential backoff mechanism invoked by TCP when packets are lost. Tom Warfel has passed on to me a DOS-based program (with source) called "NETRoute-PC" that had been written by a student at Carnegie Mellon named William Kish. This program turns a PC running DOS into an internet router node. It communicates with network interface cards using standard DOS packet drivers, the same packet drivers that the FTP Software brand "PCTCP" TCP/IP stack uses.
I began to experiment with the software. I was in the midst of a typical hectic spring semester (teaching 15-211), and didn't have much time to devote to my hobby. So each week I wouldn't get started until 4pm on Friday afternoon. Much to my annoyance, the CS network went down three weeks in a row just as I was beginning to play with the router. Like everyone else in the department, I would go home in disgust soon after the network crashed. The network gurus had trouble finding the problem until one Friday night when I forget to turn the router off before going home. When I arrived on Monday, the machine had been unplugged, and there was a terse message taped to the monitor. I was the one crashing the network! I knew very little about TCP/IP at the time, and had been plugging my router, which thought that it was a machine on the ECE network (in Hammerschlag Hall), into the CS network. The router then started to advertise that it was the gateway to addresses in the ECE network. Traffic for ECE machines would start to arrive, and the router would forward it who-knows-where, causing loops in the routing tables. After this fiasco, I had to agree not to plug the router into the CS network, and I made an offering of a six-pack of Sam Adams to appease the network demi-gods who had been taking flack for my transgressions.
It took a long time for me to implement my new acknowledgements mechanism. My experience has been that nothing comes easy when trying to get real hardware to perform a real job. The first sign of this came on the day that I started working on the router. As I was entering my office, I dropped the case housing the router PC, blowing the front panel off of the case and bending the frame. I killed numerous mice (the electrical variety) with static electricity. I learned that modems overheat more easily than PCs. I dealt with birds. We painted the antennas above Hammerschlag hall black so that after an ice storm the ice would melt more quickly in the sun. (We've since had a few ice storms, and the antennas don't work when covered in ice.) Birds began to rest on the antennas, persumably because the black paint keeps their feet warm. The birds don't interfere with the radio signals too much, but their weight can cause the antennas to droop! W3VC was evicted from their shack for nearly a year as repairs were made to the tower and roof of Hammerschlag Hall. The repairs were a welcome relief, because plaster had been falling from the ceiling onto all of the equipment in the room for years. I was determined to keep the router up and running through the repairs, so I set it up in the ECE graduate student lounge across the hall, and ran cables between the two rooms through open windows. One day someone had misplaced the radio club's key to the ECE lounge, and I wanted to make an adjustment to the router, so I let myself in through the window. I startled a campus police officer who was sitting in the room by himself in the dark! Needless to say, he gave me the third-degree. But I managed to convince him that I was a mad scientist/professor without even showing him my ID, and he let me go. At one point a construction tarp broke free and wrapped itself around my antennas. I cut away as much as I could reach with scissors, but a small piece was left hanging from the end of the upper antenna. You can see this piece of the tarp in the picture of me holding the antenna mast above Hammerschlag Hall. Eventually a tall student in my course 15-299 "Mathematical Foundations of Computer Science" (perhaps angling for some extra credit) stood with one foot on each of two opposite guard rails and cut the last piece off while I held his belt. Even worse, as part of a class project, an art student tethered a big red helium balloon to the top of the tower on one of the windiest days of the year. Some of the balloon's mooring lines broke free, and the balloon smashed several of my antennas.
Over the past few years I've had a lot of help with this project. Tom Warfel designed the network, ordered the materials, and helped to put everything in place. Todd Turco helped me implement a prototype of the acknowledgements mechanism. Chris Hobbs made further enhancements to the router, and helped conduct some experiments to measure the impact of asymmetry on the performance of the TCP protocol. Matt Kurtz kept the network running smoothly and, with Chris, helped to compile traces of network traffic in a variety of contexts. (What we found was that independent of the underlying networking technology, network usage by individual IP hosts is typically quite asymmetric. Nearly all hosts either receive a lot more data than they send, or send a lot more than they receive.) George Economou has been helping with the the Shadyside base station (see below) and with creating the web pages concerning this project. Joe O'Sullivan helped configure Steve Week's Linux machine so that it could talk to my router (see below). Finally, Claudson Bornstein helped to solve dozens and dozens of small problems that have cropped up over the years.
Eventually I got the new acknowledgements mechanism up and running. I learned that debugging network routing code is not an easy thing to do. To start with, the code is typically running on more than one machine, which makes repeating and isolating errors tricky. The code interacts with device drivers, which aren't always reliable, and (in DOS anyway) have the capacity to crash the system. Finally, if a bug goes undetected until after the code is installed on two machines located over a mile apart, shuttling back and forth to figure out what's wrong is a real pain! Throughout this ordeal, my (unappreciative) graduate students joked that it would have taken less time for me to hand carry every packet of data that the network delivered between my home and school.
The new acknowledgements mechanism made the network usuable again for a short time. The main feature of the mechanism was that it moderated the maximum backoff time so that it never exceed a tenth of a second. (I've been told, however, that even this relatively benign violation of networking etiquette is considered quite rude.) Unfortunately, as Wireless Andrew attracted more and more users, performance continued to degrade. My goal was to be able to run an X server at home so that I could keep just one copy all of my files on the workstation in my office on campus, and log in to that machine remotely (as I am right now). But the keyboard response became sluggish, with delays of over a second occurring frequently. In my experience any delay over 100 milliseconds (ms) is noticable to the user. To add insult to injury, the University of Pittsburgh began to use a 915MHz paging system for its medical school residents, which interfered with my network as well as with Wireless Andrew.
Finally I abandoned the idea of using a bidirectional wireless connection between my home and school. Instead, I decided to use a phone line to carry packets from home to school. I reasoned that most of the traffic carried by the network would be graphical images sent from the machine in my office to the X server at home. I now run a web browser at home as well. In the opposite direction, most of the traffic consists of keystrokes, acknowledgements of packets sent from school, and requests to download web documents. I modified the router so that it understood that two IP nodes could be connected by two separate, opposite, and asymmetric communication channels. Building on top of the router's acknowledgements mechanism, the router now has the capacity to adaptively decide whether to send packets from home to school using the radio transmitter or the modem, based on the percentage of packets sent using the transmitter that are successfully received at the campus end. Fortunately, running the SLIP (serial line IP) protocol over a standard 33.6kb/s modem to carry packets from home to campus has proven adequate to support most of the tasks that I envisioned carrying out at home when I embarked on this project.
 |
At the time of this writing (June 1998), three student homes in Oakland have bidirectional wireless network connections, and my home in Shadyside has an asymmetric connection. Over the past few years three other sites in Oakland that have been connected with bidirectional wireless links, and one site in Squirrel Hill with a short-lived asymmetric connection. Perhaps the most interesting connection was that of Steve Weeks, who lived in Shadyside across the street from me. Steve would "piggyback" through my connection using a wireless connection between his house and mine. He was able to run an X server at home much as I did, and did not notice any decrease in network performance. We enjoyed playing Doom over the wireless connection. When Steve moved to New Jersey, he donated his WaveLAN PC Card to the project, which I first used when conducting some experiments and now use to connect a laptop to Wireless Andrew. (Thanks Steve!) The map above shows the past and present network sites in Oakland, Shadyside, and Squirrel Hill. Red dots indicate bidirectional links, while blue dots indicate asymmetric links. Solid lines connecting red and blue dots to the tower on Hammerschlag Hall (the black dot) indicate sites that are currently in operation. If you live very close to any of the current sites in Oakland and have a view of the tower above Hammerschlag Hall, send me email!
 |
One of my plans for the future is to establish a base station in Shadyside so that students living near my home can piggyback through my network connection much as Steve Weeks did. Claudson Bornstein and I attached an 8-foot tall 915MHz omni-directional antenna to a 36-foot extensible pole and mounted it above my house, as shown in the picture above. This was quiet an ordeal, and at one point I had to wrap ropes around Claudson to attach him to the house while he stood on a ledge. The antenna is attached to a lightning arrestor, and both the pole and the lightning arrestor are connected by a thick wire to an 8-foot long grounding pole that I've driven into the earth behind my house, but I'm still a bit nervous about lightning. Unfortunately, after all of this effort, the antenna did not work well, and we've recently taken the whole thing down to test the components individually.
 |
Most of our experiments were conducted using a four node network arranged in a chain, as shown above. The two end nodes were DECpc 425SL laptops, running NetBSD 1.1. These machines have Intel x486 processors running at 25MHz. Each of these machines made network connections using Intel EtherExpress 595 PCMCIA 10Mb/s ethernet cards. The two machines in the middle ran a DOS-based dedicated router program. The first machine was a desktop with a 25MHz Intel x386 processor, while the second machine was another DECpc 425SL laptop. The deskop was connected to the leftmost node using a 3Com 3c503 ISA-bus ethernet card. The laptop was connected to the rightmost node using a 3Com 3c589 PMCIA 10Mb/s ethernet card. In these experiments, the connection between the two machines in the middle was asymmetric. In the download direction, from left to right, the desktop was connected to the laptop using either another 3Com 3c503 ISA-bus ethernet card, or a 2Mb/s wireless ISA-bus WaveLAN card. In the laptop, the corresponding cards were either another 3Com 3c589 PCMCIA ethernet card, or a 2Mb/s wireless WaveLAN PCMCIA card. In the upload direction, the two middle nodes were connected by a serial line. The laptop used an 8250 serial port to send data upstream, while the desktop received data using a CyperPro 16650 serial port. The desktop was used in these experiments (rather than a fourth laptop) because the 8250 serial port built into these laptops is unable to reliably receive data at 115200 b/s, and crashes the machine when presented with data at this rate. Although the machines involved in these experiments are now out-of-date and rather slow, they are fast enough to drive the ethernet and wireless ethernet cards at speeds approaching peak performance, certainly within a factor of 2.
In these experiments we measured the time to download a 10 MB file using the test program ttcp. We varied the speed of the serial line, which carried TCP acknowledgements, from 1200bps to 115200bps, and measured the actual download performance. In all of these experiments, data was sent on the serial channel using the SLIP protocol, with no form of data or header compression. The SLIP protocol transmits raw IP datagrams across a serial line, using a special byte value to indicate the end of each datagram. If the special byte value is needed in the body of the datagram, then an additional byte with the same value is inserted into the stream so that the special byte value appears twice in succession. The IP datagrams are not encapsulated in any other datagrams, and so there are no datagram headers (e.g., ethernet headers) traveling across the serial line except for IP headers and TCP headers encapsulated inside IP datagrams.
 |
The figure above presents the results of the experiment using a 10Mb/s ethernet downlink. For each setting of the upload speed, the data shows the maximum download performance achieved over 10 trials. For the ethernet data, there was very little deviation in performance across the trials. As a reference point, we also measured the performance of ttcp when the two nodes in the middle were connected by a single ethernet that carried both the upload and download traffic. As a second reference point, we measured the performance when the two NetBSD laptops on the ends of the chain were connected directly using their ethernet cards (avoiding the two middle nodes altogether). These two additional experimental setups are shown in the figure below.
 |
Another set of experiments was conducted using 2Mb/s WaveLAN wireless ethernet for downloading. Again, we measured the impact of varying the upload speed on the download performance. The data is shown in the figure above. For reference points, we also measured the download performance when the two middle nodes were connected using the wireless ethernet in both directions, and when the two NetBSD nodes were connected directly using wireless ethernet. Each data point represents the maximum download performance achieved over 10 trials. In these experiments there were slight variations across the trials due to radio-frequency noise in the experimental environment. To avoid this noise, the experiments were conducted at off-peak usage hours. In all cases at least a majority of the trials yielded a download speed very close to the maximum.
The experiments show that the when the download speed greatly exceeds the upload speed, download performance is roughly proportional to upload speed. This makes sense, since the download speed is limited by the rate at which acknowledgements are delivered upstream. In principle, the TCP kernels running on the NetBSD machines could adjust the size of the sliding window in the download direction, but this implementation of NetBSD imposes a fixed maximum window size on all TCP connections. Eventually, improvements in the upload speed do not yield linear improvements in the download speed. At this point the acknowledgements are keeping up with the download speed. In a file transfer of this size, the download stream consists of large datagrams carrying approximately 1500 bytes of data, while the upload stream should consist of 40-byte datagrams comprised of a 20-byte IP header and a 20-byte TCP header, and no data. Each of the upstream datagrams may acknowledgement several downstream datagrams.
The experiments show that when using the 2Mb/sec wireless ethernet, 95% of peak performance is achieved with an uplink speed of 57.6Kb/sec. This combination of upload and download speed is a convenient ``sweet spot'' for the asymmetric network deployed at Carnegie Mellon. Recall that this network uses 2Mb/sec wireless ethernet to transmit data from campus to home, but an ordinary telephone line to return data (and acknowledgements). Although the maximum upload speed achievable on an ordinary telephone line (using today's V34bis modems) is 33.6Kb/sec, the modems perform on-the-fly compression of the data stream, and typically achieve compression ratios of about 2-to-1. Furthermore, upload performance can be improved by using serial line protocols more sophisticated than SLIP that send shorter datagram headers. Two examples are SLIP with Van Jacobson header compression, and the PPP protocol. This sweet spot should also apply to some ADSL networks. For instance, the ADSL network in the Pittsburgh trial provides a download speed of 1.5Mb/sec, and an upload speed of 64Kb/sec. This upload speed should be sufficient to provide acknowledgements for a single download stream at nearly peak performance.
Another interesting feature of the experimental data is that in the 2Mb/sec wireless ethernet experiments, the download performance achieved using a 115.2Kb/sec serial line to carry acknowledgements actually exceeds the performance achieved when the wireless ethernet is used to carry traffic both downstream and upstream. Although counterintuitive, there are several possible explanations for this phenomenon.
First, using a separate serial line to carry acknowledgements allows data to flow in both directions simultaneously. At 115.2Kb/sec, the serial line is fast enough to provide the downstream with acknowledgments so that it can operate at peak or nearly peak speed. Hence optimum download performance is achieved when all of the wireless ethernet medium is allocated to the downstream.
Second, when the wireless medium is shared by the the downstream and upstream, there may be collisions between transmissions in the two streams. The WaveLAN transceivers implement a Carrier-Sense Multiple Access/Collision Avoidance (CSMA/CA) protocol. In order to make a transmission, a transceiver must wait until it hears no other transmissions. It then waits for an additional randomly-chosen amount of time, and, provided that it hears no new transmissions, begins its own transmission. This protocol is in contrast to the CSMA/Collision Detect protocol used by traditional ethernet. In the CSMA/CD protocol, a transceiver may begin transmitting as soon as all other transmissions cease. If a collision occurs, the transceiver will detect it, and will then wait for a randomly-chosen amount of time before retransmitting. Unlike traditional ethernet, it is not possible for a transceiver to detect a collision between because the effective signal strength of its own transmission is so much greater than that of any other transceiver. Furthermore, the wireless protocol does not provide any acknowledgements mechanism, but instead relies on higher level protocols (in these experiments TCP) to furnish acknowledgments. The net effect is that collisions are more costly in the wireless ethernet, and introducing the possibility of collision has a measurable effect on download performance.
It is interesting to note that the lack of an acknowledgement mechanism in the wireless ethernet protocol does have certain advantages. For example, in the asymmetric network at CMU, bidirectional wireless connections were abandoned because reliable transmission in the upload direction was not possible. Hence, it would not have been possible to provide acknowledgements for frames sent downstream. Because these acknowledgements are not required, reliable transmission is implemented through higher level protocols (TCP), and the acknowledgements used by these protocols are carried by separate media.
Similar results, and all sorts of other interesting experiments are reported in the following paper.
Protocols for Asymmetric Communication
Channels. M. Adler and B. M. Maggs, November, 1997.
Abstract
| Description | Size | Thumbnail |
|---|---|---|
| Bruce standing next to antennas on top of
Hammerschlag antenna1b.jpg (480x640) |
42k | |
| Two antennas on top of Hammerschlag antenna2b.jpg (640x480) |
49k |  |
| Bruce with two antennas on top of Hammerschlag antenna3b.jpg (640x480) |
64k |  |
| An antenna on top of Hammerschlag, pointing towards Oakland antenna4b.jpg (640x480) |
64k |  |
| Photo of the antenna in Bruce's house, with the computer it is
connected to (somewhat blurry) home1b.jpg (640x480) |
39k |  |
| Another photo of the antenna in Bruce's house in Shadyside home2b.jpg (480x640) |
45k |  |
| A picture of the antenna at home and the window it points out of home3b.jpg (640x480) |
51k | |
| A closer view of the antenna at home home4b.jpg (640x480) |
47k |  |
| Lightning arrestors in the W3VC shack in Hammerschlag equip-1-exc.jpg (640x480) |
432k | |
| A picture of the machine in Hammerschlag that handles the wireless
transmission and reception, and integration with the SLIP
lines equip-2-exc.jpg (480x640) |
91k |  |
| Both the machine and the lightning arrestors in the W3VC shack in Hammerschlag equip-3-exc.jpg (640x480) |
456k |  |
| A picture of the base transmitter antenna in Shadyside, from below base1b.jpg (640x480) |
38k |  |
| Another picture of the base transmitter antenna from below base2b.jpg (640x480) |
44k | |
| A photo of the base transmitter antenna in Shadyside from further away base3b.jpg (480x640) |
32k |  |
| A photo of the base transmitter antenna from a below and to
the right base4b.jpg (480x640) |
48k |  |
| A picture of Wean Hall, taken from the tower above Hammerschlag wean-exc.jpg (320x240) |
135k |  |
| A shot of Phipps Conservatory from atop Hammerschlag phipps.jpg (640x480) |
47k |  |
| A view of the CMU quadrangle from atop Hammersclag quad.jpg (640x480) |
48k |  |
| A bird's eye view of Oakland craigst-exc.jpg (320x240) |
127k |  |
| A picture of Bruce spending quality time with his favorite WaveLAN antennas bruce-exc.jpg (480x640) |
86k |  |
