Switching and Multiplexing
Switching and multiplexing are both techniques we use to make communication more economical and scaleable.
Switching
Fully connected networks don't scale well, but you still need to let any possible pair of nodes communicate.
Switching is the idea that you can dynamically configure a network which is less than fully connected in order to join any two nodes for communication.
Two ways to switch: you can
establish your own dedicated path (circuit switching) or you can take whatever
path is available at the time you send data (packet switching).
Circuit switching
Circuit switching maintains the idea of dedicated connections between two
end points, but allows for sharing of channels within the network, and
hence is much more scaleable. Circuit switching takes advantage of the
fact that while everybody needs to be able to talk to everybody else, they
aren't likely to all do so at the same time.
The telephone network is based on circuit switching. To make a phone
call you ask the PSTN to establish a dedicated circuit for you. It does
this by finding unused channels all along the way through the network and
dedicates them to your call. When you actually start exchanging data (talking)
all of your data follows the same path or circuit through the network.
If you pause in your conversation the circuit you're using is idle, wasting
bandwidth. But you never lose data because you have a guaranteed, reserved
circuit, so it is impossible for the system to be too busy to handle your
data.
<picture of switches and circuits>
Pros
Guarantee of performance through dedication of resources.
Messages all follow same route, preserving ordering and (perhaps) intermessage
timing.
No buffering in the switches (data flows continuously).
Cons
Wasted resources due to idle, dedicated resources.
Potentially large set-up time (round trip time) could be unacceptable
for short message exchange.
If part of the circuit (link or switch) fails your connection is lost.
Poorly matched to bursty traffice since it reserves a fixed amount
of capacity.
Circuit routing fixed so can't adapt to changes in network.
Usually assumes symmetrical traffic flows for full-duplex channels.
Questions
Telephone network assumes symmetrical traffic, i.e. the same amount
of data flows in either direction. How well does this assumption hold when
you're using a modem from home?
Alternatives to circuit switching are message switching (store and forward)
and packet switching.
Message Switching
Message switching is the way (at the high level, at least) that USENET
articles are distributed. Each article is sent in its entirety from one
news host to another before the next article is sent. During the time that
an article is in transit no other article can be sent. The potentially
large size of messages means that the routers can be busy for long periods
handling one message, and the messages take a lot of storage.
Packet Switching
Packet switching alleviates the problems of circuit and message switching.
A small upper bound is put on the maximum size of a packet sent through
the network. No reserved channel is created ahead of time. Each packet
belonging to a single message may take a different route through the network.
Since there is no reservation of capacity it is possible that congestion
becomes a problem. Too many packets trying to get through the same router
requires that the router be able to buffer packets. All buffers have finite
size, so it is possible that packets are dropped.
<figure showing routers and queues in packet switched network>
Pros
No set-up time.
No assumption of symmetrical traffic flow for full-duplex.
No wasted resources due to dedicated, idle resources.
Good match to bursty traffic.
Potenial for more robust, adaptive behavior in the event of a down
link or router.
Routing algorithm can adapt route per packet based on network loading.
Cons
Congestion is possible in routers - lost packets.
Packets may be re-ordered by network.
Time spent in each router deciding which path to take.
Each packet has to carry more information with it so it can be routed.
Router must buffer as packets are sent store-and-forward style.
See ATM Switching for a continued discussion
of switching.
Multiplexing
Long distance links use high capacity point-to-point connections with a
single physical medium. Some means must be found of sharing the capacity
to enable multiple simultaneous uses of the medium. The motivation is the
same here as for time shared operating systems (one expensive resource
shared by many people). Think of the links between the regional phone switches.
What is the relationship between switching and multiplexing?
Multiplexing divides a fat pipe into independently useable portions.
Switching could be done without multiplexing, but since the point of switching
is to share a network with fewer links than the fully-connected network,
it is quite likely these few links will be fat and multiplexing will be
used.
There are three ways to divide (and hence share) a channel: time, frequency,
code.
Frequency Division Multiplexing
Possible when a single source requires less than the total available bandwidth
in the medium.
Frequency modulation lets data be moved to any particular part of the
frequency spectrum of the channel. Multiple sources can thus share the
same medium, by using different parts of the channel simultaneously.
FDM allows for full duplex modems, radio, and TV.
Carrier frequency is what shifts the spectrum of a channel
Individual TV signal also an example of FDM
-
one side-band of the 4MHz signal
-
separate color carrier and audio carrier
-
total is 6MHz
<figure 2-24, block diagram of FDM>
Example: telephone system trunks
Remember how thick the 2100 TP cable was? Imagine that crossing the
country (where many more than 2100 simultaneous conversations are possible).
Microwave radio and co-axial cable are used (since they have greater
bandwidth)
Multiplexing must obviously be done.
12 voice channels (4KHz each) form a Group (48KHz at 60kHz)
5 Groups (60 voice channels) form a Supergroup (240KHz at 312kHz)
10 Supergroups (600 voice channels) form a Mastergroup (2.52MHz at
564kHz)
...
(10,800 voice channels) form a jumbogroup multiplex
Many levels of modulation/demodulation can result in distortion.
Wave Division Multiplexing
Just FDM in the context of optical fibers. Better because no interference
properties of light.
Time Division Multiplexing
If the data rate of a medium is larger than the data rate (bps) of a source
channel, then multiple channels can be sent by allotting different channels
different slices of time. Multitasking in an OS is TDM of the CPU.
The multiple channels can be interleaved by bit, byte, or frame.
Synchronous TDM refers to the fact that a time slot is reserved for
each source
-
this allows for a guaranteed portion of the data rate to go to each channel
-
(important for sending things like voice and video)
-
has the potential to waste data capacity (if the source doesn't need its
slot)
-
sources need not all be the same speed
The issues of link control (flow, error control) are handled per channel,
independent of the TDM
Example: TDM Carrier System
Example: Cogent MANs
US-wide switched LAN network. Two regional rings (fiber, 1 Tbps), one for east and one for west coast, interconnect city-wide MANs.
Cogent sells Fast Ethernet to OC192 (10 Gbps) services for amazing rates (flat 1000 USD for 100 Mbps). Speeds and distance creates the possibility of treating the Cogent MAN like a LAN, sharing software, doing video conferencing, etc, even between cities.
DWDM allows for high data rates out of the fiber loops. Each fiber is of course TDM'd with packets of data.
Customers are companies located in large buildings. Eight or so large buildings are served by a single loop using DWDM; the loop is attached to the backbone. Each customer is assigned (dedicated) a single wavelength of light. This means QoS is not an issue, as there is no interaction amongst users of the network.
Economics: cherry-pick big customers in big cities, charge a flat rate to avoid large billing and customer service support.
Statistical TDM
Tries to reduce the wasted capacity which is inevitable with TDM when not
all channels have data during every slot.
A statistical multiplexer can support many more devices given the same
data rate
The design of a stat TDM depends on the expected utilization of each
channel
Potential problem: peak load could exceed capacity, since design is
statistical Buffers must be provided to soak up the extra bits when over
capacity.
CDMA Code Division Multiple Access
References
GSM uses TDM and FDM to divide the channel and dedicate time/space to a
user. The whole point is to avoid multiple stations transmitting on the
same frequency at the same time. An alternative strategy is to use spread
spectrum techniques so collisions aren't a problem. All conversations use
all the available bandwidth at the same time.
Divide each bit interval into smaller units called chips. Real schemes
use 64 or 128 chips per bit. Each chip is one of two signals (i.e. it is
a binary digital signal).
Each station is given a unique m bit chip sequence. When the station
wants to transmit a 1 bit, it sends the m bit sequence. When it wants to
transmit a 0 bit, it sends the complement of its m bit sequence.
If you want to communicate b bits, then you must signal b*m chips
So a seemingly crazy thing has been done. If you want to communicate b
bits/sec, you must signal b*m bits/sec. The signalling data rate is higher
yet the communication rate is the same. A higher signalling rate obviously
requires greater bandwidth in the channel. Instead of using FDM and limiting
each conversation to one discrete part of the total spectrum, you allow
all conversations to use the entire allocated frequency spectrum.
Here's an example using a 1 MHz bandwidth channel centered at 1000 MHz.
Three different strategies will be used to share this channel among 100
simultaneous conversations.
FDM strategy
100 channels via FDM gives you 10kHz per channel <frequency domain
picture>
Assuming perfect electronics, each conversation is given a 10kHz subchannel.
With a signalling/encoding scheme of 1 bit/Hz each subchannel yields
10k bps.
TDM strategy
The 1Mz channel with a signalling/encoding scheme of 1 bit/Hz yields
1M bps.
This could be divided into 100 bit frames transmitted every 1/10,000
of a second (10k frames/sec).
Ignoring framing overhead and control, each station could be allocated
1 bit of each frame, so each conversation sees a rate of 1 bit/frame *
10k frames/sec = 10k bps.
CDMA strategy
Each conversation is given entire 1 MHz channel to use <frequency
domain picture>
With the same signaling/encoding scheme of 1 bit/Hz, each conversation
now gets capacity of 1M bps.
But with CDMA the signalling rate is chips/sec, and there are m chips/bit,
so the chip rate is greater than the bit rate.
If the chips/bit, m, is equal to 100, then each station sends 1 M bps
/ 100 chips/bit = 10 k bps.
If the chips/bit, m, is less than 100, the actual data rate for each
conversation will be greater than 10k bps.
Conclusion
CDMA can be a more efficient (bits/Hz) scheme for sharing the bandwidth
than TDM or FDM.
Some means has to be found for allowing all stations to transmit simultaneously
across the entire frequency spectrum of the channel. The resulting interference
or collisions must be able to be resolved by the receiver.
Background
m = 8 chips/bit
Chip signals are shown as +1 and -1 to avoid confusion with data bits
as 0 and 1
4-16b shows chip sequences (in bipolar notation) assigned to four stations,
A, B, C and D.
notice each chip sequence is unique
Call a chip sequence S and its complement S. All chip
sequences are pair-wise orthogonal.
where in the example the S and T represent A, B, C, D.
Being pair-wise orthogonal means that when you multiply all the pairs
in two chip sequences together, pair-wise, you end up with 0. If two chips
match (+1,+1 or -1,-1) you get a 1 in the sum. If two chips are opposite
(+1,-1 or -1,+1) you get a -1 in the sum. If there are as many matches
as mis-matches, then you get a sum of 0, and the two sequences are said
to be pair-wise orthogonal.
A Walsh function generates these pair-wise orthogonal sequences. A sequence
of m bits has m unique sequences.
The pair-wise multiplication and summation, when divided by the number
of chips in each sequence, is the normalized inner product of the two sequences.
If S.T = 0 then S.T = 0 too.
The normalized inner product of any sequence with itself is 1, since
the pairs all match, the multiplications all yield 1, and you divide by
m.
The normalized inner product of any sequence with its complement is
-1, since the pairs are all opposites, the multiplications all yield -1,
and you divide by m.
How it works, Tanenbaums example in Figure 4-16
Assume all stations are synchronized, so they all transmit their chip
sequences on the same time boundaries.
When multiple stations transmit simultaneously, their bipolar chip signals
add linearly. If three stations send a +1 chip, and two stations send a
-1 chip, then the receiver ends up with +1.
4-16c shows six combinations of various stations transmitting either
0s or 1s at the same time. Don't be fooled by the picture where the bits
are shown next to each other implying time sequencing. All bits are transmitted
simultaneously. A dash means that station doesn't transmit. The right hand
side shows the resulting signal at the receiver. It is the linear combination
of the chip sequences sent by the stations A, B, C, D to transmit their
respective bits of data.
Take the fourth example, where A and C transmit 1s, and B transmits
a 0. The receiver gets a signal S which is the linear superposition
of A, C and B. Where A is the chip sequence
for A sending a 1, etc.
Suppose the receiver wants to determine what, if anything, C transmitted
during this bit interval. The receiver does the following computation
S . C = (A + B + C) . C =
A.C + B.C + C.C = 0 + 0 + 1 = 1
Seeing the result, the receiver knows that C must have transmitted a 1
data bit. The terms from A and B drop out because of the orthogonal property
of the chip sequences.
Another way to look at it is as if the receiver could receive the signals
separately (which of course it can't) and does the above operation to each
of them individually. Only the signal from C would have a non-zero result.
You can look at the receiver's operation of correlating the received
signal with the chip sequence of the sender as a means of increasing the
SNR at the receiver, rather than in the channel itself.
With an ideal, noiseless channel, there is nothing that bounds the capacity
of the channel with CDMA. You can just keep adding stations as long as
you have unused orthogonal codes, and you can increase the code length
when you need more.
With real, noisy channels you have a limit. There is also the problem
of having all the chip signals synchronized in time. GPS is used in some
systems to synchronize mobile and base stations.
Another problem is that the power in the signals is assumed to be equal.
In a wireless network that won't be the case because the stations are different
distances from the receiver. Power control is very important in CDMA.
Disadvantage over narrow band schemes
very high chip signal transmission rates (expensive transmitter/receivers)
Advantages over narrow band schemes
Capacity
"Simple models suggest that the capacity improvement may be more than
20 times that of the existing narrowband cellular standards, such as AMPS
in North America, NMT in Scandinavia, TACS in the United Kingdom." CDMA
Technology Website.
CDMA benefits in terms of interference and frequency re-use over FDM/TDM
schemes. The interference in CDMA is an average interference since all
stations use all the bandwidth of the channel. In traditional narrow band
schemes you must design for the worst case interference, where two stations
are interfering in frequency with the full power of their signals. In CDMA
stations spread there power over a large channel. Designing to this average
frequency gives greater frequecy reuse and hence capacity.