Bez tytułu slajdu

Metody dostępu do medium

transmisyjnego

Dowolna stacja może rozpocząć transmisję w sieci tylko wtedy,

gdy medium nie jest zajęte przez inną transmisję.

Mechanizm kontrolujący stan medium i uruchamiania transmisji

nazywamy

metodą dostępu do medium

metodą dostępu do medium.

Protokoły LAN wykorzystują jedną z dwóch metod dostępu do

medium:

CSMA/CD

CSMA/CD (ang. Carrier Sense Multiple Access Collision Detect) -

wielodostęp z rozpoznaniem stanu kanału i wykrywaniem kolizji.
W metodzie tej stacje sieciowe konkurują między sobą o dostęp
do medium. Przykładami tej technologii są: Ethernet, IEEE 802.3
i 100Base-T.

Token Passing

Token Passing (ang. Token Passing) - wielodostęp z

przekazywaniem uprawnień. W metodzie tej stacje sieciowe
uzyskują dostęp do medium w zależności od tego, gdzie
aktualnie znajduje się token (specjalna ramka sterująca).
Przykładami technologii sieciowych, w których stosuje się
metodę dostępu Token Passing, są Token-Ring (IEEE 802.5) i
FDDI.

LAN Transmission Techniques

Baseband LANs

Broadband
LANs

Baseband LANs are single channel (digital in nature),
supporting a single communication at a time.

Broadband LANs are multichannel (analog in nature),
supporting diferent channels to communication at a time

LAN transmission techniques are divided into two categories:

Modem

Broadband
Transmissio
n

Baseband
Transmissio
n

In the

broadband technique

a modem

is used to transform the digital signal

(from a transmitting device) into a high frequency analog signal

  A broadband LAN uses analog technology,
      in which high frequency modems operating at or
above 4 kHz
      place carrier signals onto the transmission medium
  The carrier signals are then modifed:
      a process known as

modulation

      Other modems connected to a broadband LAN
reconvert
      the analog signal block into its original digital
format:
      a process known as

demodulation

 The most modulation method used on broadband
LANs
is a

frequency shift keying (FSK),

      in which two diferent frequencies are used,
      one to represent a binary "1„
      and other frequency to represent a binary "0"

Broadband Techniques

Baseband Techniques

 In the baseband technique, the digital signal from a
transmitting device
is directly introduced into the transmission medium
(after encoding).



Unipolar encoding

has two voltage states with one of the states

being 0 volts



Bipolar encoding

is symmetrical around 0 volts



Return-to-Zero (RZ)

is a technique in which the signal returns

to zero
in the middle of the bit period (not at the end of the bit)



Non-Return-to-Zero (NRZ)

is a technique in which the signal

does not return to zero
in the middle of the bit period



There are diferent line encoding techniques:

Unipolar
Return-to-Zero

Bipolar
Return-to-Zero

Unipolar
Non-Return-to-Zero

Bipolar
Non-Return-to-Zero

Baseband Techniques



Non-Return-to-Zero (NRZ) is the simplest technique:

      - NRZ uses the presence and absence of voltage (or positive
and negative voltage)
        to represent 1s and 0s
      - Without timing, the sending and receiving stations will not
be able to recognize
        how many bits are actually being transmitted when a
consecutive 1s or 0s are sent
        (protocol must specify a timing mechanism)
      - NRZ code requires only half the bandwidth required by the
Manchester code

  Because LAN transmissions are intermittent in nature
      and cannot be used to provide a constant source of clocking,
      variation on NRZ were developed, known as

Manchester and Diferential Manchester

       - IEEE 802.3 standard species the use of Manchester encoding for Ethernet LANs
         operating at data rates up to 10 Mbps
       - IEEE 802.5 standard species the use of Diferential Manchester encoding
          for Token Ring LANs

Manchester Encoding

There are two opposing conventions for the
representations of data:

  I.   The frst of these was frst published by G.E. Thomas
        and is followed by some authors (e.g., A. Leon-Garcia
and I. Widjaja)
         - a binary

"1"

is represented by the voltage transition

from high to low

- a binary

"0"

is represented by the voltage transition

from low to high

  II.  The second one is also followed by diferent authors
(e.g., W. Stallings)
         as well as by IEEE standards
          - a binary

"1"

is represented by the voltage transition

from low to high

- a binary

"0"

is represented by the voltage transition

from high to low

II.

Diferential Manchester Encoding

- a binary

"1"

is indicated by making the frst half of the signal

equal
to the last half of the previous bit's signal
i.e.,

no transition at the start of the bit period

- a binary

"0"

is indicated by making the frst half of the signal

opposite to the second half of the previous bit's signal
i.e.,

a zero bit is indicated by the voltage transition at the

beginning of the bit period

in the middle of a bit period there is always a transition,

whether from high to low, or from low to high

  A problem with polar encoding (as Manchester)
      is that an error in polarity can cause all 0s to be detected as 1s
and all 1s as 0s
  The problem can be avoided by using diferential encoding (as
Diferential Manchester),
      since only the presence of a transition is important, while polarity
is not
   Manchester and Diferential Manchester ensure frequent line
voltage transitions,
      directly proportional to the clock rate (this helps clock recovery)

Diferential Manchester Encoding

Binary encoding

Manchester encoding

Diferential
Manchester encoding

Access Methods

Fixed

Toke

Hybrid

Rando

FDMA

TDM

CDMA

Hidden

Open-ended

Polling

Carrier Sense

ALOHA

Other

Slotted

Ring

Register

Insertion

Ring

CSMA/CD

CSMA

CSMA/C

ACCESS CONTROL TO THE MEDIUM

 TDMA - Time Division Multiple Access

(time slots are reserved for stations that want to transmit A -> C, B -> D)

 FDMA - Frequency Division Multiple Access

(diferent RF carriers are reserved for stations that want to transmit)

 CDMA (Code Division Multiple Access)

(N orthogonal Pseudo-Random Sequences (PRS) => N channels)

ACCESS CONTROL TO THE MEDIUM

Random access

 The access to the medium is made without bandwidth or time slot reservation

 Used in Ethernet networks under the name CSMA/CD



ALOHA -

frst random access method used in a data radio network.

(stations send without testing if the medium is free)


CSMA

- Carrier Sense Multiple Access

(station tries to send when the bus is free)


CSMA/CD

- Carrier Sense Multiple Access with Collision Detection

(station tries to send when the medium is free,
must detect if a collision occurs and retransmit after collisions)


CSMA/CA

- Carrier Sense Multiple Access with Collision Avoidance

(station that have seen a free medium has to wait a random time
before sending)

ALOHA

(transmission procedure)



ALOHA is the basis of all non-deterministic (random) access methods.

     The ALOHA protocol was originally developed for communication between islands
    (University of Hawaï) using radio channels at low bit rates.
  ALOHA protocol requires acknowledgements and timers.
     If a packet is lost („collisions occur”) then source has to retransmit;
     the retransmission strategy is not specifed.
  The maximum utilization can be proven to be 18% („pure” ALOHA).
      This is assuming an ideal retransmission policy (no collisions).

i = 1
while (i  maxAttempts) do

send

packet

wait for acknowledgement or timeout
if

ack

received then leave

wait for random time
increment i
end do

Central

node

Host

Pure (Unslotted) ALOHA

Users are not synchronized.

Each user transmits a data packet when ready.

In the event of two or more packets collide (overlap
in time), „each user involved realized this” and
retransmit the packet after a randomized delay.



packet needs transmission is sended without awaiting for

beginning of slot
 collision probability includes two overlapping intervals:

packet sent at

collide with other packets sent in [

+ 1

]

Slotted ALOHA

Like Pure-ALOHA with additional requirements:

channel is slotted in time
each user is required to synchronize the start of

packet transmission to coincide with the slot boundary

(only complete collision would occur, avoid partial

collision)

  time is divided into equal size slots (= packet transmission  time)
  node which has a new arriving packet, transmits its at beginning of next slot
  if collision: retransmit packet in future slots with probability

, until successful.

Success (S),

Collision (C),

Empty (E) slots

S S

•

Divide time into slots “T”

•  A station can begin transmission only at the beginning of a slot
•  Collision probability is reduced
•  Success rate  S = G e

-G

(Slotted Aloha)

whereas S = G e

-2G

(Pure Aloha)

G - trafic measured as average frames generated per slot
S - average successful frames sent successfully slot

Slotted vs. Pure ALOHA

P (success by given node) =
P (node transmits) x

P (no other node transmits in [t

-1, t

]

x P (no other node transmits in [t

, t

+1]

= p

(1-p)

(N-1) .

(1-p)

(N-1)

P (success by any of N nodes) = N p

(1-p)

(N-1).

(1-p)

(N-1)

… choosing optimum p as N   ...

= 1/(2e) = 0.18

Pure Aloha Efficiency

At best:

channel use for useful transmissions

18% of time!

Suppose N stations have packets to send

(each transmits in slot with probability p)

Probability successful transmission S is:

by single node:

S= p (1-p)

(N-1)

by any of N nodes

= N p (1-p)

(N-1)

… choosing optimum p as N





...

= 1/e = 0.37

as N





At best:

channel use for useful transmissions

37% of time!

Slotted Aloha Efficiency

S =

Probability of success of any of the N nodes (i.e. only

one transmits)

= N p (1-p)

(N-1)

Solution:

Setting ds/dp = 0, we get

N (1-p)

(N-1) _

N p (N-1) (1-p)

(N-2)

= 0 ,



p =

1/N

Putting this value “p” in S and taking limits

we get

S = 1/e

Lim





 





Derivation of Slotted Aloha efficiency

Performance Comparison

• Pure ALOHA
– Max. occurs at

G = 0.5

, for which S = 1/2e =

0.184

• Slotted ALOHA
– Max. occurs at

G = 1.0

, for which S = 1/e =

0.368

O,5

0,184

0,368

 Propagation delay is small compared to frame transmission time.

 Avoid collision by listening to the carrier before transmission.

Carrier Sense Multiple Access (CSMA)

CSMA (listen before transmit):

If channel sensed idle  transmit packet
If channel sensed busy  defer

transmission

Collisions can occur:

Propagation delay means
two nodes may not yet hear
each other’s transmission

Note:

Role of distance and

propagation delay

in determining collision

probability.

- B sense channel idle  start to transmit packet

- D sense channel idle  start to transmit packet

Carrier Sense Multiple Access (CSMA)



1-persistent:

the station listens before sending.

If the channel is busy, it waits until it idle. Transmit when the
channel is idle.


non-persistent:

if busy, the station does not continually sense.

Instead, waiting for a random period, then repeating the
algorithm


p-persistent:

it applies to slotted channel. If it is idle, it transmits

with probability of p.

Family of CSMA protocols:

1-persistent

(stations

are most aggressive)

non-persistent

(stations

are not aggressive)

p-persistent

(persistence

depends

on probability p)

CSMA / CD (carrier sense – deferrer transm. as in CSMA):

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

(IEEE 802.3 uses 1-persistent CSMA algorithm)

Collision detection:

easy in wired LANs: compare transmitted and received signals
dificult in wireless LANs: receiver shut of while transmitting

CSMA/CD

(Carrier Sense Multiple Access / Collision Detection)

Minimize the period of collision

i = 1

while

(i <= maxAttempts)

                   listen until channel is idle
                   transmit and listen
                   wait until (end of transmission) or (collision detected)

collision detected

then

stop transmitting and instead sends jam bits (32 bits)

else

                                      wait for interframe delay
                                      leave
                   wait random time
                   increment i

end do

 if the channel is idle  then transmit
 if the channel is busy  then continue to listen

      until idle then transmit immediately
   if a collision is detected during the transmission,
      immediately cease transmitting the frame
      and transmit a jamming signal
      to ensure everyone knows the collision
      (hence the name

Collision Detection - CD)

   after transmitting the jamming signal,
      then wait a random time
      and attempt to transmit again

CSMA/CD
(Rules)

Procedure:

Collision
Detection

„A” begins transmission

„B” begins transmission

„B” detects collision,
stops transmitting

„A” detects collision,
stops transmitting

CSMA/CD Performance

Media Type

Propagation Propagation Propagation
speed

delay (500 m) delay

(2500 m)

Coax (10BASE5)

0.77 c

2,16 s

10,80 s

Coax (10BASE2)

0.65 c

2,56 s

12,80 s

Twisted Pair (10BASE-T)

0.585 c

2,85 s

14,25 s

Frame

transmission
time:

(1518 bytes)

(8 bits / bytes) / 10 Mbps = 1 214.4μs

Propagation delay (T) on the medium

c - velocity of propagation = 300 000 km/s

The length of frame: (64 – 1518) bytes

CSMA / CD (Collision Detection)



A senses idle
channel,

starts

transmitting



shortly before T,

B senses idle

channel,

starts

transmitting



B senses collision,

continues to

transmit

the jam signal

(32-bit)



A senses collision,

continues to

transmit

the jam signal

Random retransmission interval

r = random (0, 2 - 1)
k = min (10, AttemptNb)

Procedure:

slot time

Round trip time limits the interval during which collisions may occur:

Round trip time  51.2 s

(transmission of 512 bits = 64B)



InterFrame Gap (IFG) – min. idle period between
transmission of frames



Minimum interframe gap is 96 bit:  9 600 ns for 10 Mb/s

Ethernet

 960 ns for 100

Mb/s Ethernet

 96 ns for 1

Gb/s Ethernet

Min. frame length (64 bytes)  take into account frame header



data feld  46 bytes

Original standard specifes: – max. length of the segment: 500m
– max. number of repeaters: 4 (we can have 5 segments)
This means that the signal can travel 2500 m (12,5 s),

take into account return trip we have =

25 s

(2 x 12.5

s)

The above

25 s

estimate does not take the repeaters delay, interface delay, ….

Assume the added delay is 25 s,

then total delay



50 s

Collision Backof Scheme (discussion)

Retransmission attempts

I. The following outcomes are equally likely
during the I retransmission:

(0,0),

i.e., station A picks slot 0 and station B also picks slot 0,

(0,1),

i.e., station A picks slot 0 and station B picks slot 1,

(1,0),

i.e., station A picks slot 1 and station B picks slot 0,

(1,1),

i.e., station A picks slot 1 and station B also picks slot 1.

II. The following outcomes are during II retrans.:

(0,0),

(0,1), (0,2), (0,3)

(1,0),

(1,1),

(1,2), (1,3)

(2,0), (2,1),

(2,2),

(2,3)

(3,0), (3,1), (3,2),

(3,3)

P(c) =

1/2

P(s) =

1/2

P(c) =

1/4

P(s) =

12/1
6

III. The following outcomes are during III retrans.:

P(c) = 1/8

P(s) = 7/8

III. The following outcomes are during IV retrans.:

P(c) =

16/256

P(s) =

240/256

The probability of exactly two retransmissions is:
(prob of collision on frst retransmission) x (prob of success on second)
Pr (2) =

1/2

12/16

= 0,375

Similarly:

Pr (3) =

1/2

1/4

7/8

= 0.109,

Pr (4) =

1/2

1/4

1/8

240/256

= 0,0146

……

Finally, the average number of retransmissions is:

Collision Backof Scheme (discussion)

On average then, with two stations competing for the medium,
one will capture the medium during the second retransmission attempt.



i x (prob. of i retransmission) = (1 x 0,5)+(2 x 0,375)+(3 x 0,109)+(4 x 0,0146)+ …=

= 0,5 + 0,75 + 0,327 + 0,058 + … = 1,635

Non-persistent

• idle ⇒ transmit

• busy ⇒ wait random time and repeat

1-persistent

• idle    ⇒ transmit
• busy  ⇒ wait until idle then transmit immediately

(Note that if 2 or more stations are waiting to transmit,

a collision is guaranteed)

p-persistent *

• idle  ⇒ transmit with probability p
               and delay one time unit with probability 1-p;

(time unit is typically the maximum propagation delay)

• busy ⇒ continue to listen until channel is idle
and repeat above for idle
• delayed one time unit ⇒ repeat above for idle

Choice of p (

need to avoid instability under heavy load):

- If N stations are waiting to send, the expected number transmitting is „Np

> 1” ⇒ collision is likely.

(all stations waiting to transmit, permanent collisions, no throughput ⇒

network will collapse)

- Thus „Np” must be < 1;
(but heavy load means p must be small, for example p <

0,1

and time will be wasted even on a lightly loaded line).

The IEEE 802.3 standard specifies the 1-persistent scheme.

Persistency scheme

CSMA

CSMA/CD

Suppose both stations decide
to transmit frame in time 0 – 2,2 s.

With no collision detection,
both will continue to transmit
for the entire frame time.
Time (over 1200 s ) will be wasted.

Collision Detection (CD) solves this problem;
The stations stop transmitting
when they sense collision and they implement
a binary exponential backof scheme.
The collision detection scheme will minimize
wasted resources.

CSMA vs. CSMA/CD

(transmission procedure)

i = 1
while (i  maxAttempts) do

listen until channel idle

send

packet

            wait for acknowledgement or timeout

            if

ack

received then leave

wait random time
increment i
end do

CSMA protocol requires

that stations be able to monitor

whether the channel is idle or busy

(no requirements to detect collisions).

i = 1
while (i  maxAttempts) do

listen until channel idle

send

packet

and listen

wait until

(end of transmission)

or (collision detected)

if collision detected then

                       stop transmitting (after 32 bits - ”jam”)
            else
                        wait for interframe delay

then leave

wait random time

increment i
end do

CSMA/CD protocol requires,

that a sending station monitors the channel

and detects a collision.

(collision is detected within a propagation round

trip)

CSMA

CSMA/CD

CSMA/CD performance

Max. utilization for CSMA/CD (Ethernet) –
approximation:

 

( 1 + C  )

where:



= (2



R) / L



= propagation delay,

R = bit rate,
L = frame size
C is a constant:

= 3.1 is a pessimistic value;

= 2.5 is an approximate value based on simulations

For example if (2



R) = 60 B:

- for trafic with small frames (L = 64 bytes), the utilization is less than 30 %.

- for large frames

(L = 1500 Bytes),

the utilization is around 90%.



0,5

0,1

0,05 0,0

0,001



24% 39% 76% 87% 97

99,6



29% 44% 80% 89% 98

99,8

where: m (frame length [s]) = L /R

Throughput
S
for diferent



For good performance,  should be

<= 0,01

CSMA vs. CSMA/CD

Max. throughput is roughly indirectly proportional to :

  2

/m = (2

R) / L

 = 0,01 or 0,1

„Taking Turns” MAC protocols

Channel partitioning MAC protocols:

share channel  eficiently at high load
ineficient at low load  delay in channel access

Random access MAC protocols

eficient at low load  single node can fully utilize channel
high load  collision overhead

“Taking turns” protocols:

Polling:

 master node “invites” slave nodes
to transmit in turn
 concerns:

- polling overhead
- latency
- single point of failure (master)

Token passing:

  control token passed from
one node
     to next sequentially
  token message concerns:

- token overhead
- latency
- single point of failure
(token)

Reservation Protocols

Reservation protocol:

time divided into slots
begins with N short reservation slots

reservation slot time equal to channel end-end propagation
delay
station with message to send posts reservation
reservation seen by all stations

after reservation slots, message transmissions ordered by known
priority

Token Passing Active Monitor

Node 1

Node 3

Node 2

Node 4

Token Ring

token

Active
Monitor

Standby monitor

Standby
monitor

Standby monitor

R, data rate of channel (bps)
d, maximum distance between any pair of stations
V, velocity of propagation (m/s)
L, frame length (bits)
a = maximum normalized propagation delay

As the number of stations N becomes very large, S has a

maximum possible value:

max

= 1, a < 1

max

= 1/a, a > 1





The assume that LAN has N active stations
and each station is always prepared to transmit frame,
normalized system throughputs may be expressed as:

Token Passing - Performance

where T1= average time to transmit a data frame

T2 = average time to pass a token

Token Ring Performance

a = propagation time around ring

(normalized)
1 = frame time (normalized)

Case 1: a < 1

Case 1: a > 1

t= 0: F

rame begins

around ring

Time

t=a: Start of frame

reaches around ring

t=1: Station fnishes

transmission, releases token

t=1+a/N: Token

gets to next station

t = 0: F

rame begins

around ring

Time

t =1: Station fnishes

transmission, releases token

t =a+a/N: Token

gets to next station

t =a: Start of frame

reaches around ring,

station releases token

Token Ring Performance



When a station wishes to transmit, it must wait for the token and seize the token

       - change one bit in token which transforms it into a “start-of-frame sequence”
         and appends frame for transmission.
      - station claims token by removing it from the ring.


The data frame circles the ring and is removed by the transmitting station.

 Each station interrogates passing frame.
If destined for station, it copies the frame into local bufer.

Token operation

single-token:

insert token after last bit of busy token is received and the last bit of the

frame is transmitted.

single-frame:

insert token after the last bit of the frame has returned to the sending

station.

multi-token:

insert token after station has completed transmission of the last bit of the

frame.

Performance

is determined by

whether more than one frame is allowed on the ring at the same

time

and the relative propagation time.

multi-token:

insert token after station has completed transmission of the last bit of the

frame.

single-token:

insert token after last bit of busy token is received and the last bit of the

frame is transmitted.

single-frame:

insert token after the last bit of the frame has returned to the sending

station.

Performance

is determined by

whether more than one frame is allowed on the ring at the same

time

and the relative propagation time.

Token Insertion Choices

Single frame operation

(a) Low Latency Ring (T

= 90, T

= 400)

t = 0,

A begins frame

t = 90,

return of

first bit

t = 400,

transmit

last bit

t = 490,

reinsert

token

(b) High Latency Ring (T

= 840, T

= 400)

t = 0,

A begins frame

t = 400,

last bit of frame

enters ring

t = 840,

return of first

bit

t = 1240,

reinsert

token

Single token operation

(a) Low Latency Ring (T

= 90, T

= 400)

t = 0,

A begins frame

t = 90,

return of first

bit

t = 210,

return of

header

t = 400,

last bit enters

ring, reinsert

token

(b) High Latency Ring (T

= 840, T

= 400)

t = 0,

A begins frame

t = 400,

transmit last

bit

t = 840,

arrival first

frame bit

t = 960,

reinsert token

Slotted Ring

  Cambridge Ring : University of Cambridge
  Each slot has token bit to indicate
     the slot as empty or full.
  A station with data to send,
     waits until an empty slot arrives,
     marks the slot full and inserts a frame of data.
  The station cannot transmit another frame
     until this slot returns

DATA

Data

S T

Ack

1b 1b 1b 8b 8b 16b 2b 1b

Each slot:

To/From node local trafic

Frame received
from upstream
nodes

Register Insertion Ring

RSR – Receive Serial Register
TSR – Transmit Serial Register

Fram
e

Frame
transmitted
to downstream
nodes

OUT

RSR

TSR

Summary of MAC protocols

What can we do with a shared media?

Channel Partitioning, by time, frequency or code

Time Division, Code Division, Frequency

Division

Random partitioning

ALOHA, S-ALOHA,
CSMA,
CSMA/CD

Detemined partitioning

token passing,
polling from a central node,
reservation protocol,
slotted ring,
register insertion ring

Three general MAC techniques exist for use within networks:

1. Contention:
    There is no regulating mechanism directly to govern stations attempting
    to access a medium. Two or more stations may contend for the medium
    and any multiple simultaneous accesses are resolved as they arise.

2. Token passing:
    A single token exists within the network and is passed between stations in turn.
    Only a station holding the token may use the medium for transmission.
    This eliminates multiple simultaneous accesses of the medium
    with the attendant risk of collision.

3. Slotted and register insertion rings:
Similar in principle to token passing, but a unique time interval is granted
to a station for transmission.

Access to medium (summary)

Document Outline