Multiplexing Techniques

Contents 1. 2. 3. 4. 5. 6. 7. 8. 9.

Overview Multiple Access Protocols Multiplexing Techniques TDMA FDMA CDMA SDMA Others Example of GSM 1

Multiple Access protocols ❒ single shared communication channel ❒ two or more simultaneous transmissions by nodes:

interference ❍

❒

only one node can send successfully at a time

multiple access protocol: ❍

❍ ❍

distributed algorithm that determines how stations share channel, i.e., determine when station can transmit communication about channel sharing must use channel itself! what to look for in multiple access protocols: • synchronous or asynchronous • information needed about other stations • robustness (e.g., to channel errors) • performance 2

Ideal Multiple Access Protocol Broadcast channel of rate R bps 1. When one node wants to transmit, it can send at rate R. 2. When M nodes want to transmit, each can send at average rate R/M 3. Fully decentralized: ❍ ❍

no special node to coordinate transmissions no synchronization of clocks, slots

4. Simple

3

MAC Protocols: a taxonomy Three broad classes: ❒ Channel Partitioning ❍

❍

TDMA, FDMA, CDMA

divide channel into smaller “pieces” (time slots, frequency) allocate piece to node for exclusive use

❒ Random Access

ALOHA, CSMA, CSMA/CD, CSMA/CA

allow collisions ❍ “recover” from collisions ❒ “Taking turns” Polling, Token passing ❍

❍

tightly coordinate shared access to avoid collisions

Goal: efficient, fair, simple, decentralized 4

Channel Partitioning MAC protocols: TDMA TDMA: time division multiple access ❒ access to channel in "rounds" ❒ each station gets fixed length slot (length = pkt

trans time) in each round ❒ unused slots go idle ❒ example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle

5

Channel Partitioning MAC protocols: FDMA FDMA: frequency division multiple access ❒ channel spectrum divided into frequency bands ❒ each station assigned fixed frequency band ❒ unused transmission time in frequency bands go idle ❒ example: 6-station LAN, 1,3,4 have pkt, frequency

frequency bands

bands 2,5,6 idle

time

6

Channel Partitioning (CDMA) CDMA (Code Division Multiple Access) ❒ unique “code” assigned to each user; i.e., code set partitioning ❒ used mostly in wireless broadcast channels (cellular, satellite, ❒ ❒ ❒ ❒

etc) all users share same frequency, but each user has own “chipping” sequence (i.e., code) to encode data encoded signal = (original data) X (chipping sequence) decoding: inner-product of encoded signal and chipping sequence allows multiple users to “coexist” and transmit simultaneously with minimal interference (if codes are “orthogonal”)

7

CDMA Encode/Decode

8

CDMA: two-sender interference

9

Random Access Protocols ❒ When node has packet to send ❍ transmit at full channel data rate R. ❍ no a priori coordination among nodes ❒ two or more transmitting nodes -> “collision”, ❒ random access MAC protocol specifies: ❍ how to detect collisions ❍ how to recover from collisions (e.g., via delayed retransmissions) ❒ Examples of random access MAC protocols: ❍ slotted ALOHA ❍ ALOHA ❍ CSMA, CSMA/CD, CSMA/CA 10

Slotted Aloha ❒ time is divided into equal size slots (= pkt trans. time) ❒ node with new arriving pkt: transmit at beginning of

next slot ❒ if collision: retransmit pkt in future slots with probability p, until successful.

Success (S), Collision (C), Empty (E) slots 11

Slotted ALOHA Assumptions ❒ all frames same size ❒ time is divided into equal size slots, time to transmit 1 frame ❒ nodes start to transmit frames only at beginning of slots ❒ nodes are synchronized ❒ if 2 or more nodes transmit in slot, all nodes detect collision

Operation ❒ when node obtains fresh frame, it transmits in next slot ❒ no collision, node can send new frame in next slot ❒ if collision, node retransmits frame in each subsequent slot with prob. p until success

12

Slotted ALOHA

Pros ❒ single active node can continuously transmit at full rate of channel ❒ highly decentralized: only slots in nodes need to be in sync ❒ simple

Cons ❒ collisions, wasting slots ❒ idle slots ❒ nodes may be able to detect collision in less than time to transmit packet 13

Slotted Aloha efficiency Efficiency is the long-run fraction of successful slots when there’s many nodes, each with many frames to send ❒ Suppose N nodes with many frames to send, each transmits in slot with probability p ❒ prob that 1st node has success in a slot = p(1-p)N-1

❒ prob that any node has a success = Np(1-p)N-1

❒ For max efficiency

with N nodes, find p* that maximizes Np(1-p)N-1 ❒ For many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives 1/e = .37

At best: channel used for useful transmissions 37% of time! 14

Pure (unslotted) ALOHA ❒ unslotted Aloha: simpler, no synchronization ❒ when frame first arrives ❍ transmit immediately ❒ collision probability increases: ❍ frame sent at t0 collides with other frames sent in [t0-1,t0+1]

15

Pure Aloha efficiency P(success by given node) = P(node transmits) . P(no other node transmits in [p0-1,p0] . P(no other node transmits in [p0-1,p0] = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1)

… choosing optimum p and then letting n -> infty ...

Even worse !

= 1/(2e) = .18

16

CSMA: (Carrier Sense Multiple Access) CSMA: listen before transmit: ❒ If channel sensed idle: transmit entire pkt

If collision occurs has to retransmit again ❒ If channel sensed busy, defer transmission ❍ P-Persistent CSMA: (for slotted channels) retry immediately with probability p when channel becomes idle (may cause instability) ❍ Non-persistent CSMA: (for nonslotted channels) retry after random interval ❒ human analogy: don’t interrupt others! ❍

17

CSMA collisions

spatial layout of nodes along ethernet

collisions can occur:

propagation delay means two nodes may not hear each other’ transmission

collision:

entire packet transmission time wasted

note:

role of distance and propagation delay in determining collision prob. 18

CSMA/CD (Collision Detection) CSMA/CD: carrier sensing, deferral as in CSMA collisions detected within short time ❍ colliding transmissions aborted, reducing channel wastage ❍

❒ collision detection: ❍ easy in wired LANs: measure signal strengths, compare transmitted, received signals ❍ difficult in wireless LANs: receiver shut off while transmitting ❒ human analogy: the polite conversationalist 19

CSMA/CD collision detection

20

“Taking Turns” MAC protocols channel partitioning MAC protocols: ❍ share channel efficiently and fairly at high load ❍ inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node! Random access MAC protocols ❍ efficient at low load: single node can fully utilize channel ❍ high load: collision overhead “taking turns” protocols look for best of both worlds! 21

“Taking Turns” MAC protocols Token passing: Polling: ❒ control token passed from ❒ master node one node to next “invites” slave nodes sequentially. to transmit in turn ❒ token message ❒ concerns: ❒ concerns: ❍ polling overhead ❍ ❍

latency single point of failure (master)

❍ ❍ ❍

token overhead latency single point of failure (token)

22

Frame Relay (more) flags address

data

CRC

flags

❒ Flag bits, 01111110, delimit frame ❒ address:

10 bit VC ID field ❍ 3 congestion control bits • FECN: forward explicit congestion notification (frame experienced congestion on path) • BECN: congestion on reverse path • DE: discard eligibility ❍

23

Frame Relay -VC Rate Control ❒ Committed Information Rate (CIR)

defined, “guaranteed” for each VC ❍ negotiated at VC set up time ❍ customer pays based on CIR ❍

❒ DE bit: Discard Eligibility bit

Edge FR switch measures traffic rate for each VC; marks DE bit ❍ DE = 0: high priority, rate compliant frame; deliver at “all costs” ❍ DE = 1: low priority, eligible for congestion discard ❍

24

Frame Relay - CIR & Frame Marking ❒ Access Rate: rate R of the access link between

source router (customer) and edge FR switch (provider); 64Kbps < R < 1,544Kbps ❒ Typically, many VCs (one per destination router) multiplexed on the same access trunk; each VC has own CIR ❒ Edge FR switch measures traffic rate for each VC; it marks (i.e. DE = 1) frames which exceed CIR (these may be later dropped) ❒ Internet’s more recent differentiated service uses similar ideas 25

Example: GSM ❒ Frequency Band ❍ 935-960, 890-915 MHz ❍ Two pieces of 25 MHz band (same as AMPS) ❒ AMPS has 833 user channels ❒ How about GSM?

26

Different Generations ❒ 1G ❍ analog ❒ 2G ❍ digital ❒ 3G ❍ higher data rate for multimedia applications

27

1G Cellular Systems ❒ Many Different Standards: ❍ AMPS (US) ❍ NMT (Northern Europe) ❍ TACS (Europe) ❍ NTT (Japan) ❍ many others... ❒ Spectrum ❍

around 800 and 900 MHz

28

2G Cellular Systems ❒ Four Major Standards: ❍ GSM (European) ❍ IS-54 (later becomes IS-136, US) ❍ JDC (Japanese Digital Cellular) ❍ IS-95 (CDMA, US)

29

Frequency Division Duplex (FDD) Forward Link mobile Reverse Link

base station

Two separate frequency bands are used for forward and reverse links. Typically, 25 MHz in each direction. AMPS: 824-849 MHz (forward) 869-894 MHz (reverse) 30

Frequency Division Multiple Access (FDMA) ❒ The spectrum of each link (forward or reverse)

frequency bands

is further divided into frequency bands ❒ Each station assigned fixed frequency band

idle

idle idle 31

Number of User Channels in AMPS ❒ Bandwidth allocated to each user in each link

(forward or reverse) is 30 KHz.

❒ No. of user channels

= Total bandwidth / user bandwidth = 25 MHz / 30 kHz = 833 ❒ Is it enough?

32

Frequency Reuse Radio coverage, called a cell.

f f

The same frequency can be reused in different cells, if they are far away from each other 33

Cellular Architecture MS – Mobile Station BSC – Base Station Controller MSC – Mobile Switching Center PSTN – Public Switched Telephone Network

MS BSC

MSC

PSTN

segmentation of the area into cells

34

Time Division Multiple Access (TDMA) ❒ The mobile users access the channel in round-

robin fashion. ❒ Each station gets one slot in each round.

Slots 2, 5 and 6 are idle 35

FDMA/TDMA, example GSM f 960 MHz

124

200 kHz

1

935.2 MHz

20 MHz

915 MHz

124

1

890.2 MHz

t 1 2 3

7 8

Each freq. carrier is divided into 8 time slots. 36

Number of channels in GSM ❒ Freq. Carrier: 200 kHz ❒ TDMA: 8 time slots per freq carrier ❒ No. of carriers = 25 MHz / 200 kHz

= 125 ❒ No. of user channels = 125 * 8 = 1000

37

Capacity Comparison ❒ Reuse factor ❍ 7 for AMPS ❍ 3 for GSM

(why smaller reuse factor?)

❒ What’s the capacity of GSM relative to AMPS?

A. one half of AMPS C. 3 times larger

B. the same D. 10 times larger

38

Answer ❒ AMPS ❍ reuse factor = 7 ❍ no. of users / cell = 833 / 7 = 119 ❒ GSM ❍ reuse factor = 3 ❍ no. of users / cell = 1000 / 3 = 333 ❍ almost 3 times larger than AMPS!

39

Multiple Access Methods Three major types: Frequency Division Multiple Access (FDMA) ❍ Time Division Multiple Access (TDMA) ❍ Code Division Multiple Access (CDMA) ❍

• Frequency hopping (FH-CDMA) • Direct sequence (DS-CDMA)

40

Frequency-Time Plane Frequency

Partition of signal space into time slots and frequency bands

Time 41

FDMA Frequency

Different users transmit at different frequency bands simultaneously.

Time

42

TDMA Frequency

Different users transmit at different time slots. Each user occupy the whole freq. spectrum.

Time

43

Frequency Hopping CDMA Frequency At each successive time slot, the frequency band assignments are reordered. Each user employs a code that dictates the frequency hopping pattern. Time 44

Synchronization ❒ The previous figure implies that each signal

synchronizes with each of the other signals. ❒ In practice, this is not the case. ❒ Frequency hops may collide, but it does not occur frequently. ❍

How often collisions occur depends on the choice of codes.

45

Direct Sequence CDMA Frequency All users occupy the whole bandwidth all the time. Signals of different users overlap with one other. How can it be done? Time

46

CDMA Encoding ❒ Each user is assigned a unique signature

sequence (or code), denoted by (c1,c2,…, cM). Its component is called a chip.

di, is encoded by multiplying the bit by the signature sequence: Zi,m = di cm

❒ Each bit,

47

Encoding Example ❒ Data bit

d1 = –1 ❒ Signature sequence

(c1,c2,…,c8)

= (+1,+1,+1,–1,+1,–1,–1,–1)

❒ Encoder Output

(Z1,1,Z1,2,…,Z1,8) = (–1,–1,–1,+1,–1,+1,+1,+1)

48

Bandwidth ❒ Note that the chip rate is much higher

than the data rate. ❒ Consider our previous example.

Suppose the original data signal occupies a bandwidth of W. ❍ What is the bandwidth of the encoded signal? ❍

49

Spread Spectrum Technique Frequency

Frequency

Encoding

Time

Time

The bandwidth expands by a factor of M. M is called spreading factor or processing gain. 50

CDMA Decoding ❒ Without interfering users, the receiver

would receive the encoded bits, Zi,m , and recover the original data bit, di, by computing:

1 di = M

M

∑Z m =1

c

i ,m m

51

CDMA Decoding Example (c1,c2,…,c8)

= (+1,+1,+1,–1,+1,–1,–1,–1)

(Z1,1,Z1,2,…,Z1,8) = (–1,–1,–1,+1,–1,+1,+1,+1) multiply (–1,–1,–1,–1,–1,–1,–1,–1)

di = –1

add and divide by M

52

53

Multiuser Scenario N users, the signal at the receiver becomes:

❒ If there are

N

Z i*,m = ∑ Z in,m n =1

❒

How can a CDMA receiver recover a user’s original data bit?

54

2-user example

Multiplied by the signature sequence of user 1

55

Signature Sequences ❒ In order for the receiver to be able to

extract out a particular sender’s signal, the CDMA codes must be of low correlation. ❒ Correlation of two codes, (cj,1,…, cj,M) and (ck,1,…, ck,M) , are defined by inner product:

1 M

M

∑c m =1

c

j ,m k ,m

56

The Meaning of Correlation ❒ What is correlation? ❍ It determines how much similarity one sequence has with another. ❍ It is defined with a range between –1 and 1. Correlation Value

Interpretation

1

The two sequences match each other exactly.

0

No relation between the two sequences

–1

The two sequences are mirror images of each other. Other values indicate a partial degree of correlation. 57

Generation of Signature Sequences ❒ How to generate signature sequences of

low correlation?

❒ There are two classes of signature

sequences that are widely used in CDMA systems. Orthogonal Codes ❍ Pseudo Noise Sequences (PN Sequences) ❍

58

Orthogonal Codes ❒ Two codes are said to be orthogonal if

their correlation is zero. ❍

no interference between the two users.

❒ In our previous two-user example, the

codes are orthogonal. ❒ How to generate orthogonal codes?

59

Walsh Codes ❒ The most common orthogonal codes used in

CDMA systems. ❒ A set of Walsh codes of length n is defined by the rows of an n × n Hadamard matrix. ❒ Hadamard matrix can be constructed by an iterative method.

60

Iterative Construction H1 = ( 0 )

H 2n

 H n −1 =   H n −1

H n −1   H n −1 

❒ Example:

0 0  H 2 =  0 1

0  0 H4 =  0  0 

0 1 0 1

0 0 1 1

0  1 1  0  61

Signature Sequences ❒ The signature sequences can be found by ❍ Taking the rows out ❍ Replacing 0 by –1

 0 0  H 2 =   0 1

s1 = (− 1,− 1) s2 = (− 1,+ 1) Are they orthogonal?

62

IS-95 Forward Link ❒ Walsh Codes of length 64 is used for

spreading in the forward link (base-tomobile) of IS-95.

❒ It is NOT suitable for the reverse link

(mobile-to-base). (Why?) ❍

PN sequences are used instead.

63

PN Sequences ❒ What is Pseudo-Noise Sequences? ❍ They are deterministic. ❍ But they look like random noise. ❒ How to generate PN sequences? ❍ One common way is to use linear feedback shift register.

64

Shift Register Implementation: An Example x1

x2

x3

Initial state: 1 0 0 Output: 0 0 1 0 1 1 1 … (Periodic with period 7) The output sequence must be periodic (why?) The period cannot be greater than 7. (why?)

x1

x2

x3

Output

1

0

0

---

0

1

0

0

1

0

1

0

1

1

0

1

1

1

1

0

0

1

1

1

0

0

1

1

1

0

0

1 65

2.2 Multiple Access protocols ❒ single shared communication channel ❒ two or more simultaneous transmissions by nodes: interference

only one node can send successfully at a time ❒ multiple access protocol: ❍ distributed algorithm that determines how stations share channel, i.e., determine when station can transmit ❍ communication about channel sharing must use channel itself! ❍ type of protocols: • synchronous or asynchronous • information needed about other stations • robustness (e.g., to channel errors) • performance ❍

66

2.3 Multiple Access Control Protocols Three broad classes: ❒ Channel Partitioning ❍ divide channel into smaller “pieces” (time slots, frequency, code) ❍ allocate piece to node for exclusive use ❍ TDMA, FDMA, CDMA ❒ Random Access ❍ allow collisions ❍ “recover” from collisions ❍ CSMA, ALOHA ❒ Taking turns ❍ tightly coordinate shared access to avoid collisions ❍ Token ring

Goal: efficient, fair, simple, decentralized 67

2.4 Random Access protocols When node has packet to send ❍ transmit at full channel data rate R. ❍ no a priori coordination among nodes ❒ two or more transmitting nodes -> “collision”, ❒ random access MAC protocol specifies: ❍ how to detect collisions ❍ how to recover from collisions (e.g., via delayed retransmissions) ❒ Examples of random access MAC protocols: ❍ slotted ALOHA ❍ ALOHA ❍ CSMA and CSMA/CD ❒

68

2.5 CSMA: Carrier Sense Multiple Access CSMA: listen before transmit: ❒ If channel sensed idle: transmit entire pkt ❒ If channel sensed busy, defer transmission ❒ human analogy: don’t interrupt others!

69

2.6 CSMA/CD (Collision Detection) CSMA/CD: carrier sensing, deferral as in CSMA ❍ ❍ ❍

collisions detected within short time colliding transmissions aborted, reducing channel wastage persistent or non-persistent retransmission

❒ collision detection: ❍

❍

easy in wired LANs: measure signal strengths, compare transmitted, received signals difficult in wireless LANs: receiver shut off while transmitting

❒ human analogy: the polite conversationalist

70

CSMA/CD collision detection

71

Thank You

72