Thursday, December 18, 2014

Differentiated Services


Flow-based algorithms have the potential to offer good quality of service to one or more flows
because they reserve whatever resources are needed along the route. However, they also have
a downside. They require an advance setup to establish each flow, something that does not
scale well when there are thousands or millions of flows. Also, they maintain internal per-flow
state in the routers, making them vulnerable to router crashes.
Finally, the changes required
to the router code are substantial and involve complex router-to-router exchanges for setting
up the flows. As a consequence, few implementations of RSVP or anything like it exist yet.

For these reasons, IETF has also devised a simpler approach to quality of service, one that can
be largely implemented locally in each router without advance setup and without having the
whole path involved. This approach is known as class-based (as opposed to flow-based)
quality of service. IETF has standardized an architecture for it, called differentiated services,
which is described in RFCs 2474, 2475, and numerous others. We will now describe it.

Differentiated services (DS) can be offered by a set of routers forming an administrative
domain (e.g., an ISP or a telco). The administration defines a set of service classes with
corresponding forwarding rules. If a customer signs up for DS, customer packets entering the
domain may carry a Type of Service field in them, with better service provided to some classes
(e.g., premium service) than to others. Traffic within a class may be required to conform to
some specific shape, such as a leaky bucket with some specified drain rate. An operator with a
nose for business might charge extra for each premium packet transported or might allow up
to N premium packets per month for a fixed additional monthly fee. Note that this scheme
requires no advance setup, no resource reservation, and no time-consuming end-to-end
negotiation for each flow, as with integrated services. This makes DS relatively easy to
implement.

Class-based service also occurs in other industries. For example, package delivery companies often offer overnight, two-day, and three-day service. Airlines offer first class, business class, and cattle class service. Long-distance trains often have multiple service classes. Even the Paris subway has two service classes. For packets, the classes may differ in terms of delay, jitter, and probability of being discarded in the event of congestion, among other possibilities (but probably not roomier Ethernet frames).

To make the difference between flow-based quality of service and class-based quality of
service clearer, consider an example: Internet telephony. With a flow-based scheme, each
telephone call gets its own resources and guarantees. With a class-based scheme, all the
telephone calls together get the resources reserved for the class telephony. These resources cannot be taken away by packets from the file transfer class or other classes, but no telephone call gets any private resources reserved for it alone.

Spanning Tree Bridges


To increase reliability, some sites use two or more bridges in parallel between pairs of LANs, as shown in Fig. 4-43. This arrangement, however, also introduces some additional problems
because it creates loops in the topology.


A simple example of these problems can be seen by observing how a frame, F, with unknown
destination is handled in Fig. 4-43. Each bridge, following the normal rules for handling
unknown destinations, uses flooding, which in this example just means copying it to LAN 2.
Shortly thereafter, bridge 1 sees F2, a frame with an unknown destination, which it copies to
LAN 1, generating F3 (not shown). Similarly, bridge 2 copies F1 to LAN 1 generating F4 (also
not shown). Bridge 1 now forwards F4 and bridge 2 copies F3. This cycle goes on forever.

The solution to this difficulty is for the bridges to communicate with each other and overlay the actual topology with a spanning tree that reaches every LAN. In effect, some potential
connections between LANs are ignored in the interest of constructing a fictitious loop-free
topology. For example, in Fig. 4-44(a) we see nine LANs interconnected by ten bridges. This configuration can be abstracted into a graph with the LANs as the nodes. An arc connects any two LANs that are connected by a bridge. The graph can be reduced to a spanning tree by
dropping the arcs shown as dotted lines in Fig. 4-44(b). Using this spanning tree, there is
exactly one path from every LAN to every other LAN. Once the bridges have agreed on the
spanning tree, all forwarding between LANs follows the spanning tree. Since there is a unique path from each source to each destination, loops are impossible.
Figure 4-44. (a) Interconnected LANs. (b) A spanning tree covering
the LANs. The dotted lines are not part of the spanning tree.


To build the spanning tree, first the bridges have to choose one bridge to be the root of the
tree. They make this choice by having each one broadcast its serial number, installed by the
manufacturer and guaranteed to be unique worldwide. The bridge with the lowest serial
number becomes the root. Next, a tree of shortest paths from the root to every bridge and
LAN is constructed. This tree is the spanning tree. If a bridge or LAN fails, a new one is
computed.

The result of this algorithm is that a unique path is established from every LAN to the root and thus to every other LAN. Although the tree spans all the LANs, not all the bridges are
necessarily present in the tree (to prevent loops). Even after the spanning tree has been
established, the algorithm continues to run during normal operation in order to automatically
detect topology changes and update the tree. The distributed algorithm used for constructing
the spanning tree was invented by Radia Perlman and is described in detail in (Perlman, 2000). It is standardized in IEEE 802.1D.

Local Internetworking


The previous section dealt with the problems encountered in connecting two different IEEE 802
LANs via a single bridge. However, in large organizations with many LANs, just interconnecting
them all raises a variety of issues, even if they are all just Ethernet. Ideally, it should be
possible to go out and buy bridges designed to the IEEE standard,
plug the connectors into the
bridges, and everything should work perfectly, instantly. There should be no hardware changes
required, no software changes required, no setting of address switches, no downloading of
routing tables or parameters, nothing. Just plug in the cables and walk away. Furthermore, the
operation of the existing LANs should not be affected by the bridges at all. In other words, the
bridges should be completely transparent (invisible to all the hardware and software).
Surprisingly enough, this is actually possible. Let us now take a look at how this magic is
accomplished.

In its simplest form, a transparent bridge operates in promiscuous mode, accepting every
frame transmitted on all the LANs to which it is attached. As an example, consider the
configuration of Fig. 4-42. Bridge B1 is connected to LANs 1 and 2, and bridge B2 is connected to LANs 2, 3, and 4. A frame arriving at bridge B1 on LAN 1 destined for A can be discarded
immediately, because it is already on the correct LAN, but a frame arriving on LAN 1 for C or F must be forwarded.


When a frame arrives, a bridge must decide whether to discard or forward it, and if the latter, on which LAN to put the frame. This decision is made by looking up the destination address in a big (hash) table inside the bridge. The table can list each possible destination and tell which output line (LAN) it belongs on. For example, B2's table would list A as belonging to LAN 2, since all B2 has to know is which LAN to put frames for A on. That, in fact, more forwarding happens later is not of interest to it.

When the bridges are first plugged in, all the hash tables are empty. None of the bridges know
where any of the destinations are, so they use a flooding algorithm: every incoming frame for
an unknown destination is output on all the LANs to which the bridge is connected except the
one it arrived on. As time goes on, the bridges learn where destinations are, as described
below. Once a destination is known, frames destined for it are put on only the proper LAN and
are not flooded.

The algorithm used by the transparent bridges is backward learning.As mentioned above, the bridges operate in promiscuous mode, so they see every frame sent on any of their LANs. By looking at the source address, they can tell which machine is accessible on which LAN. For example, if bridge B1 in Fig. 4-42 sees a frame on LAN 2 coming from C, it knows that C must be reachable via LAN 2, so it makes an entry in its hash table noting that frames going to C should use LAN 2. Any subsequent frame addressed to C coming in on LAN 1 will be forwarded, but a frame for C coming in on LAN 2 will be discarded.

The topology can change as machines and bridges are powered up and down and moved
around. To handle dynamic topologies, whenever a hash table entry is made, the arrival time of the frame is noted in the entry. Whenever a frame whose source is already in the table arrives, its entry is updated with the current time. Thus, the time associated with every entry tells the last time a frame from that machine was seen.

Periodically, a process in the bridge scans the hash table and purges all entries more than a
few minutes old. In this way, if a computer is unplugged from its LAN, moved around the
building, and plugged in again somewhere else, within a few minutes it will be back in normal
operation, without any manual intervention. This algorithm also means that if a machine is
quiet for a few minutes, any traffic sent to it will have to be flooded until it next sends a frame
itself.

The routing procedure for an incoming frame depends on the LAN it arrives on (the source LAN) and the LAN its destination is on (the destination LAN), as follows:

1.  If destination and source LANs are the same, discard the frame.
2.  If the destination and source LANs are different, forward the frame.
3.  If the destination LAN is unknown, use flooding.

As each frame arrives, this algorithm must be applied. Special-purpose VLSI chips do the lookup and update the table entry, all in a few microseconds.


Comparison of 802.11 with 802.16


At this point you may be thinking: Why devise a new standard? Why not just use 802.11?
There are some very good reasons for not using 802.11, primarily because 802.11 and 802.16 solve different problems. Before getting into the technology of 802.16, it is probably
worthwhile saying a few words about why a new standard is needed at all.


The environments in which 802.11 and 802.16 operate are similar in some ways, primarily in
that they were designed to provide high-bandwidth wireless communications. But they also
differ in some major ways. To start with, 802.16 provides service to buildings, and buildings
are not mobile. They do not migrate from cell to cell often. Much of 802.11 deals with mobility,
and none of that is relevant here. Next, buildings can have more than one computer in them, a
complication that does not occur when the end station is a single notebook computer. Because
building owners are generally willing to spend much more money for communication gear than
are notebook owners, better radios are available. This difference means that 802.16 can use
full-duplex communication, something 802.11 avoids to keep the cost of the radios low.

Because 802.16 runs over part of a city, the distances involved can be several kilometers, which means that the perceived power at the base station can vary widely from station to station. This variation affects the signal-to-noise ratio, which, in, turn, dictates multiple
modulation schemes. Also, open communication over a city means that security and privacy are essential and mandatory.

Furthermore, each cell is likely to have many more users than will a typical 802.11 cell, and
these users are expected to use more bandwidth than will a typical 802.11 user. After all it is
rare for a company to invite 50 employees to show up in a room with their laptops to see if
they can saturate the 802.11 wireless network by watching 50 separate movies at once. For
this reason, more spectrum is needed than the ISM bands can provide, forcing 802.16 to
operate in the much higher 10-to-66 GHz frequency range, the only place unused spectrum is
still available.

But these millimeter waves have different physical properties than the longer waves in the ISM bands, which in turn requires a completely different physical layer. One property that
millimeter waves have is that they are strongly absorbed by water (especially rain, but to
some extent also by snow, hail, and with a bit of bad luck, heavy fog). Consequently, error
handling is more important than in an indoor environment. Millimeter waves can be focused
into directional beams (802.11 is omnidirectional), so choices made in 802.11 relating to
multipath propagation are moot here.

Another issue is quality of service. While 802.11 provides some support for real-time traffic
(using PCF mode), it was not really designed for telephony and heavy-duty multimedia usage. In contrast, 802.16 is expected to support these applications completely because it is intended for residential as well as business use.

In short, 802.11 was designed to be mobile Ethernet, whereas 802.16 was designed to be wireless, but stationary, cable television. These differences are so big that the resulting standards are very different as they try to optimize different things.

A very brief comparison with the cellular phone system is also worthwhile. With mobile phones, we are talking about narrow-band, voice-oriented, low-powered, mobile stations that
communicate using medium-length microwaves. Nobody watches high-resolution, two-hour
movies on GSM mobile phones (yet). Even UMTS has little hope of changing this situation. In short, the wireless MAN world is far more demanding than is the mobile phone world, so a
completely different system is needed. Whether 802.16 could be used for mobile devices in the future is an interesting question. It was not optimized for them, but the possibility is there. For the moment it is focused on fixed wireless.

Services


The 802.11 standard states that each conformant wireless LAN must provide nine services.
These services are divided into two categories: five distribution services and four station
services. The distribution services relate to managing cell membership and interacting with
stations outside the cell. In contrast, the station services relate to activity within a single cell.


The five distribution services are provided by the base stations and deal with station mobility as they enter and leave cells, attaching themselves to and detaching themselves from base stations. They are as follows.

1.  Association. This service is used by mobile stations to connect themselves to base
stations. Typically, it is used just after a station moves within the radio range of the
base station. Upon arrival, it announces its identity and capabilities. The capabilities
include the data rates supported, need for PCF services (i.e., polling), and power
management requirements. The base station may accept or reject the mobile station. If the mobile station is accepted, it must then authenticate itself.
2.  Disassociation. Either the station or the base station may disassociate, thus breaking
the relationship. A station should use this service before shutting down or leaving, but
the base station may also use it before going down for maintenance.
3.  Reassociation. A station may change its preferred base station using this service. This
facility is useful for mobile stations moving from one cell to another. If it is used
correctly, no data will be lost as a consequence of the handover. (But 802.11, like
Ethernet, is just a best-efforts service.)
4.  Distribution. This service determines how to route frames sent to the base station. If
the destination is local to the base station, the frames can be sent out directly over the
air. Otherwise, they will have to be forwarded over the wired network.
5.  Integration. If a frame needs to be sent through a non-802.11 network with a
different addressing scheme or frame format, this service handles the translation from the 802.11 format to the format required by the destination network.






The remaining four services are intracell (i.e., relate to actions within a single cell). They are used after association has taken place and are as follows.

1.  Authentication. Because wireless communication can easily be sent or received by
unauthorized stations, a station must authenticate itself before it is permitted to send
data. After a mobile station has been associated by the base station (i.e., accepted into
its cell), the base station sends a special challenge frame to it to see if the mobile
station knows the secret key (password) that has been assigned to it. It proves its
knowledge of the secret key by encrypting the challenge frame and sending it back to
the base station. If the result is correct, the mobile is fully enrolled in the cell. In the
initial standard, the base station does not have to prove its identity to the mobile
station, but work to repair this defect in the standard is underway.
2.  Deauthentication. When a previously authenticated station wants to leave the
network, it is deauthenticated. After deauthentication, it may no longer use the
network.
3.  Privacy. For information sent over a wireless LAN to be kept confidential, it must be
encrypted. This service manages the encryption and decryption. The encryption
algorithm specified is RC4, invented by Ronald Rivest of M.I.T.
4.  Data delivery. Finally, data transmission is what it is all about, so 802.11 naturally
provides a way to transmit and receive data. Since 802.11 is modeled on Ethernet and transmission over Ethernet is not guaranteed to be 100% reliable, transmission over 802.11 is not guaranteed to be reliable either. Higher layers must deal with detecting and correcting errors.

An 802.11 cell has some parameters that can be inspected and, in some cases, adjusted. They relate to encryption, timeout intervals, data rates, beacon frequency, and so on.
Wireless LANs based on 802.11 are starting to be deployed in office buildings, airports, hotels,
restaurants, and campuses around the world. Rapid growth is expected. For some experience about the widespread deployment of 802.11 at CMU, see (Hills, 2001).

Broadband Wireless


We have been indoors too long. Let us now go outside and see if any interesting networking is going on there. It turns out that quite a bit is going on there, and some of it has to do with the so-called last mile. With the deregulation of the telephone system in many countries,
competitors to the entrenched telephone company are now often allowed to offer local voice and high-speed Internet service.
There is certainly plenty of demand. The problem is that
running fiber, coax, or even category 5 twisted pair to millions of homes and businesses is
prohibitively expensive. What is a competitor to do?

The answer is broadband wireless. Erecting a big antenna on a hill just outside of town and
installing antennas directed at it on customers' roofs is much easier and cheaper than digging
trenches and stringing cables. Thus, competing telecommunication companies have a great
interest in providing a multimegabit wireless communication service for voice, Internet, movies
on demand, etc. As we saw in Fig. 2-30, LMDS was invented for this purpose. However, until
recently, every carrier devised its own system. This lack of standards meant that hardware and
software could not be mass produced, which kept prices high and acceptance low.

Many people in the industry realized that having a broadband wireless standard was the key
element missing, so IEEE was asked to form a committee composed of people from key
companies and academia to draw up the standard. The next number available in the 802
numbering space was 802.16, so the standard got this number. Work was started in July
1999, and the final standard was approved in April 2002. Officially the standard is called ''Air
Interface for Fixed Broadband Wireless Access Systems.'' However, some people prefer to call






it a wireless MAN (Metropolitan Area Network) or a wireless local loop. We regard all these terms as interchangeable.

Like some of the other 802 standards, 802.16 was heavily influenced by the OSI model,
including the (sub)layers, terminology, service primitives, and more. Unfortunately, also like
OSI, it is fairly complicated. In the following sections we will give a brief description of some of the highlights of 802.16, but this treatment is far from complete and leaves out many details. For additional information about broadband wireless in general, see (Bolcskei et al., 2001; and Webb, 2001). For information about 802.16 in particular, see (Eklund et al., 2002).

The Physical Layer


In this chapter we will look at the lowest layer depicted in the hierarchy of Fig. 1-24. It defines the mechanical, electrical, and timing interfaces to the network. We will begin with a theoretical analysis of data transmission, only to discover that Mother (Parent?) Nature puts some limits on what can be sent over a channel.


Then we will cover three kinds of transmission media: guided (copper wire and fiber optics), wireless (terrestrial radio), and satellite. This material will provide background information on the key transmission technologies used in modern networks.

The remainder of the chapter will be devoted to three examples of communication systems used in practice for wide area computer networks: the (fixed) telephone system, the mobile phone system, and the cable television system.  All  three  use  fiber  optics  in  the  backbone,  but  they  are  organized  differently  and  use  different technologies for the last mile.

The Theoretical Basis for Data Communication

Information can be transmitted on wires by varying some physical property such as voltage or current. By
representing the value of this voltage or current as a single-valued function of time, f(t), we can model the
behavior of the signal and analyze it mathematically. This analysis is the subject of the following sections.

Fourier Analysis

In the early 19th century, the French mathematician Jean-Baptiste Fourier proved that any reasonably behaved
periodic function, g(t) with period T can be constructed as the sum of a (possibly infinite) number of sines and
cosines:


where f = 1/T is the fundamental frequency, an and bn are the sine and cosine amplitudes of the nth harmonics (terms), and c is a constant. Such a decomposition is called a Fourier series. From the Fourier series, the function can be reconstructed; that is, if the period, T, is known and the amplitudes are given, the original function of time can be found by performing the sums of Eq. (2-1).

A data signal that has a finite duration (which all of them do) can be handled by just imagining that it repeats the entire pattern over and over forever (i.e., the interval from T to 2T is the same as from 0 to T, etc.).

The an amplitudes can be computed for any given g(t) by multiplying both sides of Eq. (2-1) by sin(2pkft) and then integrating from 0 to T. Since only one term of the summation survives: an. The bn summation vanishes completely. Similarly, by multiplying Eq. (2-1) by cos(2pkft) and integrating between 0 and T, we can derive bn. By just integrating both sides of the equation as it stands, we can find c. The results of performing these operations are as follows:

 Bandwidth-Limited Signals

To see what all this has to do with data communication, let us consider a specific example: the transmission of the ASCII character ''b'' encoded in an 8-bit byte. The bit pattern that is to be transmitted is 01100010. The lefthand part of Fig. 2-1(a) shows the voltage output by the transmitting computer. The Fourier analysis of this signal yields the coefficients:

Figure 2-1. (a)  A  binary  signal  and  its  root-mean-square  Fourier  amplitudes. (b)-(e)  Successive
approximations to the original signal.

The root-mean-square amplitudes, , for the first few terms are shown on the right-hand side of Fig. 2-
1(a). These values are of interest because their squares are proportional to the energy transmitted at the corresponding frequency.

No  transmission  facility  can  transmit  signals  without  losing  some  power  in  the  process.  If  all  the  Fourier components were equally diminished, the resulting signal would be reduced in amplitude but not distorted [i.e., it would have the same nice squared-off shape as Fig. 2-1(a)]. Unfortunately, all transmission facilities diminish different  Fourier components  by  different  amounts,  thus  introducing  distortion. Usually, the amplitudes  are transmitted  undiminished  from  0  up  to  some  frequency  fc  [measured  in  cycles/sec  or  Hertz  (Hz)] with  all frequencies above this cutoff frequency attenuated. The range of frequencies transmitted without being strongly attenuated is called the bandwidth. In practice, the cutoff is not really sharp, so often the quoted bandwidth is from 0 to the frequency at which half the power gets through.

The bandwidth is a physical property of the transmission medium and usually depends on the construction,
thickness, and length of the medium. In some cases a filter is introduced into the circuit to limit the amount of
bandwidth available to each customer. For example, a telephone wire may have a bandwidth of 1 MHz for short
distances, but telephone companies add a filter restricting each customer to about 3100 Hz. This bandwidth is
adequate for intelligible speech and improves system-wide efficiency by limiting resource usage by customers.

Now let us consider how the signal of Fig. 2-1(a) would look if the bandwidth were so low that only the lowest
frequencies were transmitted [i.e., if the function were being approximated by the first few terms of Eq. (2-1)].
Figure 2-1(b) shows the signal that results from a channel that allows only the first harmonic (the fundamental, f)
to pass through. Similarly, Fig. 2-1(c)-(e) show the spectra and reconstructed functions for higher-bandwidth
channels.

Given a bit rate of b bits/sec, the time required to send 8 bits (for example) 1 bit at a time is 8/b sec, so the frequency of the first harmonic is b/8 Hz. An ordinary telephone line, often called a voice-grade line, has an artificially-introduced cutoff frequency just above 3000 Hz. This restriction means that the number of the highest harmonic passed through is roughly 3000/(b/8) or 24,000/b, (the cutoff is not sharp).

For some data rates, the numbers work out as shown in Fig. 2-2. From these numbers, it is clear that trying to send at 9600 bps over a voice-grade telephone line will transform Fig. 2-1(a) into something looking like Fig. 2-
1(c), making accurate reception of the original binary bit stream tricky. It should be obvious that at data rates much higher than  38.4 kbps, there is no hope at all for binary signals, even if the transmission facility is completely noiseless. In other words, limiting the bandwidth limits the data rate, even for perfect channels. However, sophisticated coding schemes that make use of several voltage levels do exist and can achieve higher data rates. We will discuss these later in this chapter.