3 Other LANs¶
In the wired era, one could get along quite well with nothing but Ethernet and the occasional long-haul point-to-point link joining different sites. However, there are important alternatives out there. Some, like token ring, are mostly of historical importance; others, like virtual circuits, are of great conceptual importance but – so far – of only modest day-to-day significance.
And then there is wireless. It would be difficult to imagine contemporary laptop networking, let alone mobile devices, without it. In both homes and offices, Wi-Fi connectivity is the norm. Mobile networking is ubiquitous. A return to being tethered by wires is almost unthinkable.
3.1 Virtual Private Networks¶
Suppose you want to connect to your workplace network from home. Your workplace, however, has a security policy that does not allow “outside” IP addresses to access essential internal resources. How do you proceed, without leasing a dedicated telecommunications line to your workplace?
A virtual private network, or VPN, provides a solution; it supports creation of virtual links that join far-flung nodes via the Internet. Your home computer creates an ordinary Internet connection (TCP or UDP) to a workplace VPN server (IP-layer packet encapsulation can also be used, and avoids the timeout problems sometimes created by sending TCP packets within another TCP stream; see 7.13 Mobile IP). Each end of the connection is typically associated with a software-created virtual network interface; each of the two virtual interfaces is assigned an IP address. (Virtual interfaces are not essential; VPNs created with IPsec, 21.11 IPsec, generally omit them.) When a packet is to be sent along the virtual link, it is actually encapsulated and sent along the original Internet connection to the VPN server, wending its way through the commodity Internet; this process is called tunneling. To all intents and purposes, the virtual link behaves like any other physical link.
Tunneled packets are often encrypted as well as encapsulated, though that is a separate issue. One relatively easy-to-implement example of a tunneling mechanism is to treat a TCP home-workplace connection as a serial line and send packets over it back-to-back, using PPP with HDLC; see 220.127.116.11 HDLC and RFC 1661 (though this can lead to the above-mentioned TCP-in-TCP timeout problems).
At the workplace side, the virtual network interface in the VPN server is attached to a router or switch; at the home user’s end, the virtual network interface can now be assigned an internal workplace IP address. The home computer is now, for all intents and purposes, part of the internal workplace network.
In the diagram below, the user’s regular Internet connection is via hardware interface
eth0. A connection is established to Site A’s VPN server; a virtual interface
tun0 is created on the user’s machine which appears to be a direct link to the VPN server. The
tun0 interface is assigned a Site-A IP address. Packets sent via the
tun0 interface in fact travel over the original connection via
eth0 and the Internet.
After the VPN is set up, the home host’s
tun0 interface appears to be locally connected to Site A, and thus the home host is allowed to connect to the private area within Site A. The home host’s forwarding table will be configured so that traffic to Site A’s private addresses is routed via interface
VPNs are also commonly used to connect entire remote offices to headquarters. In this case the remote-office end of the tunnel will be at that office’s local router, and the tunnel will carry traffic for all the workstations in the remote office.
Other applications of VPNs include trying to appear geographically to be at another location, and bypassing firewall rules blocking specific TCP or UDP ports.
To improve security, it is common for the residential (or remote-office) end of the VPN connection to use the VPN connection as the default route for all traffic except that needed to maintain the VPN itself. This may require a so-called host-specific forwarding-table entry at the residential end to allow the packets that carry the VPN tunnel traffic to be routed correctly via
eth0. This routing strategy means that potential intruders cannot access the residential host – and thus the workplace internal network – through the original residential Internet access. A consequence is that if the home worker downloads a large file from a non-workplace site, it will travel first to the workplace, then back out to the Internet via the VPN connection, and finally arrive at the home.
To improve congestion response, IP packets are sometimes marked by routers that are experiencing congestion; see 14.8.2 Explicit Congestion Notification (ECN). If such marking is done to the outer, encapsulating, packet, and the marks are not transferred at the remote endpoint of the VPN to the inner, encapsulated, packet, then the marks are lost. Congestion response may suffer. RFC 6040 spells out a proper re-marking strategy in general; RFC 7296 defines re-marking for IPsec (21.11 IPsec). Older VPN protocols, however, may not support congestion re-marking.
3.2 Carrier Ethernet¶
Carrier Ethernet is a leased-line point-to-point link between two sites, where the subscriber interface at each end of the line looks like Ethernet (in some flavor). The physical path in between sites, however, need not have anything to do with Ethernet; it may be implemented however the carrier wishes. In particular, it will be (or at least appear to be) full-duplex, it will be collision-free, and its length may far exceed the maximum permitted by any IEEE Ethernet standard.
Bandwidth can be purchased in whatever increments the carrier has implemented. The point of carrier Ethernet is to provide a layflooder of abstraction between the customers, who need only install a commodity Ethernet interface, and the provider, who can upgrade the link implementation at will without requiring change at the customer end.
In a sense, carrier Ethernet is similar to the widespread practice of provisioning residential DSL and cable routers with an Ethernet interface for customer interconnection; again, the actual link technologies may not look anything like Ethernet, but the interface will.
A carrier Ethernet connection looks like a virtual VPN link, but runs on top of the provider’s internal network rather than the Internet at large. Carrier Ethernet connections often provide the primary Internet connectivity for one endpoint, unlike Internet VPNs which assume both endpoints already have full Internet connectivity.
3.3 Token Ring¶
A significant part of the previous chapter was devoted to classic Ethernet’s collision mechanism for supporting shared media access. After that, it may come as a surprise that there is a simple multiple-access mechanism that is not only collision-free, but which supports fairness in the sense that if N stations wish to send then each will receive 1/N of the opportunities.
That method is Token Ring. Actual implementations come in several forms, from Fiber-Distributed Data Interface (FDDI) to so-called “IBM Token Ring”. The central idea is that stations are connected in a ring:
Packets will be transmitted in one direction (clockwise in the ring above). Stations in effect forward most packets around the ring, although they can also remove a packet. (It is perhaps more accurate to think of the forwarding as representing the default cable connectivity; non-forwarding represents the station’s momentarily breaking that connectivity.)
When the network is idle, all stations agree to forward a special, small packet known as a token. When a station, say A, wishes to transmit, it must first wait for the token to arrive at A. Instead of forwarding the token, A then transmits its own packet; this travels around the network and is then removed by A. At that point (or in some cases at the point when A finishes transmitting its data packet) A then forwards the token.
In a small ring network, the ring circumference may be a small fraction of one packet. Ring networks become “large” at the point when some packets may be entirely in transit on the ring. Slightly different solutions apply in each case. (It is also possible that the physical ring exists only within the token-ring switch, and that stations are connected to that switch using the usual point-to-point wiring.)
If all stations have packets to send, then we will have something like the following:
- A waits for the token
- A sends a packet
- A sends the token to B
- B sends a packet
- B sends the token to C
- C sends a packet
- C sends the token to D
All stations get an equal number of chances to transmit, and no bandwidth is wasted on collisions. (A station constantly sending smaller packets will send the same number of packets as a station constantly sending larger packets, but the bandwidth will be smaller in proportion to the smaller packet size.)
One problem with token ring is that when stations are powered off it is essential that the packets continue forwarding; this is usually addressed by having the default circuit configuration be to keep the loop closed. Another issue is that some station has to watch out in case the token disappears, or in case a duplicate token appears.
Because of fairness and the lack of collisions, IBM Token Ring was once considered to be the premium LAN mechanism. As such, a premium price was charged (there was also the matter of licensing fees). But due to a combination of lower hardware costs and higher bitrates (even taking collisions into account), Ethernet eventually won out.
There was also a much earlier collision-free hybrid of 10 Mbps Ethernet and Token Ring known as Token Bus: an Ethernet physical network (often linear) was used with a token-ring-like protocol layer above that. Stations were physically connected to the (linear) Ethernet but were assigned identifiers that logically arranged them in a (virtual) ring. Each station had to wait for the token and only then could transmit a packet; after that it would send the token on to the next station in the virtual ring. As with “real” Token Ring, some mechanisms need to be in place to monitor for token loss.
Token Bus Ethernet never caught on. The additional software complexity was no doubt part of the problem, but perhaps the real issue was that it was not necessary.
3.4 Virtual Circuits¶
Before we can get to our final LAN example, ATM, we need to detour briefly through virtual circuits.
Virtual circuits are The Road Not Taken by IP.
Virtual-circuit switching (or routing) is an alternative to datagram switching, which was introduced in Chapter 1. In datagram switching, routers know the next_hop to each destination, and packets are addressed by destination. In virtual-circuit switching, routers know about end-to-end connections, and packets are “addressed” by a connection ID.
Before any packets can be sent, a connection needs to be established first. For that connection, the route is computed and then each link along the path is assigned a connection ID, traditionally called the VCI, for Virtual Circuit Identifier. In most cases, VCIs are only locally unique; that is, the same connection may use a different VCI on each link. The lack of global uniqueness makes VCI allocation much simpler. Although the VCI keeps changing along a path, the VCI can still be thought of as identifying the connection. To send a packet, the host marks the packet with the VCI assigned to the host–router1 link.
Packets arrive at (and depart from) switches via one of several ports, which we will assume are numbered beginning at 0. Switches maintain a connection table indexed by ⟨VCI,port⟩ pairs; unlike a forwarding table, the connection table has a record of every connection through that switch at that particular moment. As a packet arrives, its inbound VCIin and inbound portin are looked up in this table; this yields an outbound ⟨VCIout,portout⟩ pair. The VCI field of the packet is then rewritten to VCIout, and the packet is sent via portout.
Note that typically there is no source address information included in the packet (although the sender can be identified from the connection, which can be identified from the VCI at any point along the connection). Packets are identified by connection, not destination. Any node along the path (including the endpoints) can in principle look up the connection and figure out the endpoints.
Note also that each switch must rewrite the VCI. Datagram switches never rewrite addresses (though they do update hopcount/TTL fields). The advantage to this rewriting is that VCIs need be unique only for a given link, greatly simplifying the naming. Datagram switches also do not make use of a packet’s arrival interface.
As an example, consider the network below. Switch ports are numbered 0,1,2,3. Two paths are drawn in, one from A to F in red and one from B to D in green; each link is labeled with its VCI number in the same color.
We will construct virtual-circuit connections between
- A and F (shown above in red)
- A and E
- A and C
- B and D (shown above in green)
- A and F again (a separate connection)
The following VCIs have been chosen for these connections. The choices are made more or less randomly here, but in accordance with the requirement that they be unique to each link. Because links are generally taken to be bidirectional, a VCI used from S1 to S3 cannot be reused from S3 to S1 until the first connection closes.
- A to F: A──4──S1──6──S2──4──S4──8──S5──5──F; this path goes from S1 to S4 via S2
- A to E: A──5──S1──6──S3──3──S4──8──E; this path goes, for no particular reason, from S1 to S4 via S3, the opposite corner of the square
- A to C: A──6──S1──7──S3──3──C
- B to D: B──4──S3──8──S1──7──S2──8──D
- A to F: A──7──S1──8──S2──5──S4──9──S5──2──F
One may verify that on any one link no two different paths use the same VCI.
We now construct the actual ⟨VCI,port⟩ tables for the switches S1-S4, from the above; the table for S5 is left as an exercise. Note that either the ⟨VCIin,portin⟩ or the ⟨VCIout,portout⟩ can be used as the key; we cannot have the same pair in both the in columns and the out columns. It may help to display the port numbers for each switch, as in the upper numbers in following diagram of the above red connection from A to F (lower numbers are the VCIs):
The namespace for VCIs is small, and compact (eg contiguous). Typically the VCI and port bitfields can be concatenated to produce a ⟨VCI,Port⟩ composite value small enough that it is suitable for use as an array index. VCIs work best as local identifiers. IP addresses, on the other hand, need to be globally unique, and thus are often rather sparsely distributed.
Virtual-circuit switching offers the following advantages:
- connections can get quality-of-service guarantees, because the switches are aware of connections and can reserve capacity at the time the connection is made
- headers are smaller, allowing faster throughput
- headers are small enough to allow efficient support for the very small packet sizes that are optimal for voice connections. ATM packets, for instance, have 48 bytes of data; see below.
Datagram forwarding, on the other hand, offers these advantages:
- Routers have less state information to manage.
- Router crashes and partial connection state loss are not a problem.
- If a router or link is disabled, rerouting is easy and does not affect any connection state. (As mentioned in Chapter 1, this was Paul Baran’s primary concern in his 1962 paper introducing packet switching.)
- Per-connection billing is very difficult.
The last point above may once have been quite important; in the era when the ARPANET was being developed, typical daytime long-distance rates were on the order of $1/minute. It is unlikely that early TCP/IP protocol development would have been as fertile as it was had participants needed to justify per-minute billing costs for every project.
It is certainly possible to do virtual-circuit switching with globally unique VCIs – say the concatenation of source and destination IP addresses and port numbers. The IP-based RSVP protocol (19.6 RSVP) does exactly this. However, the fast-lookup and small-header advantages of a compact namespace are then lost.
Multi-Protocol Label Switching (19.12 Multi-Protocol Label Switching (MPLS)) is another IP-based application of virtual circuits.
Note that virtual-circuit switching does not suffer from the problem of idle channels still consuming resources, which is an issue with circuits using time-division multiplexing (eg shared T1 lines)
3.5 Asynchronous Transfer Mode: ATM¶
ATM is a network mechanism intended to accommodate real-time traffic as well as bulk data transfer. We present ATM here as a LAN layer, for which it is still sometimes used, but it was originally proposed as a replacement for the IP layer as well, and, to an extent, the Transport layer. These broader plans were not greeted with universal enthusiasm within the IETF. When used as a LAN layer, IP packets are transmitted over ATM as in 3.5.1 ATM Segmentation and Reassembly.
A distinctive feature of ATM is its small packet size. ATM has its roots in the telephone industry, and was therefore particularly intended to support voice. A significant source of delay in voice traffic is the packet fill time: at DS0 speeds (64 Kbps), voice data accumulates at 8 bytes/ms. If we are sending 1KB packets, this means voice is delayed by about 1/8 second, meaning in turn that when one person stops speaking, the earliest they can hear the other’s response is 1/4 second later. Slightly smaller levels of voice delay can introduce an annoying echo. Smaller packets reduce the fill time and thus the delay: when voice is sent over IP (VoIP), one common method is to send 160 bytes every 20 ms.
ATM took this small-packet strategy even further: packets have 48 bytes of data, plus 5 bytes of header. Such small packets are often called cells. To manage such a small header, virtual-circuit routing is a necessity. IP packets of such small size would likely consume more than 50% of the bandwidth on headers, if the LAN header were included.
Aside from reduced voice fill-time, other benefits to small cells are reduced store-and-forward delay and minimal queuing delay, at least for high-priority traffic. Prioritizing traffic and giving precedence to high-priority traffic is standard, but high-priority traffic is never allowed to interrupt transmission already begun of a low-priority packet. If you have a high-priority voice cell, and someone else has a 1500-byte packet just started, your cell has to wait about 30 cell times, because 1500 bytes is about 30 cells. However, if their low-priority traffic is instead made up of 30 cells, you have only to wait for their first cell to finish; the delay is 1/30 as much.
ATM also made the decision to require fixed-size cells. The penalty for one partially used cell among many is small. Having a fixed cell size simplifies hardware design, and, in theory, allows it easier to design for parallelism.
Unfortunately, the designers of ATM also chose to mandate no cell reordering. This means cells can use a smaller sequence-number field, but also makes parallel switches much harder to build. A typical parallel switch design might involve distributing incoming cells among any of several input queues; the queues would then handle the VCI lookups in parallel and forward the cells to the appropriate output queues. With such an architecture, avoiding reordering is difficult. It is not clear to what extent the no-reordering decision was related to the later decline of ATM in the marketplace.
ATM cells have 48 bytes of data and a 5-byte header. The header contains up to 28 bits of VCI information, three “type” bits, one cell-loss priority, or CLP, bit, and an 8-bit checksum over the header only. The VCI is divided into 8-12 bits of Virtual Path Identifier and 16 bits of Virtual Channel Identifier, the latter supposedly for customer use to separate out multiple connections between two endpoints. Forwarding is by full switching only, and there is no mechanism for physical (LAN) broadcast.
3.5.1 ATM Segmentation and Reassembly¶
Due to the small packet size, ATM defines its own mechanisms for segmentation and reassembly of larger packets. Thus, individual ATM links in an IP network are quite practical. These mechanisms are called ATM Adaptation Layers, and there are four of them: AALs 1, 2, 3/4 and 5 (AAL 3 and AAL 4 were once separate layers, which merged). AALs 1 and 2 are used only for voice-type traffic; we will not consider them further.
The ATM segmentation-and-reassembly mechanism defined here is intended to apply only to large data; no cells are ever further subdivided. Furthermore, segmentation is always applied at the point where the data enters the network; reassembly is done at exit from the ATM path. IPv4 fragmentation, on the other hand, applies conceptually to IP packets, and may be performed by routers within the network.
For AAL 3/4, we first define a high-level “wrapper” for an IP packet, called the CS-PDU (Convergence Sublayer - Protocol Data Unit). This prefixes 32 bits on the front and another 32 bits (plus padding) on the rear. We then chop this into as many 44-byte chunks as are needed; each chunk goes into a 48-byte ATM payload, along with the following 32 bits worth of additional header/trailer:
- 2-bit type field:
- 10: begin new CS-PDU
- 00: continue CS-PDU
- 01: end of CS-PDU
- 11: single-segment CS-PDU
- 4-bit sequence number, 0-15, good for catching up to 15 dropped cells
- 10-bit MessageID field
- CRC-10 checksum.
We now have a total of 9 bytes of header for 44 bytes of data; this is more than 20% overhead. This did not sit well with the IP-over-ATM community (such as it was), and so AAL 5 was developed.
AAL 5 moved the checksum to the CS-PDU and increased it to 32 bits from 10 bits. The MID field was discarded, as no one used it, anyway (if you wanted to send several different types of messages, you simply created several virtual circuits). A bit from the ATM header was taken over and used to indicate:
- 1: start of new CS-PDU
- 0: continuation of an existing CS-PDU
The CS-PDU is now chopped into 48-byte chunks, which are then used as the entire body of each ATM cell. With 5 bytes of header for 48 bytes of data, overhead is down to 10%. Errors are detected by the CS-PDU CRC-32. This also detects lost cells (impossible with a per-cell CRC!), as we no longer have any cell sequence number.
For both AAL3/4 and AAL5, reassembly is simply a matter of stringing together consecutive cells in order of arrival, starting a new CS-PDU whenever the appropriate bits indicate this. For AAL3/4 the receiver has to strip off the 4-byte AAL3/4 headers; for AAL5 the receiver has to verify the CRC-32 checksum once all cells are received. Different cells from different virtual circuits can be jumbled together on the ATM “backbone”, but on any one virtual circuit the cells from one higher-level packet must be sent one right after the other.
A typical IP packet divides into about 20 cells. For AAL 3/4, this means a total of 200 bits devoted to CRC codes, versus only 32 bits for AAL 5. It might seem that AAL 3/4 would be more reliable because of this, but, paradoxically, it was not! The reason for this is that errors are rare, and so we typically have one or at most two per CS-PDU. Suppose we have only a single error, ie a single cluster of corrupted bits small enough that it is likely confined to a single cell. In AAL 3/4 the CRC-10 checksum will fail to detect that error (that is, the checksum of the corrupted packet will by chance happen to equal the checksum of the original packet) with probability 1/210. The AAL 5 CRC-32 checksum, however, will fail to detect the error with probability 1/232. Even if there are enough errors that two cells are corrupted, the two CRC-10s together will fail to detect the error with probability 1/220; the CRC-32 is better. AAL 3/4 is more reliable only when we have errors in at least four cells, at which point we might do better to switch to an error-correcting code.
Moral: one checksum over the entire message is often better than multiple shorter checksums over parts of the message.
3.6 Adventures in Radioland¶
For the remainder of this chapter we leave wires (and fiber) behind, and contemplate the transmission of packets via radio, freeing nodes from their cable tethers. Wi-fi (3.7 Wi-Fi) and mobile wireless (3.8 WiMAX and LTE) are now ubiquitous. But radio is not quite like wire, and wireless transmission of packets brings several changes.
It’s hard to tap into wired Ethernet, especially if you are locked out of the building. But anyone can receive wireless transmissions, often from a considerable distance. The data breach at TJX Corporation was achieved by attackers parking outside a company building and pointing a directional antenna at it; encryption was used but it was weak (see 21 Security and 21.7.7 Wi-Fi WEP Encryption Failure). Similarly, Internet café visitors generally don’t want other patrons to read their email. Radio communication needs strong encryption.
Ethernet-like collision detection is no longer feasible over radio. This has to do with the relative signal strength of the remote signal at the local transmitter. Along a wire-based Ethernet the remote signal might be as weak as 1/100 of the transmitted signal but that 1% received signal is still detectable during transmission. However, with radio the remote signal might easily be as little as 1/1,000,000 of the transmitted signal (-60 dB), as measured at the transmitting station, and it is simply overwhelmed during transmission.
As a result, wireless protocols must be constructed appropriately. We will look at how Wi-Fi handles this in its most common mode of operation in 3.7.1 Wi-Fi and Collisions. Wi-Fi also supports its PCF mode (3.7.7 Wi-Fi Polling Mode) that involves fewer (but not zero) collisions through the use of central-point polling. Finally, WiMAX and LTE switch from polling to scheduling to further reduce collisions, though the potential for collisions is still inevitable when new stations join the network.
It is also worth pointing out that, while an Ethernet collision affects every station in the physical Ethernet (the “collision domain”), wireless collisions are often local. Two stations can transmit at the same time, but their signals “collide” only in locations where both signals are strong enough. As an example, suppose three stations are arranged linearly, A–C–B, with the A–C and C–B distances just under the maximum effective range. When A and B both transmit there is a collision at C. But when C and B transmit simultaneously, A may receive C’s signal just fine, as B’s is too weak to matter.
3.6.4 Band Width¶
To radio engineers, “band width” means the frequency range used by a signal, not the data transmission rate. No information can be conveyed using a single frequency; even signaling by switching a carrier frequency off and on at a low rate “blurs” the carrier into a band of nonzero width.
In keeping with this we will for the remainder of this chapter use the term “data rate” for what we have previously called “bandwidth”. We will use the terms “channel width” or “width of the frequency band” for the frequency range.
All else being equal, the data rate achievable with a radio signal is proportional to the channel width. The constant of proportionality is limited by the Shannon-Hartley theorem: the maximum data rate divided by the width of the frequency band is log2(1+SNR), where SNR is the signal to noise power ratio. Noise here is assumed to have a specific statistical form known as Gaussian white noise. If SNR is 127, for example, and the width of the frequency band is 1 MHz, then the maximum theoretical data rate is 7 Mbps, where 7 = log2(128). If the signal power S drops by about half so SNR=63, the data rate falls to 6 Mbps, as 6 = log2(64); the relationship between signal power and data rate is logarithmic.
The actual data rate achievable, for a given channel width and SNR, depends on the signal encoding, or modulation, mechanism. Most newer modulation mechanisms use “orthogonal frequency-division multiplexing”, OFDM, or some variant.
A central feature of OFDM is that one wider frequency band is divided into multiple narrow subchannels; each subchannel then carries a proportional fraction of the total information signal, modulated onto a subchannel-specific carrier. All the subchannels can be allocated to one transmission at a time (time-division multiplexing, 4.2 Time-Division Multiplexing), or disjoint sets of subchannels can be allocated to different transmissions that can then proceed (at proportionally lower data rates) in parallel. The latter is known as frequency-division multiplexing.
In many settings OFDM comes reasonably close to the Shannon-Hartley limit. Perhaps more importantly, OFDM also performs reasonably well with multipath interference, below, which is endemic in urban and building-interior environments with their many reflective surfaces. Multipath interference is, however, not necessarily comparable to the Gaussian noise assumed by the Shannon-Hartley theorem. We will not address further technical details of OFDM here, except to note that implementation usually requires some form of digital signal processing.
Another fundamental issue is that everyone shares the same radio spectrum. For mobile wireless providers, this constraint has driven prices to remarkable levels; the 2014-15 FCC AWS-3 auction raised almost $45 billion for 65 MHz (usable throughout the entire United States). This works out to somewhat over $2 per megahertz per phone. The corresponding issue for Wi-Fi users in a dense area is that all the available Wi-Fi bandwidth may be in use. Inside busy buildings one can often see dozens of Wi-Fi access points competing for the same Wi-Fi channel; the result is that no user will be getting close to the nominal data rates of 3.7 Wi-Fi.
Higher data rates require wider frequency bands. To reduce costs in the face of fixed demand, the usual strategy is to make the coverage zones smaller, either by reducing power (and adding more access points as appropriate), or by using directional antennas, or both.
While a radio signal generally covers a wide area – even with ordinary directional antennas – it does so in surprisingly non-uniform ways. A signal may reach a receiver through a line-of-sight path and also several reflected paths, possibly of varying length. In addition to reflection, the signal may be subject to reflection-like scattering and diffraction. All of this together is known as multipath interference (or, if analog audio is involved, multipath distortion; in the analog TV era this was ghosting).
The picture above shows two transmission paths from A to B. The respective carrier paths may interfere with or supplement one another. The longer delay of the reflecting path (red) wil also delay its encoded signal. The result, shown at right, is that the line-of-sight and reflected data symbols may overlap and interfere with each other; this is known as intersymbol interference. Multipath interference may even change the meaning of the data symbol as seen by the receiver; for example, the red and black low data-signal peaks above at the point of the vertical dashed line may sum together so as to be received as a higher peak (assuming the underlying carriers are in sync).
- Multipath interference tends to lead to wide fluctuations in signal intensity with a period of about half a wavelength; this phenomenon is known as multipath fading. As an example, the wavelength of FM radio stations in the United States is about 3 meters; in fringe reception areas it is not uncommon to pull a car forward a quarter wavelength and have a station go from clear to indecipherable, or even for reception to switch to another station (on the same frequency but transmitted from another location) altogether.
Signal-intensity map (simulated) in a room with walls with 40% reflectivity
The picture above is from a mathematical simulation intended to illustrate multipath fading. The walls of the room reflect 40% of the signal from the transmitter located in the orange ball at the lower left. The transmitter transmits an unmodulated carrier signal, which may be reflected off the walls any number of times; at any point in the room the total signal intensity is the sum over all possible reflection paths. On the right-hand side, the small-scale blue ripples represent the received carrier strength variation due to multipath interference between the line-of-sight and all the reflected paths. Note that the ripple size is about half a wavelength.
In comparison to this simulated intensity map, real walls tend to have a lower reflectivity, real rooms are not two-dimensional, and real carriers are modulated. However, real rooms also introduce scattering, diffraction and shadowing from objects within, and significant (3× to 10×) multipath-fading signal-strength variations are common in actual wireless settings.
Multipath fading can be either flat – affecting all frequencies more or less equally – or selective – affecting some frequencies differently than others. It is quite possible for an OFDM channel (18.104.22.168 OFDM) to encounter selective fading of only some of its subchannel frequencies.
Generally, multipath interference is a problem that engineers go to great lengths to overcome. However, as we shall see in 3.7.3 Multiple Spatial Streams, multipath interference can sometimes be put to positive use by allowing almost-adjacent antennas to transmit and receive independent signals, thus increasing the effective throughput.
For an alternative example of multipath interference in which the signal strength has no ripples, see exercise 13.0.
If you are cutting the network cable and replacing it with wireless, there is a good chance you will also want to cut the power cable as well and replace it with batteries. This tends to make power consumption a very important issue. The Wi-Fi standard has provisions for minimizing power usage by allowing a device to “doze” most of the time, waking periodically to check if any packets are ready to be sent to it (see 22.214.171.124 Joining a Network). The 6LoWPAN project (IPv6 Low-power Wireless Personal Area Network) is intended to support very low-power devices; see RFC 4919 and RFC 6282.
Wireless is also used simply to replace cords and their attendant tangle, and, of course, the problem of incompatible connectors. The low-power Bluetooth wireless standard is commonly used as a cable alternative for things like computer mice and telephone headsets. Bluetooth is also a low-power network; for many applications the working range is about 10 meters. ZigBee is another low-power small-scale network.
Wi-Fi is a trademark of the Wi-Fi Alliance denoting any of several IEEE wireless-networking protocols in the 802.11 family, specifically 802.11a, 802.11b, 802.11g, 802.11n, and 802.11ac. (Strictly speaking, these are all amendments to the original 802.11 standard, but they are also de facto standards in their own right.) Like classic Ethernet, Wi-Fi must deal with collisions; unlike Ethernet, however, Wi-Fi is unable to detect collisions in progress, complicating the backoff and retransmission algorithms. See 3.6.2 Collisions above.
Unlike any wired LAN protocol we have considered so far, in addition to normal data packets Wi-Fi also uses control and management packets that exist entirely within the Wi-Fi LAN layer; these are not initiated by or delivered to higher network layers. Control packets are used to compensate for some of the infelicities of the radio environment, such as the lack of collision detection. Putting radio-essential control and management protocols within the Wi-Fi layer means that the IP layer can continue to interact with the Wi-Fi LAN exactly as it did with Ethernet; no changes are required.
Wi-Fi is designed to interoperate freely with Ethernet at the logical LAN layer. Wi-Fi MAC (physical) addresses have the same 48-bit size as Ethernet’s and the same internal structure (2.1.3 Ethernet Address Internal Structure). They also share the same namespace: one is never supposed to see an Ethernet and a Wi-Fi interface with the same address. As a result, data packets can be forwarded by switches between Ethernet and Wi-Fi; in many respects a Wi-Fi LAN attached to an Ethernet LAN looks like an extension of the Ethernet LAN. See 3.7.4 Access Points.
Generally, Wi-Fi uses the 2.4 GHz ISM (Industrial, Scientific and Medical) band used also by microwave ovens, though 802.11a uses a 5 GHz band, 802.11n supports that as an option and the new 802.11ac has returned to using 5 GHz exclusively. The 5 GHz band has reduced ability to penetrate walls, often resulting in a lower effective range (though in offices and multi-unit housing this can be an advantage).
Wi-Fi radio spectrum is usually unlicensed, meaning that no special permission is needed to transmit but also that others may be trying to use the same frequency band simultaneously; the availability of unlicensed channels in the 5 GHz band continues to evolve.
The table below summarizes the different Wi-Fi versions. All data bit rates assume a single spatial stream; channel widths are nominal.
|IEEE name||maximum bit rate||frequency||channel width|
|802.11a||54 Mbps||5 GHz||20 MHz|
|802.11b||11 Mbps||2.4 GHz||20 MHz|
|802.11g||54 Mbps||2.4 GHz||20 MHz|
|802.11n||65-150 Mbps||2.4/5 GHz||20-40 MHz|
|802.11ac||78-867 Mbps||5 GHz||20-160 MHz|
The maximum bit rate is seldom achieved in practice. The effective bit rate must take into account, at a minimum, the time spent in the collision-handling mechanism. More significantly, all the Wi-Fi variants above use dynamic rate scaling, below; the bit rate is reduced up to tenfold (or more) in environments with higher error rates, which can be due to distance, obstructions, competing transmissions or radio noise. All this means that, as a practical matter, getting 150 Mbps out of 802.11n requires optimum circumstances; in particular, no competing senders and unimpeded line-of-sight transmission. 802.11n lower-end performance can be as little as 10 Mbps, though 40-100 Mbps (for a 40 MHz channel) may be more typical.
The 2.4 GHz ISM band is divided by international agreement into up to 14 officially designated (and mostly adjacent) channels, each about 5 MHz wide, though in the United States use may be limited to the first 11 channels. The 5 GHz band is similarly divided into 5 MHz channels. One Wi-Fi sender, however, needs several of these official channels; the typical 2.4 GHz 802.11g transmitter uses an actual frequency range of up to 22 MHz, or up to five official channels. As a result, to avoid signal overlap Wi-Fi use in the 2.4 GHz band is often restricted to official channels 1, 6 and 11. The end result is that there are generally only three available Wi-Fi bands in the 2.4 GHz range, and so Wi-Fi transmitters can and do interact with and interfere with each other.
There are almost 200 5 MHz channels in the 5 GHz band. The United States requires users of the this band to avoid interfering with weather and military applications in the same frequency range; this may involve careful control of transmission power and so-called “dynamic frequency selection” to choose channels with little interference. Even so, there are many more channels than at 2.4 GHz; the larger number of channels is one of the reasons (arguably the primary reason) that 802.11ac can run faster (below).
Wi-Fi designers can improve throughput through a variety of techniques, including
- improved radio modulation techniques
- improved error-correcting codes
- smaller guard intervals between symbols
- increasing the channel width
- allowing multiple spatial streams via multiple antennas
The first two in this list seem now to be largely tapped out; OFDM modulation (126.96.36.199 OFDM) is close enough to the Shannon-Hartley limit that there is limited room for improvement. The third reduces the range (because there is less protection from multipath interference) but may increase the data rate by ~10%. The largest speed increases are obtained the last two items in the list.
The channel width is increased by adding additional 5 MHz channels. For example, the 65 Mbps bit rate above for 802.11n is for a nominal frequency range of 20 MHz, comparable to that of 802.11g. However, in areas with minimal competition from other signals, 802.11n supports using a 40 MHz frequency band; the bit rate then goes up to 135 Mbps (or 150 Mbps if a smaller guard interval is used). This amounts to using two of the three available 2.4 GHz Wi-Fi bands. Similarly, the wide range in 802.11ac bit rates reflects support for using channel widths ranging from 20 MHz up to 160 MHz (32 5-MHz official channels).
Using multiple spatial streams is the newest data-rate-improvement technique; see 3.7.3 Multiple Spatial Streams.
For all the categories in the table above, additional bits are used for error-correcting codes. For 802.11g operating at 54 Mbps, for example, the actual raw bit rate is (4/3)×54 = 72 Mbps, sent in symbols consisting of six bits as a unit.
3.7.1 Wi-Fi and Collisions¶
We looked extensively at the 10 Mbps Ethernet collision-handling mechanisms in 2.1 10-Mbps Classic Ethernet, only to conclude that with switches and full-duplex links, Ethernet collisions are rapidly becoming a thing of the past. Wi-Fi, however, has brought collisions back from obscurity. An Ethernet sender will discover a collision, if one occurs, during the first slot time, by monitoring for faint interference with its own transmission. However, as mentioned in 3.6.2 Collisions, Wi-Fi transmitting stations simply cannot detect collisions in progress. If another station transmits at the same time, a Wi-Fi sender will see nothing amiss although its signal will not be received. While there is a largely-collision-free mode for Wi-Fi operation (3.7.7 Wi-Fi Polling Mode), it is not commonly used, and collision management has a significant impact on ordinary Wi-Fi performance.
188.8.131.52 Collision Avoidance and Backoff¶
The Ethernet collision-management algorithm was known as CSMA/CD, where CD stood for Collision Detection. The corresponding Wi-Fi mechanism is CSMA/CA, where CA stands for Collision Avoidance. A collision is presumed to have occurred if the link-layer ACK is not received. As with Ethernet, there is an exponential-backoff mechanism as well, though it is scaled somewhat differently.
Any sender wanting to send a new data packet waits the IFS time after first sensing the medium to see if it is idle. If no other traffic is seen in this interval, the station may then transmit immediately. However, if other traffic is sensed, the sender must do an exponential backoff even for its first transmission attempt; other stations, after all, are likely also waiting, and avoiding an initial collision is strongly preferred.
The initial backoff is to choose a random k<25 = 32 (recall that classic Ethernet in effect chooses an initial backoff of k<20 = 1; ie k=0). The prospective sender then waits k slot times. While waiting, the sender continues to monitor for other traffic; if any other transmission is detected, then the sender “suspends” the backoff-wait clock. The clock resumes when the other transmission has completed and one followup idle interval of length IFS has elapsed.
Note that, under these rules, data-packet senders always wait for at least one idle interval of length IFS before sending, thus ensuring that they never collide with an ACK sent after an idle interval of only SIFS.
On an Ethernet, if two stations are waiting for a third to finish before they transmit, they will both transmit as soon as the third is finished and so there will always be an initial collision. With Wi-Fi, because of the larger initial k<32 backoff range, such initial collisions are unlikely.
If a Wi-Fi sender believes there has been a collision, it retries its transmission, after doubling the backoff range to 64, then 128, 256, 512, 1024 and again 1024. If these seven attempts all fail, the packet is discarded and the sender starts over.
In one slot time, radio signals move 6,000 meters; the Wi-Fi slot time – unlike that for Ethernet – has nothing to do with the physical diameter of the network. As with Ethernet, though, the Wi-Fi slot time represents the fundamental unit for backoff intervals.
Finally, we note that, unlike Ethernet collisions, Wi-Fi collisions are a local phenomenon: if A and B transmit simultaneously, a collision occurs at node C only if the signals of A and B are both strong enough at C to interfere with one another. It is possible that a collision occurs at station C midway between A and B, but not at station D that is close to A. We return to this below in 184.108.40.206 Hidden-Node Problem.
220.127.116.11 Wi-Fi RTS/CTS¶
Wi-Fi stations optionally also use a request-to-send/clear-to-send (RTS/CTS) protocol, again negotiated with designated control packets. Usually this is used only for larger data packets; often, the RTS/CTS “threshold” (the size of the largest packet not sent using RTS/CTS) is set (as part of the Access Point configuration, 3.7.4 Access Points) to be the maximum packet size, effectively disabling this feature. The idea behind RTS/CTS is that a large packet that is involved in a collision represents a significant waste of potential throughput; for large packets, we should ask first.
The RTS control packet – which is small – is sent through the normal procedure outlined above; this packet includes the identity of the destination and the size of the data packet the station desires to transmit. The destination station then replies with CTS after the SIFS wait period, effectively preventing any other transmission after the RTS. The CTS packet also contains the data-packet size. The original sender then waits for SIFS after receiving the CTS, and sends the packet. If all other stations can hear both the RTS and CTS messages, then once the RTS and CTS are sent successfully no collisions should occur during packet transmission, again because the only idle times are of length SIFS and other stations should be waiting for time IFS.
18.104.22.168 Wi-Fi Fragmentation¶
Conceptually related to RTS/CTS is Wi-Fi fragmentation. If error rates or collision rates are high, a sender can send a large packet as multiple fragments, each receiving its own link-layer ACK. As we shall see in 5.3.1 Error Rates and Packet Size, if bit-error rates are high then sending several smaller packets often leads to fewer total transmitted bytes than sending the same data as one large packet.
Wi-Fi packet fragments are reassembled by the receiving node, which may or may not be the final destination.
As with the RTS/CTS threshold, the fragmentation threshold is often set to the size of the maximum packet. Adjusting the values of these thresholds is seldom necessary, though might be appropriate if monitoring revealed high collision or error rates. Unfortunately, it is essentially impossible for an individual station to distinguish between reception errors caused by collisions and reception errors caused by other forms of noise, and so it is hard to use reception statistics to distinguish between a need for RTS/CTS and a need for fragmentation.
3.7.2 Dynamic Rate Scaling¶
Wi-Fi senders, if they detect transmission problems, are able to reduce their transmission bit rate in a process known as rate scaling or rate control. The idea is that lower bit rates will have fewer noise-related errors, and so as the error rate becomes unacceptably high – perhaps due to increased distance – the sender should fall back to a lower bit rate. For 802.11g, the standard rates are 54, 48, 36, 24, 18, 12, 9 and 6 Mbps. Senders attempt to find the transmission rate that maximizes throughput; for example, 36 Mbps with a packet loss rate of 25% has an effective throughput of 36 × 75% = 27 Mbps, and so is better than 24 Mbps with no losses.
Senders may update their bit rate on a per-packet basis; senders may also choose different bit rates for different recipients. For example, if a sender sends a packet and receives no confirming link-layer ACK, the sender may fall back to the next lower bit rate. The actual bit-rate-selection algorithm lives in the particular Wi-Fi driver in use; different nodes in a network may use different algorithms.
The earliest rate-scaling algorithm was Automatic Rate Fallback, or ARF, [KM97]. The rate decreases after two consecutive transmission failures (that is, the link-layer ACK is not received), and increases after ten transmission successes.
A significant problem for rate scaling is that a packet loss may be due either to low-level random noise (white noise, or thermal noise) or to a collision (which is also a form of noise, but less random); only in the first case is a lower transmission rate likely to be helpful. If a larger number of collisions is experienced, the longer packet-transmission times caused by the lower bit rate may increase the frequency of hidden-node collisions. In fact, a higher transmission rate (leading to shorter transmission times) may help; enabling the RTS/CTS protocol may also help.
A variety of newer rate-scaling algorithms have been proposed; see [JB05] for a summary. One, Receiver-Based Auto Rate (RBAR, [HVB01]), attempts to incorporate the signal-to-noise ratio into the calculation of the transmission rate. This avoids the confusion introduced by collisions. Unfortunately, while the signal-to-noise ratio has a strong theoretical correlation with the transmission bit-error rate, most Wi-Fi radios will report to the host system the received signal strength. This is not the same as the signal-to-noise ratio, which is harder to measure. As a result, the RBAR approach has not been quite as effective in practice as might be hoped.
With the Collision-Aware Rate Adaptation algorithm (CARA, [KKCQ06]), a transmitting station attempts (among other things) to infer that its packet was lost to a collision rather than noise if, after one SIFS interval following the end of its packet transmission, no link-layer ACK has been received and the channel is still busy. This will detect collisions only when the colliding packet is longer than the station’s own packet, and only when the hidden-node problem isn’t an issue.
Because the actual data in a Wi-Fi packet may be sent at a rate not every participant is close enough to receive correctly, every Wi-Fi transmission begins with a brief preamble at the minimum bit rate. Link-layer ACKs, too, are sent at the minimum bit rate.
3.7.3 Multiple Spatial Streams¶
The latest innovation in improving Wi-Fi (and other wireless) data rates is to support multiple simultaneous data streams, through an antenna technique known as multiple-input-multiple-output, or MIMO. To use N streams, both sender and receiver must have N antennas; all the antennas use the same frequency channels but each transmitter antenna sends a different data stream. At first glance, any significant improvement in throughput might seem impossible, as the antenna elements in the respective sending and receiving groups are each within about half a wavelength of each other; indeed, in clear space MIMO is not possible.
The reason MIMO works in most everyday settings is that it puts multipath interference to positive use. Consider again at the right-hand side of the final image of 3.6.6 Multipath, in which the signal strength varies according to the blue ripples; the peaks and valleys have a period of about half a wavelength. We will assume initially that the signal strength is low enough that reception in the darkest blue areas is no longer viable; a single antenna with the misfortune to be in one of these “dead zones” may receive nothing.
We will start with two simpler cases: SIMO (single-input-multiple-output) and MISO (multiple-input-single-output). In SIMO, the receiver has multiple antennas; in MISO, the transmitter. Assume for the moment that the multiple-antenna side has two antennas. In the simplest implementation of SIMO, the receiver picks the stronger of the two received signals and uses that alone; as long as at least one antenna is not in a “dead zone”, reception is successful. With two antennas under half a wavelength apart, the odds are that at least one of them will be located outside a dead zone, and will receive an adequate signal.
Similarly, in simple MISO, the transmitter picks whichever of its antennas that gets a stronger signal to the receiver. The receiver is unlikely to be in a dead zone for both transmitter antennas. Note that for MISO the sender must get some feedback from the receiver to know which antenna to use.
We can do quite a bit better if signal-processing techniques are utilized so the two sender or two receiver antennas can be used simultaneously (though this complicates the mathematics considerably). Such signal-processing is standard in 802.11n and above; the Wi-Fi header, to assist this process, includes added management packets and fields for reporting MIMO-related information. One station may, for example, send the other a sequence of training symbols for discerning the response of the antenna system.
MISO with these added techniques is sometimes called beamforming: the sender coordinates its multiple antennas to maximize the signal reaching one particular receiver.
In our simplistic description of SIMO and MIMO above, in which only one of the multiple-antenna-side antennas is actually used, we have suggested that the idea is to improve marginal reception. At least one antenna on the multiple-antenna side can successfully communicate with the single antenna on the other side. MIMO, on the other hand, can be thought of as applying when transmission conditions are quite good all around, and every antenna on one side can reach every antenna on the other side. The key point is that, in an environment with a significant degree of multipath interference, the antenna-to-antenna paths may all be independent, or uncorrelated. At least one receiving antenna must be, from the perspective of at least one transmitting antenna, in a multipath-interference “gray zone” of reduced signal strength.
As a specific example, consider the diagram above, with two sending antennas A1 and A2 at the left and two receiving antennas B1 and B2 at the right. Antenna A1 transmits signal S1 and A2 transmits S2. There are thus four physical signal paths: A1-to-B1, A1-to-B2, A2-to-B1 and A2-to-B2. If we assume that the signal along the A1-to-B2 path (dashed and blue) arrives with half the strength of the other three paths (solid and black), then we have
signal received by B1: S1 + S2signal received by B2: S1/2 + S2
From these, B can readily solve for the two independent signals S1 and S2. These signals are said to form two spatial streams, though the spatial streams are abstract and do not correspond to any of the four physical signal paths.
The antennas are each more-or-less omnidirectional; the signal-strength variations come from multipath interference and not from physical aiming. Similarly, while the diagonal paths A1-to-B2 and A2-to-B1 are slightly longer than the horizontal paths A1-to-B1 and A2-to-B2, the difference is not nearly enough to allow B to solve for the two signals.
In practice, overall data-rate improvement over a single antenna can be considerably less than a factor of 2 (or than N, the number of antennas at each end).
The 802.11n standard allows for up to four spatial streams, for a theoretical maximum bit rate of 600 Mbps. 802.11ac allows for up to eight spatial streams, for an even-more-theoretical maximum of close to 7 Gbps. MIMO support is sometimes described with an A×B×C notation, eg 3×3×2, where A and B are the number of transmitting and receiving antennas and C ≤ min(A,B) is the number of spatial streams.
3.7.4 Access Points¶
There are two standard Wi-Fi configurations: infrastructure and ad hoc. The former involves connection to a designated access point; the latter includes individual Wi-Fi-equipped nodes communicating informally. For example, two laptops can set up an ad hoc connection to transfer data at a meeting. Ad hoc connections are often used for very simple networks not providing Internet connectivity. Complex ad hoc networks are, however, certainly possible; see 3.7.8 MANETs.
The infrastructure configuration is much more common. Stations in an infrastructure network communicate directly only with their access point, which, in turn, communicates with the outside world. If Wi-Fi nodes B and C share access point AP, and B wishes to send a packet to C, then B first forwards the packet to AP and AP then forwards it to C. While this introduces a degree of inefficiency, it does mean that the access point and its associated nodes automatically act as a true LAN: every node can reach every other node. (It is also often the case that most traffic is between Wi-Fi nodes and the outside world.) In an ad hoc network, by comparison, it is common for two nodes to be able to reach each other only by forwarding through an intermediate third node; this is in fact a form of the hidden-node scenario.
Wi-Fi access points are generally identified by their SSID (“Service Set IDentifier”), an administratively defined human-readable string such as “linksys” or “loyola”. Ad hoc networks also have SSIDs; these are generated pseudorandomly at startup and look like (but are not) 48-bit MAC addresses.
Finally, Wi-Fi is by design completely interoperable with Ethernet; if station A is associated with access point AP, and AP also connects via (cabled) Ethernet to station B, then if A wants to send a packet to B it sends it using AP as the Wi-Fi destination but with B also included in the header as the “actual” destination. Once it receives the packet by wireless, AP acts as an Ethernet switch and forwards the packet to B. While this forwarding is transparent to senders, the Ethernet and Wi-Fi LAN header formats are quite different.
The above diagram illustrates an Ethernet header and the Wi-Fi header for a typical data packet (not using Wi-Fi quality-of-service features). The Ethernet type field usually moves to an IEEE Logical Link Control header in the Wi-Fi region labeled “data”. The receiver and transmitter addresses are the MAC addresses of the nodes receiving and transmitting the (unicast) packet; these may each be different from the ultimate destination and source addresses. If station B wants to send a packet to station C in the same network, the source and destination are B and C but the transmitter and receiver are B and the access point. In infrastructure mode either the receiver or transmitter address is always the access point; in typical situations either the receiver is the destination or the sender is the transmitter. In ad hoc mode, if LAN-layer routing is used then all four addresses may be distinct; see 22.214.171.124 Routing in MANETs.
126.96.36.199 Joining a Network¶
To join the network, an individual station must first discover its access point, and must authenticate and then associate to that access point before general communication can begin. The authentication and association processes are carried out by an exchange of special management packets, which are confined to the Wi-Fi LAN layer. Occasionally stations may re-associate to their Access Point, eg if they wish to communicate some status update.
Access points periodically broadcast their SSID in special beacon packets (though for pseudo-security reasons the SSID in the beacon packets can be suppressed). Beacon packets are one of several Wi-Fi-layer-only management packets; the default beacon-broadcast interval is 100 ms. These broadcasts allow stations to see a list of available networks; the beacon packets also contain other Wi-Fi network parameters such as radio-modulation parameters and available data rates.
Another use of beacons is to support the power-management doze mode. Some stations may elect to enter this power-conservation mode, in which case they inform the access point, record the announced beacon-transmission time interval and then wake up briefly to receive each beacon. Beacons, in turn, each contain a list (in a compact bitmap form) of each dozing station for which the access point has a packet to deliver.
Ad hoc networks have beacon packets as well; all nodes participate in the regular transmission of these via a distributed algorithm.
A connecting station may either wait for the next scheduled beacon, or send a special probe packet to elicit a beacon-like response. These operations may involve listening to or transmitting on multiple radio channels, sequentially, as the station does not yet know the correct channel to use.
Once the beacon is received, the station initiates an authentication process. In the early versions of Wi-Fi this involved either “open” authentication or “shared WEP key” authentication. Later, support for a wide range of authentication protocols was introduced, via the 802.1X framework; we return to this in 3.7.5 Wi-Fi Security.
In open authentication the station sends an authentication request to the access point and the access point replies. About all the station needs to know is the SSID of the access point, though it is usually possible to configure the access point to restrict admission to stations with MAC (physical) addresses on a predetermined list. (Stations might evade MAC-address checking by changing their MAC address to an acceptable one, if the Wi-Fi driver supports it.)
Because the SSID plays something of the role of a password here, some Wi-Fi access points are configured so that beacon packets does not contain the SSID; such access points are said to be hidden. Unfortunately, access points hidden this way are easily unmasked: first, the SSID is sent in the clear by any other stations that need to authenticate, and second, an attacker can often transmit forged deauthentication or disassociation requests to force legitimate stations to retransmit the SSID. (See “management frame protection” in 3.7.5 Wi-Fi Security for a fix to this last problem.)
The shared-WEP-key authentication is based on the (obsolete) WEP encryption mechanism (3.7.5 Wi-Fi Security). It involves a challenge-response exchange by which the station proves to the access point that it knows the shared WEP key. Actual WEP encryption starts slightly later.
The next step in an infrastructure network is for the station to associate to the access point; this is not necessary in an ad hoc network. The primary goal of the association process is to ensure that the access point knows what stations it can reach, as packets from other stations or the outside world arrive and need to be either forwarded (or dropped, if the destination is not associated).
Any station (in particular an access point) keeps track of three states for each other station:
- not authenticated
- authenticated but not associated
- authenticated and associated
In each state, only certain packets are accepted for reception from or forwarding to the remote station. For example, in the “not authenticated” state, basic control packets such as ACK and RTS/CTS are accepted, as are the management packets necessary for authentication. Data packets are permitted either from or to the remote station if their ultimate destination is within the Wi-Fi LAN, though data packets from or to the outside world are permitted only in the third state above.
188.8.131.52 MAC Address Randomization¶
Most Wi-Fi-enabled devices are configured to transmit Wi-Fi probe requests at regular intervals (and on all available channels), at least when not connected. These probe requests identify available Wi-Fi networks, but they also reveal the device’s MAC address. This allows sites such as stores to track customers by their device. To prevent such tracking, some devices now support MAC address randomization, proposed in [GG03]: the use at appropriate intervals of a new MAC address randomly selected by the device.
Probe requests are generally sent when the device is not joined to a network. To prevent tracking via probe requests, the simplest approach is to change the MAC address used for probes at regular, frequent intervals. A device might even change its MAC address on every probe.
Changing the MAC address used for actually joining a network is also important to prevent tracking, but introduces some complications. RFC 7844 suggests these options for selecting new random addresses:
- At regular time intervals
- Per connection: each time the device connects to a Wi-Fi network, it will select a new MAC address
- Per network: like the above, except that if the device reconnects to the same network (identified by SSID), it will use the same MAC address
The first option, changing the joined MAC address at regular time intervals, breaks things. First, it will likely result in assignment of a new IP address to the device, terminating all existing connections. Second, many sites still authenticate – at least in part – based on the MAC address. The per-connection option prevents the first problem. The per-network option prevents both, but allows a site at which the device actually joins the network to track repeat connections. (Configuring the device to “forget” the connection between successive joins will usually prevent this, but may not be convenient.)
Another approach to the tracking problem is to disable probe requests entirely, except on explicit demand.
In the original plan, IPv6 addresses embedded the MAC address, and thus introduced another mechanism for device tracking. MAC address randomization can prevent this form of tracking as well, but other techniques implementable solely in the IP layer appear to be more popular; see 8.2.1 Interface identifiers.
Finally, it is possible to track many Wi-Fi devices based on minute variations in the modulated signals they transmit. MAC address randomization does nothing to prevent such “radiometric identification”. See [BBGO08] and [VMCCP16].
184.108.40.206 Wi-Fi Roaming¶
Large installations with multiple access points can create “roaming” access by assigning all the access points the same SSID. An individual station will stay with the access point with which it originally associated until the signal strength falls below a certain level, at which point it will seek out other access points with the same SSID and with a stronger signal. In this way, a large area can be carpeted with multiple Wi-Fi access points, so as to look like one large Wi-Fi domain. The access points must all be connected via a wired LAN, known as the distribution system. At any one time, a station may be associated to only one access point.
In order for such a large-area network to work, traffic to a wireless station, eg B, must find that station’s current access point, eg AP. This is a job for the distribution system. If the distribution system is a switched Ethernet supporting the usual learning mechanism (2.4 Ethernet Switches), one simple approach is to handle this the same way as, in a wired Ethernet, traffic finds a laptop that has been unplugged, carried to a new building, and plugged in again. Suppose B is a wireless node that has been exchanging packets via the distribution system with wired node C (perhaps a router connecting B to the Internet). When B moves to a new access point, all it has to do is send any packet over the LAN to C, and the Ethernet switches on the path from B to C will then learn the route through the switched Ethernet from C back to B’s new AP, and thus to B. It is also possible for B’s new AP to send this switch-updating packet.
This process may leave other switches in the distribution system still holding in their forwarding tables the old location for B. This is not terribly serious, as it will be fixed for any one switch as soon as B sends a packet to a destination reached by that switch. The problem can be avoided entirely if, after moving, B (or, again, its new AP) sends out an Ethernet broadcast packet.
3.7.5 Wi-Fi Security¶
Unencrypted Wi-Fi traffic is visible to anyone nearby with an appropriate receiver; this eavesdropping zone can be expanded by use of a larger antenna. Because of this, Wi-Fi security is important, and Wi-Fi supports several types of traffic encryption.
The original – and now obsolete – Wi-Fi encryption standard was Wired-Equivalent Privacy, or WEP. It involved a 5-byte key, later sometimes extended to 13 bytes. The encryption algorithm was based on RC4, 220.127.116.11 RC4. The key was a pre-shared key, manually configured into each station.
Because of the specific way WEP made use of the RC4 cipher, it contained a fatal (and now-classic) flaw. Bytes of the key could be could be “broken” – that is, guessed – sequentially. Knowing bytes 0 through i−1 would allow an attacker to guess byte i with a relatively small amount of data, and so on through the entire key. See 21.7.7 Wi-Fi WEP Encryption Failure for details.
WEP was replaced with Wi-Fi Protected Access, or WPA. This used the so-called TKIP encryption algorithm that, like WEP, was ultimately based on RC4, but which was immune to the sequential attack that made WEP so vulnerable. WPA was later replaced by WPA2, which uses the presumptively stronger AES encryption (21.7.2 Block Ciphers). WPA2 encryption is believed to be quite secure, although there was a vulnerability in the associated Wi-Fi Protected Setup protocol. WPA and WPA2 are defined in the IEEE 802.11i standard (an amendment to 802.11), where they are known as robust security network protocols.
WPA2 (and WPA) comes in two flavors: WPA2-Personal and WPA2-Enterprise. These use the same AES encryption, but differ in how keys are managed. WPA2-Personal, appropriate for many smaller sites, uses a pre-shared master key. This key must be entered into the Access Point (ideally not over the air) and into each connecting station. The key is usually a secure hash (21.6 Secure Hashes) of a somewhat longer passphrase. The use of a common key for multiple stations makes changing the key, or revoking the key for a particular user, difficult.
In any secure Wi-Fi authentication protocol, the station must authenticate to the access point and the access point must authenticate to the station; without the latter part, stations might inadvertently connect to rogue access points, which would then likely gain at least partial access to private data. In WPA2-Personal authentication, this is achieved through a so-called four-way handshake, which also generates a session key that is independent of the master key.
Both station and access point begin by each selecting a random string, called a nonce, typically 32 bytes long. The session key will be a secure hash of the master key, both nonces, and both MAC addresses. The four-way handshake begins with the access point sending its nonce, unencrypted, to the station.
At this point the station has enough information to compute the session key; in the second message of the handshake it now sends its own nonce to the access point. The nonce is again sent in the clear, but this second message also includes a digital signature based on the session key. This signature is calculated in a manner similar to the HMAC mechanism of 21.6.1 Secure Hashes and Authentication. Upon receipt of the station’s nonce, the access point too is able to compute the session key. With this key the access point now verifies the attached signature. If it checks out, that proves to the access point that the station did in fact know the master key, as a valid signature could not have been constructed without it. The station has now authenticated itself to the access point.
For the third step, the access point, now also in possession of the full session key, sends a signed message to the station; this message includes a starting sequence number for future message numbering. When this message is received and verified, the access point has authenticated itself to the station. The fourth and final step is simply an acknowledgment from the client.
The WPA2-Enterprise alternative allows each station to have its own separate key. In fact, it largely separates the encryption mechanisms from the Wi-Fi protocols, allowing sites great freedom in choosing the former. Despite the “enterprise” in the name, it is also well suited for smaller sites. WPA2-Enterprise is based rather closely on the 802.1X framework, which supports arbitrary authentication protocols as plug-in modules.
The keys are all held by a single common system known as the authentication server, usually unrelated to the access point. The client node (that is, the Wi-Fi station) is known as the supplicant, and the access point is known as the authenticator.
To begin the authentication/association process, the supplicant contacts the authenticator using the Extensible Authentication Protocol, or EAP, with what amounts to a request to associate to that access point. EAP is a generic message framework meant to support multiple specific types of authentication; see RFC 3748 and RFC 5247. The EAP request is forwarded to the authentication server, which may exchange (via the authenticator) several challenge/response messages with the supplicant. EAP is usually used in conjunction with the RADIUS (Remote Authentication Dial-In User Service) protocol (RFC 2865), which is a specific (but flexible) authentication-server protocol. WPA2-Enterprise is sometimes known as 802.1X mode, EAP mode or RADIUS mode.
One peculiarity of EAP is that EAP communication takes place before the supplicant is given an IP address (in fact before the supplicant has completed associating itself to the access point); thus, a mechanism must be provided to support exchange of EAP packets between supplicant and authenticator. This mechanism is known as EAPOL, for EAP Over LAN. EAP messages between the authenticator and the authentication server, on the other hand, can travel via IP; in fact, sites may choose to have the authentication server hosted remotely.
Once the authentication server (eg RADIUS server) is set up, specific per-user authentication methods can be entered. This can amount to ⟨username,password⟩ pairs, or some form of security certificate, or often both. The authentication server will generally allow different encryption protocols to be used for different supplicants, thus allowing for the possibility that there is not a common protocol supported by all stations.
When this authentication strategy is used, the access point no longer needs to know anything about what authentication protocol is actually used; it is simply the middleman forwarding EAP packets between the supplicant and the authentication server. The access point allows the supplicant to associate into the network once it receives permission to do so from the authentication server. A four-way-handshake mechanism may still be used to negotiate a session key.
18.104.22.168 Encryption Coverage¶
Originally, encryption covered only the data packets. A common attack involved forging management packets, eg to force stations to disassociate from their access point. Sometimes this was done continuously as a denial-of-service attack; it might also be done to force a station to reassociate and thus reveal a hidden SSID, or to reveal key information to enable a brute-force decryption attack.
The 2009 IEEE 802.11w amendment introduced the option for a station and access point to negotiate management frame protection, which encrypts (and digitally signs) essential management packets exchanged after the authentication phase is completed. This includes those station-to-access-point packets requesting deauthentication or disassociation, effectively preventing the above attacks. However, management frame protection is (as of 2015) seldom enabled by default by consumer-grade Wi-Fi access points, even when data encryption is in effect.
3.7.6 Wi-Fi Monitoring¶
Again depending on ones driver, it is sometimes possible to monitor all Wi-Fi traffic on a given channel. Special tools exist for this, including aircrack-ng and kismet, but often plain Wireshark will suffice if one can get the underlying driver into so-called “monitor” mode. On linux systems the command
iwconfig wlan0 mode monitor may do this (where
wlan0 is the name of the wireless network interface); it may be necessary to kill other processes that also have the
wlan0 interface open. One likely also needs to set the receive channel, eg with
iwconfig wlan0 channel 1. (On the author’s system, the interface
wlan0 changed to
mon0 after the transition to monitor mode.)
After the mode and channel are set, Wireshark will report the 802.11 management-frame headers, and also the so-called radiotap header containing information about the transmission data rate, channel, and received signal strength.
One useful experiment is to begin monitoring and then to power up a Wi-Fi enabled device. The WireShark filter
wlan.addr == device-MAC-address helps focus on the relevant packets. The WireShark screenshot below is an example.
we see node AsustekC_a7:66:6f broadcast a probe request, which is answered by the access point Cisco-Li_d1:24:40. The next three packets begin the authentication process; the packet highlighted in orange represents the association request.
3.7.7 Wi-Fi Polling Mode¶
Wi-Fi also includes a “polled” mechanism, where one station (the Access Point) determines which stations are allowed to send. While it is not often used, it has the potential to greatly reduce collisions, or even eliminate them entirely. This mechanism is known as “Point Coordination Function”, or PCF, versus the collision-oriented mechanism which is then known as “Distributed Coordination Function”. The PCF name refers to the fact that in this mode it is the Access Point that is in charge of coordinating which stations get to send when.
The PCF option offers the potential for regular traffic to receive improved throughput due to fewer collisions. However, it is often seen as intended for real-time Wi-Fi traffic, such as voice calls over Wi-Fi.
The idea behind PCF is to schedule, at regular intervals, a contention-free period, or CFP. During this period, the Access Point may
- send Data packets to any receiver
- send Poll packets to any receiver, allowing that receiver to reply with its own data packet
- send a combination of the two above (not necessarily to the same receiver)
- send management packets, including a special packet marking the end of the CFP
None of these operations can result in a collision (unless an unrelated but overlapping Wi-Fi domain is involved).
Stations receiving data from the Access Point send the usual ACK after a SIFS interval. A data packet from the Access Point addressed to station B may also carry, piggybacked in the Wi-Fi header, a Poll request to another station C; this saves a transmission. Polled stations that send data will receive an ACK from the Access Point; this ACK may be combined in the same packet with the Poll request to the next station.
At the end of the CFP, the regular “contention period” or CP resumes, with the usual CSMA/CA strategy. The time interval between the start times of consecutive CFP periods is typically 100 ms, short enough to allow some real-time traffic to be supported.
During the CFP, all stations normally wait only the Short IFS, SIFS, between transmissions. This works because normally there is only one station designated to respond: the Access Point or the polled station. However, if a station is polled and has nothing to send, the Access Point waits for time interval PIFS (PCF Inter-Frame Spacing), of length midway between SIFS and IFS above (our previous IFS should now really be known as DIFS, for DCF IFS). At the expiration of the PIFS, any non-Access-Point station that happens to be unaware of the CFP will continue to wait the full DIFS, and thus will not transmit. An example of such a CFP-unaware station might be one that is part of an entirely different but overlapping Wi-Fi network.
The Access Point generally maintains a polling list of stations that wish to be polled during the CFP. Stations request inclusion on this list by an indication when they associate or (more likely) reassociate to the Access Point. A polled station with nothing to send simply remains quiet.
PCF mode is not supported by many lower-end Wi-Fi routers, and often goes unused even when it is available. Note that PCF mode is collision-free, so long as no other Wi-Fi access points are active and within range. While the standard has some provisions for attempting to deal with the presence of other Wi-Fi networks, these provisions are somewhat imperfect; at a minimum, they are not always supported by other access points. The end result is that polling is not quite as useful as it might be.
The MANET acronym stands for mobile ad hoc network; in practice, the term generally applies to ad hoc wireless networks of sufficient complexity that some internal routing mechanism is needed to enable full connectivity. The term mesh network is also used. While MANETs can use any wireless mechanism, we will assume here that Wi-Fi is used.
MANET nodes communicate by radio signals with a finite range, as in the diagram below.
Each node’s radio range is represented by a circle centered about that node. In general, two MANET nodes may be able to communicate only by relaying packets through intermediate nodes, as is the case for nodes A and G in the diagram above.
In the field, the radio range of each node may not be very circular at all, due to among other things signal reflection and blocking from obstructions. An additional complication arises when the nodes (or even just obstructions) are moving in real time (hence the “mobile” of MANET); this means that a working route may stop working a short time later. For this reason, and others, routing within MANETs is a good deal more complex than routing in an Ethernet. A switched Ethernet, for example, is required to be loop-free, so there is never a choice among multiple alternative routes.
Note that, without successful LAN-layer routing, a MANET does not have full node-to-node connectivity and thus does not meet the definition of a LAN given in 1.9 LANs and Ethernet. With either LAN-layer or IP-layer routing, one or more MANET nodes may serve as gateways to the Internet.
Note also that MANETs in general do not support broadcast or multicast, unless the forwarding of broadcast and multicast messages throughout the MANET is built in to the routing mechanism. This can complicate the operation of IPv4 and IPv6 networks, even assuming that the MANET routing mechanism replaces the need for broadcast/multicast protocols like IPv4’s ARP (7.9 Address Resolution Protocol: ARP) and IPv6’s Neighbor Discovery (8.6 Neighbor Discovery) that otherwise play important roles in local packet delivery. For example, the common IPv4 address-assignment mechanism we will describe in 7.10 Dynamic Host Configuration Protocol (DHCP) relies on broadcast and so often needs adaptation. Similarly, IPv6 relies on multicast for several ancillary services, including address assignment (8.7.3 DHCPv6) and duplicate address detection (8.7.1 Duplicate Address Detection).
Finally, we observe that while MANETs are of great theoretical interest, their practical impact has been modest; they are almost unknown, for example, in corporate environments. They appear most useful in emergency situations, rural settings, and settings where the conventional infrastructure network has failed or been disabled.
22.214.171.124 Routing in MANETs¶
Routing in MANETs can be done either at the LAN layer, using physical addresses, or at the IP layer with some minor bending (below) of the rules.
Either way, nodes must find out about the existence of other nodes, and appropriate routes must then be selected. Route selection can use any of the mechanisms we describe later in 9 Routing-Update Algorithms.
Routing at the LAN layer is much like routing by Ethernet switches; each node will construct an appropriate forwarding table. Unlike Ethernet, however, there may be multiple paths to a destination, direct connectivity between any particular pair of nodes may come and go, and negotiation may be required even to determine which MANET nodes will serve as forwarders.
Routing at the IP layer involves the same issues, but at least IP-layer routing-update algorithms have always been able to handle multiple paths. There are some minor issues, however. When we initially presented IP forwarding in 1.10 IP - Internet Protocol, we assumed that routers made their decisions by looking only at the network prefix of the address; if another node had the same network prefix it was assumed to be reachable directly via the LAN. This model usually fails badly in MANETs, where direct reachability has nothing to do with addresses. At least within the MANET, then, a modified forwarding algorithm must be used where every address is looked up in the forwarding table. One simple way to implement this is to have the forwarding tables contain only host-specific entries as were discussed in 3.1 Virtual Private Networks.
Multiple routing algorithms have been proposed for MANETs. Performance of a given algorithm may depend on the following factors:
- The size of the network
- Whether some nodes have agreed to serve as routers
- The degree of node mobility, especially of routing-node mobility if applicable
- Whether the nodes are under common administration, and thus may agree to defer their own transmission interests to the common good
- per-node storage and power availability
3.8 WiMAX and LTE¶
WiMAX and LTE are both wireless network technologies suitable for data connections to mobile (and sometimes stationary) devices.
WiMAX is an IEEE standard, 802.16; its original name is WirelessMAN (for Metropolitan Area Network), and this name appears intermittently in the IEEE standards. In its earlier versions it was intended for stationary subscribers (802.16d), but was later expanded to support mobile subscribers (802.16e). The stationary-subscriber version is often used to provide residential Internet connectivity, in both urban and rural areas.
LTE (the acronym itself stands for Long Term Evolution) is a product of the mobile telecom world; it was designed for mobile subscribers from the beginning. Its official name – at least for its radio protocols – is Evolved UTRA, or E-UTRA, where UTRA in turn stands for UMTS Terrestrial Radio Access. UMTS stands for Universal Mobile Telecommunications System, a core mobile-device data-network mechanism with standards dating from the year 2000.
Both LTE and the mobile version of WiMAX are often marketed as fourth generation (or 4G) networking technology. The ITU has a specific definition for 4G developed in 2008, officially named IMT-Advanced and including a 100 Mbps download rate to moving devices and a 1 Gbps download rate to more-or-less-stationary devices. Neither WiMAX nor LTE quite qualified technically, but to marketers that was no impediment. In any event, in December 2010 the ITU issued a statement in which it “recognized that [the term 4G], while undefined, may also be applied to the forerunners of these technologies, LTE and WiMax”. So-called Advanced LTE and WiMAX2 are true IMT-Advanced protocols.
As in 3.6.4 Band Width we will use the term “data rate” for what is commonly called “bandwidth” to avoid confusion with the radio-specific meaning of the latter term.
WiMAX can use unlicensed frequencies, like Wi-Fi, but its primary use is over licensed radio spectrum; LTE is used almost exclusively over licensed spectrum.
WiMAX and LTE both support a number of options for the width of the frequency band; the wider the band, the higher the data rate. Downlink (base station to subscriber) data rates can be well over 100 Mbps (uplink rates are usually smaller). Most LTE bands are either in the range 700-900 MHz or are above 1700 MHz; the lower frequencies tend to be better at penetrating trees and walls.
Like Wi-Fi, WiMAX and LTE subscriber stations connect to a central access point. The WiMAX standard prefers the term base station which we will use henceforth for both protocols; LTE officially prefers the term “evolved NodeB” or eNB.
The coverage radius for LTE and mobile-subscriber WiMAX might be one to ten kilometers, versus less (sometimes much less) than 100 meters for Wi-Fi. Stationary-subscriber WiMAX can operate on a larger scale; the coverage radius can be several tens of kilometers. As distances increase, the data rate is reduced.
Large-radius base stations are typically mounted in towers; smaller-radius base-stations, generally used only in areas densely populated with subscribers, may use lower antennas integrated discretely into the local architecture. Subscriber stations are not expected to be able to hear other stations; they interact only with the base station.
The uplink scheduling of the previous section requires that each subscriber station know the distance to the base station. If a subscriber station is to transmit so that its message arrives at the base station at a certain time, it must actually begin transmission early by an amount equal to the one-way station-to-base propagation delay. This distance/delay measurement process is called ranging.
Ranging can be accomplished through any RTT measurement. Any base-station delay in replying, once a subscriber message is received, simply needs to be subtracted from the total RTT. Of course, that base-station delay needs also to be communicated back to the subscriber.
The distance to the base station is used not only for the subscriber station’s transmission timing, but also to determine its power level; signals from each subscriber station, no matter where located, should arrive at the base station with about the same power.
3.8.3 Network Entry¶
The scheduling process eliminates the potential for collisions between normal data transmissions. But there remains the issue of initial entry to the network. If a handoff is involved, the new base station can be informed by the old base station, and send an appropriate schedule to the moving subscriber station. But if the subscriber station was just powered on, or is arriving from an area without LTE/WiMAX coverage, potential transmission collisions are unavoidable. Fortunately, network entry is infrequent, and so collisions are even less frequent.
A subscriber station begins the network-entry connection process to a base station by listening for the base station’s transmissions; these message streams contain regular management messages containing, among other things, information about available data rates in each direction. Also included in the base station’s message stream is information about when network-entry attempts can be made.
In WiMAX these entry-attempt timeslots are called ranging intervals; the subscriber station waits for one of these intervals and sends a “range-request” message to the base station. These ranging intervals are open to all stations attempting network entry, and if another station transmits at the same time there will be a collision. An Ethernet/Wi-Fi-like exponential-backoff process is used if a collision does occur.
In LTE the entry process is known as RACH, for Random Access CHannel. The base station designates certain 1 ms timeslots for network entry. During one of these slots an entry-seeking subscriber chooses at random one of up to 64 predetermined random access preambles (some preambles may be reserved for a second, contention-free form of RACH), and transmits it. The 1-ms timeslot corresponds to 300 kilometers, much larger than any LTE cell, so the fact that the subscriber does not yet know its distance to the base does not matter.
The preambles are mathematically “orthogonal”, in such a way that as long as no two RACH-participating subscribers choose the same preamble, the base station can decode overlapping preambles and thus receive the set of all preambles transmitted during the RACH timeslot. The base station then sends a reply, listing the preambles received and, in effect, an initial schedule indexed by preamble of when each newly entering subscriber station can transmit actual data. This reply is sent to a special temporary multicast address known as a radio network temporary identifier, or RNTI, as the base station does not yet know the actual identity of any new subscriber. Those identities are learned as the new subscribers transmit to the base station according to this initial schedule.
A collision occurs when two LTE subscriber stations have the misfortune of choosing the same preamble in the same RACH timeslot, in which case the chosen preamble will not appear in the initial schedule transmitted by the base station. As for WiMAX, collisions are rare because network entry is rare. Subscribers experiencing a collision try again during the next RACH timeslot, choosing at random a new preamble.
For both WiMAX and LTE, network entry is the only time when collisions can occur; afterwards, all subscriber-station transmissions are scheduled by the base station.
If there is no collision, each subscriber station is able to use the base station’s initial-response transmission to make its first ranging measurement. Subscribers must have a ranging measurement in hand before they can send any scheduled transmission.
There are some significant differences between stationary and mobile subscribers. First, mobile subscribers will likely expect some sort of handoff from one base station to another as the subscriber moves out of range of the first. Second, moving subscribers mean that the base-to-subscriber ranging information may change rapidly; see exercise 7.0. If the subscriber does not update its ranging information often enough, it may transmit too early or too late. If the subscriber is moving fast enough, the Doppler effect may also alter frequencies.
3.9 Fixed Wireless¶
This category includes all wireless-service-provider systems where the subscriber’s location does not change. Often, but not always, the subscriber will have an outdoor antenna for improved reception and range. Fixed-wireless systems can involve relay through satellites, or can be terrestrial.
3.9.1 Terrestrial Wireless¶
Terrestrial wireless – also called terrestrial broadband or fixed-wireless broadband – involves direct (non-satellite) radio communication between subscribers and a central access point. Access points are usually tower-mounted and serve multiple subscribers, though single-subscriber point-to-point “microwave links” also exist. A multi-subscriber access point may serve an area with radius up to several tens of miles, depending on the technology, though more common ranges are under ten miles. WiMAX 802.16d is one form of terrestrial wireless, but there are several others. Frequencies may be either licensed or unlicensed. Unlicensed frequency bands are available at around 900 MHz, 2.4 GHz, and 5 GHz. Nominally all three bands require that line-of-sight transmission be used, though that requirement becomes stricter as the frequency increases. Lower frequencies tend to be better at “seeing” through trees and other obstructions.
Terrestrial fixed wireless was originally popularized for rural areas, where residential density is too low for economical cable connections. However, some fixed-wireless ISPs now operate in urban areas, often using WiMAX. One advantage of terrestrial fixed-wireless in remote areas is that the antennas covers a much smaller geographical area than a satellite, generally meaning that there is more data bandwidth available per user and the cost per megabyte is much lower.
Outdoor subscriber antennas often use a parabolic dish to improve reception; sizes range from 10 to 50 cm in diameter. The size of the dish may depend on the distance to the central tower.
While there are standardized fixed-wireless systems, such as WiMAX, there are also a number of proprietary alternatives, including systems from Trango and Canopy. Fixed-wireless systems might, in fact, be considered one of the last bastions of proprietary LAN protocols. This lack of standardization is due to a variety of factors; two primary ones are the relatively modest overall demand for this service and the the fact that most antennas need to be professionally installed by the ISP to ensure that they are “properly mounted, aligned, grounded and protected from lightning”.
3.9.2 Satellite Internet¶
An extreme case of fixed wireless is satellite Internet, in which signals pass through a satellite in geosynchronous orbit (35,786 km above the earth’s surface). Residential customers have parabolic antennas typically from 70 to 100 cm in diameter, larger than those used for terrestrial wireless but smaller than the dish antennas used at access points. The geosynchronous satellite orbit means that the antennas need to be pointed only once, at installation. Transmitter power is typically 1-2 watts, remarkably low for a signal that travels 35,786 km.
The primary problem associated with satellite Internet is very long RTTs. The the speed-of-light round-trip propagation delay is about 500 ms to which must be added queuing delays for the often-backlogged access point (my own personal experience suggested that RTTs of close to 1,000 ms were the norm). These long delays affect real-time traffic such as VoIP and gaming, but as we shall see in 14.11 The Satellite-Link TCP Problem bulk TCP transfers also perform poorly with very long RTTs. To provide partial compensation for the TCP issue, many satellite ISPs provide some sort of “acceleration” for bulk downloads: a web page, for example, would be downloaded rapidly by the access point and streamed to the satellite and back down to the user via a proprietary mechanism. Acceleration, however, cannot help interactive connections such as VPNs.
Another common feature of satellite Internet is a low daily utilization cap, typically in the hundreds of megabytes. Utilization caps are directly tied to the cost of maintaining satellites, but also to the fact that one satellite covers a great deal of ground, and so its available capacity is shared by a large number of users.
The delay issues associated with satellite Internet would go away if satellites were in so-called low-earth orbits, a few hundred km above the earth. RTTs would then be comparable with terrestrial Internet. Fixed-direction antennas could no longer be used. A large number of satellites would need to be launched to provide 24-hour coverage even at one location. To data (2016), such a network of low-earth satellites has been proposed, but not yet launched.
Along with a few niche protocols, we have focused primarily here on wireless and on virtual circuits. Wireless, of course, is enormously important: it is the enabler for mobile devices, and has largely replaced traditional Ethernet for home and office workstations.
While it is sometimes tempting (in the IP world at least) to write off ATM as a niche technology, virtual circuits are a serious conceptual alternative to datagram forwarding. As we shall see in 19 Quality of Service, IP has problems handling real-time traffic, and virtual circuits offer a solution. The Internet has so far embraced only small steps towards virtual circuits (such as MPLS, 19.12 Multi-Protocol Label Switching (MPLS)), but they remain a tantalizing strategy.
Exercises are given fractional (floating point) numbers, to allow for interpolation of new exercises. Exercise 4.5 is distinct, for example, from exercises 4.0 and 5.0. Exercises marked with a ♢ have solutions or hints at 23.3 Solutions for Other LANs.
1.0. Suppose remote host A uses a VPN connection to connect to host B, with IP address 126.96.36.199. A’s normal Internet connection is via device
eth0 with IP address 188.8.131.52; A’s VPN connection is via device
ppp0 with IP address 10.0.0.44. Whenever A wants to send a packet via
ppp0, it is encapsulated and forwarded over the connection to B at 184.108.40.206.
eth0and all traffic to anywhere else uses
ppp0. What happens if an intruder M attempts to open a connection to A at 220.127.116.11? What route will packets from A to M take?
ppp0. Describe what will happen when A tries to send a packet.
2.0. Suppose remote host A wishes to use a TCP-based VPN connection to connect to host B, with IP address 18.104.22.168. However, the VPN software is not available for host A. Host A is, however, able to run that software on a virtual machine V hosted by A; A and V have respective IP addresses 10.0.0.1 and 10.0.0.2 on the virtual network connecting them. V reaches the outside world through network address translation (7.7 Network Address Translation), with A acting as V’s NAT router. When V runs the VPN software, it forwards packets addressed to B the usual way, through A using NAT. Traffic to any other destination it encapsulates over the VPN.
Can A configure its IP forwarding table so that it can make use of the VPN? If not, why not? If so, how? (If you prefer, you may assume V is a physical host connecting to a second interface on A; A still acts as V’s NAT router.)
3.0. Token Bus was a proprietary Ethernet-based network. It worked like Token Ring in that a small token packet was sent from one station to the next in agreed-upon order, and a station could transmit only when it had just received the token.
4.0. The IEEE 802.11 standard states “transmission of the ACK frame shall commence after a SIFS period, without regard to the busy/idle state of the medium”; that is, the ACK sender does not listen first for an idle network. Give a scenario in which station A has just finished transmitting a packet to station C, and C would fail to transmit its ACK frame in the absence of this rule (due to interference from a third station B), but with the rule would disregard the interference and transmit anyway. Hint: this is another example of the hidden-node problem, 22.214.171.124 Hidden-Node Problem, with station C again the “middle” station.
4.5.♢ Give an example of a three-sender hidden-node collision (126.96.36.199 Hidden-Node Problem); that is, three nodes A, B and C, no two of which can see one another, where all can reach a fourth node D. Can you do this for more than three sending nodes?
5.0. Suppose the average contention interval in a Wi-Fi network (802.11g) is 64 SlotTimes. The average packet size is 1 KB, and the data rate is 54 Mbps. At that data rate, it takes about (8×1024)/54 = 151 µsec to transmit a packet.
6.0. WiMAX and LTE subscriber stations are not expected to hear one another at all. For Wi-Fi non-access-point stations in an infrastructure (access-point) setting, on the other hand, listening to other non-access-point transmissions is encouraged.
7.0. Suppose WiMAX subscriber stations can be moving, at speeds of up to 33 meters/sec (the maximum allowed under 802.16e).
8.0. [SM90] contained a proposal for sending IP packets over ATM as N cells as in AAL-5, followed by one cell containing the XOR of all the previous cells. This way, the receiver can recover from the loss of any one cell. Suppose N=20 here; with the SM90 mechanism, each packet would require 21 cells to transmit; that is, we always send 5% more. Suppose the cell loss-rate is p (presumably very small). If we send 20 cells without the SM90 mechanism, we have a probability of about 20p that any one cell will be lost, and we will have to retransmit the entire 20 again. This gives an average retransmission amount of about 20p extra packets. For what value of p do the with-SM90 and the without-SM90 approaches involve about the same total number of cell transmissions?
9.0. In the example in 3.4 Virtual Circuits, give the VCI table for switch S5.
10.0. Suppose we have the following network:
A───S1────────S2───B │ │ │ │ │ │ C───S3────────S4───D
The virtual-circuit switching tables are below. Ports are identified by the node at the other end. Identify all the connections. Give the path for each connection and the VCI on each link of the path.
10.5♢ We have the same network as the previous exercise:
A───S1────────S2───B │ │ │ │ │ │ C───S3────────S4───D
The virtual-circuit switching tables are below. Ports are identified by the node at the other end. Identify all the connections. Give the path for each connection and the VCI on each link of the path.
11.0. Suppose we have the following network:
A───S1────────S2───B │ │ │ │ │ │ C───S3────────S4───D
Give virtual-circuit switching tables for the following connections. Route via a shortest path.
12.0. Below is a set of switches S1 through S4. Define VCI-table entries so the virtual circuit from A to B follows the path
A ⟶ S1 ⟶ S2 ⟶ S4 ⟶ S3 ⟶ S1 ⟶ S2 ⟶ S4 ⟶ S3 ⟶ B
That is, each switch is visited twice.
A──S1─────S2 │ │ │ │ B──S3─────S4
13.0. In this exercise we outline the two-ray ground model of wireless transmission in which the signal power is inversely proportional to the fourth power of the distance, rather than following the usual inverse-square law. Some familiarity with trigonometric (or complex-exponential) manipulations is necessary.
Suppose the signal near the transmitter is A sin(2𝜋ft), where A is the amplitude, f the frequency and t the time. Signal power is proportional to A2. At distance r≥1, the amplitude is reduced by a factor of 1/r (so the power is reduced by 1/r2) and the signal is delayed by a time r/c, where c is the speed of light, giving
(A/r)sin(2𝜋f(t − r/c)) = (A/r)sin(2𝜋ft − 2𝜋𝜆r)
where 𝜆 = f/c is the wavelength.
The received signal is the superposition of the line-of-sight signal path and its reflection from the ground, as in the following diagram:
Sender and receiver are shown at equal heights above the ground, for simplicity. We assume 100% ground reflectivity (this is reasonable for very shallow angles). The phase of the ground signal is reversed 180° by the reflection, and then is delayed slightly more by the slightly longer path.
(a). Find a formula for the length of the reflected-signal path rʹ, in terms of r and h. Eliminate the square root, using the approximation (1+x)1/2 ≃ 1 + x/2 for small x. (You will need to factor r out of the square-root expression for rʹ first.)
(b). Simplify the difference (because of the 180° reflection phase-reversal) of the line-of-sight and reflected-signal paths. Use the approximation sin(X) − sin(Y) = 2 sin((X−Y)/2) cos((X+Y)/2) ≃ (X-Y) cos((X+Y)/2) ≃ (X−Y) cos(X), for X≃Y (or else use complex exponentials, noting sin(X) is the real part of i eiX). You may assume rʹ−r is smaller than the wavelength 𝜆. Start with (A/r)sin(2𝜋ft − 2𝜋𝜆r) − (A/rʹ)sin(2𝜋ft − 2𝜋𝜆rʹ); it helps to isolate the r→rʹ change to one subexpression at a time by writing this as follows (adding and subtracting the identical middle terms):
((A/r)sin(2𝜋ft − 2𝜋𝜆r) − (A/rʹ)sin(2𝜋ft − 2𝜋𝜆r)) + ((A/rʹ)sin(2𝜋ft − 2𝜋𝜆r) − (A/rʹ)sin(2𝜋ft − 2𝜋𝜆rʹ))= (A/r − A/rʹ)sin(2𝜋ft − 2𝜋𝜆r) + (A/rʹ)(sin(2𝜋ft − 2𝜋𝜆r) − sin(2𝜋ft − 2𝜋𝜆rʹ))
(c). Show that the approximate amplitude of this difference is proportional to 1/r2, making the relative power proportional to 1/r4.