10/03/2020





Lecturer: Nguyễn Thị Thanh Vân – FIT - HCMUTE






Multiple access protocols
LAN technologies:
Ethernet
Network Devices:
o repeat, Hubs, bridges, and switches, router…






Token Ring
FDDI
ATM
WLAN

10/03/2020

2

1


10/03/2020

Two types of “links”:
 point-to-point
o PPP (point-to-point protocol) for dial-up access
o point-to-point link between Ethernet switch and host



broadcast (shared wire or medium)
o traditional Ethernet
o upstream HFC (Hybrid fiber coaxial cable)
o 802.11 wireless LAN

5: DataLink Layer




5a-3

single shared broadcast channel
two or more simultaneous transmissions by nodes:
interference
o only one node can send successfully at a time


multiple access protocol
 distributed algorithm that determines how nodes share
channel, i.e., determine when node can transmit
 communication about channel sharing must use channel
itself!
o no out-of-band channel for coordination

5: DataLink Layer

5a-4

2


10/03/2020

What to look for in multiple access protocols?
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:
o no special node to coordinate transmissions
o no synchronization of clocks, slots

4. Simple

5: DataLink Layer


5a-5

Three broad classes:
 Channel Partitioning protocols
o divide channel into smaller “pieces” (time slots, frequency, code)
o allocate piece to node for exclusive use



Random Access protocols
o channel not divided, allow collisions
o “recover” from collisions



Taking-turns protocols
o tightly coordinate shared access to avoid collisions

5: DataLink Layer

5a-6

3


10/03/2020

TDMA: time division multiple access








channel divided into N time slots, one per user
access to channel in "rounds"
each station gets fixed length slot (length = packet trans time) in each
round
unused slots go idle
inefficient with low duty cycle users and at light load
example: 6-station LAN, 1,3,4 have packets, slots 2,5,6 idle

5a-7

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 packets, frequency bands 2,5,6 idle

frequency bands



5: DataLink Layer


5a-8

4


10/03/2020



When node has packet to send
o transmit at full channel data rate R.
o no a priori coordination among nodes




two or more transmitting nodes -> “collision”,
random access MAC protocol specifies:
o how to detect collisions
o how to recover from collisions (e.g., via delayed retransmissions)



Examples of random access MAC protocols:
o slotted ALOHA
o ALOHA
o CSMA, CSMA/CD, CSMA/CA

5: DataLink Layer


Assumptions
 all frames same size
 time is divided into equal
size slots (length of a slot
equals 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 a slot, all
nodes detect collision

5a-9

Operation
 when a node has a fresh
frame to send , it transmits in
the next slot
 If no collision, the frame is
transmitted successfully
 if collision, the node
retransmits the frame in each
subsequent slot with
probability p until success

5: DataLink Layer


5a-10

5


10/03/2020

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 due to probabilistic
retransmission
 nodes may be able to detect
collision in a time interval of
length less than the time to
5a-11
transmit a packet

Efficiency is the long-run fraction of successful slots when
there are many nodes, each with many frames to send
To derive the maximum efficiency
 Modified protocol: each node attempts to transmit a fresh frame in each

slot with probability p
 Suppose N nodes with many frames to send
 Probability that 1st node has success in a slot = p(1-p)N-1
 Probability that any node has a success = Np(1-p)N-1

5: DataLink Layer

5a-12

6


10/03/2020




unslotted Aloha: simpler, no synchronization
when frame first arrives
o transmit immediately
o If collision, retransmits with probability p, or waits for another frame

With probability 1-p


collision probability increases:
o frame sent at t0 collides with other frames sent in [t0-1,t0+1]

5: DataLink Layer


5a-13

P(success by given node) = P(node transmits) .
P(no other node transmits in [t0-1, t0] .
P(no other node transmits in [t0, t0+1]
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)
… choosing optimum p and then letting n -> infinity ...
maximum efficiency



= 1/(2e) = .18

Even worse !

The use of a random-access channel in ALOHAnet led to the
development of carrier sense multiple access (CSMA), a
"listen before send" random-access protocol that can be used
when all nodes send and receive on the same channel.
5: DataLink Layer

5a-14

7


10/03/2020

CSMA: listen before transmit: The first implementation of CSMA was Ethernet

 If channel sensed idle: transmit entire frame
 If channel sensed busy, defer transmission for a random
amount of time

5a-15

collisions can still occur:
propagation delay means
two nodes may not hear
each other’s transmission

spatial layout of nodes

B transmits
D transmits

collision:
entire packet transmission
time wasted

note:
The larger the end-to-end
propagation delay, the larger the
chance that a node is not able to
sense a transmission that has
already begun at another node
5a-16

8



10/03/2020

CSMA/CD: Listen While transmit, carrier sensing, deferral
as in CSMA
o collisions detected within short time
o colliding transmissions aborted, reducing channel wastage



collision detection:
o easy in wired LANs: measure signal strengths, compare

transmitted and received signals
o difficult in wireless LANs: receiver shut off while transmitting; i.e.,
cannot transmit and receive at the same time


human analogy: the polite conversationalist

5a-17

5: DataLink Layer

5a-18

9


10/03/2020






The method used by Local Talk is called CSMA/CA (Carrier
Sense Multiple Access / Collision Avoidance).
Local Talk transmits data up to 230 kbps only.
Each Local Talk Mac or printer has its own
o Local Talk adapter to connect each other as a chain.



Two Mac computers can use a serial port instead of Local
Talk adapters.

10/03/2020

19

10/03/2020

20

10


10/03/2020

channel partitioning MAC protocols:

o share channel efficiently and fairly at high load
o inefficient at low load: 1/N bandwidth allocated even if only 1 active

node!

Random access MAC protocols
o efficient at low load: single node can fully utilize channel
o high load: collision overhead

Taking-turns protocols
look for best of both worlds!

5: DataLink Layer

Polling:
 master node “invites”
slave nodes to
transmit in turn
 concerns:
o polling delay
o single point of failure

(master)

5a-21

Token passing:
 control token passed from one
node to next sequentially.
 When a node receives a token, it

can transmits up to a maximum
number of frames
 concerns:




token overhead
latency
single point of failure (token)

5a-22

11


10/03/2020



A token:
o is a small message composed of a special bit pattern.
o represents the permission to send the data packet.

o A station is allowed to transmit a data packet if and only if it possess

the token otherwise not.


Token passing method assumeso Each station has the data to send.

o Each station sends exactly one data

packet after acquiring the token.


2 strategies are used
o Delayed Token Reinsertion
o Early Token Reinsertion

10/03/2020

Delayed Token Reinsertion
Station keeps holding the token until the
last bit of the data packet transmitted by it
takes the complete revolution of the ring
and comes back to it.


10/03/2020

23

Early Token Reinsertion
Station releases the token
immediately after putting its data
packet to be transmitted on the
ring.


24


12


10/03/2020

Token ring

Token bus
Logically organized into a ring
structure by order descending node
ID
 A node must be inserted to ring
 Some nodes may not participate


The same physical ring

10/03/2020



25

What do you do with a shared media?
o Channel Partitioning, by time, frequency or code

• Time Division, Code Division, Frequency Division
o Random partitioning (dynamic),


• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard in others (wireless)
• CSMA/CD used in Ethernet
o Taking Turns

• polling from a central site, token passing

5: DataLink Layer

5a-26

13


10/03/2020

Data link layer so far:
o services, error detection/correction, multiple access

Next: LAN technologies - Logical topology represents
the way that data travel through the computer
network.
• Ethernet
• Token Ring
• FDDI
• ATM

5: DataLink Layer




5a-27



14


10/03/2020







Ethernet is a family of computer networking technologies for wired LAN
technology
It was commercially introduced in 1980 and first standardized in 1983
(802.3)
It has largely replaced competing wired LAN technologies such as
token ring, FDDI, and ARCNET
Base Ethernet standard is 10 Mbps.
Later: 100Mbps, 1Gbps, 10Gbps

5a-29



1-1. des/src address




1-n. Des address:
o FF:FF:FF:FF:FF:FF



1-some. Des address:;
o Group address

10/03/2020

30

15


10/03/2020

Ethernet-II( DIX 2.0)
7+1

6

6

2

46-1500


4

Preamble

Dest.
Address

Source
Address

Type

Data

FCS



Preamble: used to synchronize receiver, sender clock rates pattern:
10101010 followed by one byte with pattern 10101011.



Addresses: 6 bytes
o if adapter receives frame with matching destination address, or with broadcast

address (eg ARP packet), it passes data in frame to net-layer protocol
o otherwise, adapter discards frame





Data: 46 to 1500 bytes
Type: indicates the higher layer protocol (mostly IP but others may be
supported such as Novell IPX and AppleTalk)
CRC: checked at receiver, if error is detected, the frame is simply dropped
5a-31

10/03/2020

32

16


10/03/2020




Connectionless: No handshaking between sending and
receiving adapter.
Unreliable: receiving adapter doesn’t send acks or
nacks to sending adapter
o stream of datagrams passed to network layer can have data gaps

due to discarded fames if the application is using UDP
o data gaps will be filled by retransmissions if application is using
TCP

o otherwise, application will see the gaps

5: DataLink Layer









5a-33

adapter may begin to
transmit at anytime, i.e., no
slots are used
adapter doesn’t transmit if it
senses that some other
adapter is transmitting, that
is, carrier sense
transmitting adapter aborts
when it senses that another
adapter is also transmitting,
that is, collision detection
Before attempting a
retransmission, adapter
waits a random time, that is,
random access
5a-34


17


10/03/2020

1. Adaptor receives datagram
4. If adapter detects another
from network layer and
transmission while transmitting,
creates frame
aborts and sends jam signal
2. If adapter senses channel idle, 5. After aborting, adapter enters
it starts to transmit frame.
exponential backoff: after
the nth collision, adapter
If it senses channel busy, waits
chooses a K at random from
until channel idle and then
{0,1,2,…,2m-1} where m =
transmits
min(n, 10). Adapter waits
3. If adapter transmits entire
K*512 bit times and returns to
frame without detecting
Step 2
another transmission, the
adapter is done with frame !

5a-35


Jam Signal: make sure all other
Exponential Backoff:
transmitters are aware of collision;  Goal: adapt retransmission
48 bits;
attempts to estimated current load
Bit time: 0.1 microsec for 10 Mbps
o heavy load: random wait will be
Ethernet ;
longer
for K=1023, wait time is about 50  first collision: choose K from {0,1};
msec
delay is K x 512 bit transmission
times
 after second collision: choose K
from {0,1,2,3}…
 after ten collisions, choose K from
{0,1,2,3,4,…,1023}

5a-36

18


10/03/2020






Tprop = max propagation delay between 2 nodes in LAN
ttrans = time to transmit max-size frame
Efficiency: the long-run fraction of time during which frames
are being transmitted on the channel without collisions
when there are a large number of active nodes

efficiency 




1
1  5t prop / ttrans

[Lam 1980, Bertsekas 1991]

Efficiency goes to 1 as tprop goes to 0
Goes to 1 as ttrans goes to infinity
Much better than ALOHA, but still decentralized, simple,
and cheap
5a-37

5a-38

19


10/03/2020




Media:

10BASE-F

5a-39

Đầu nối BNC-T

10/03/2020

Terminator

40

20


10/03/2020



Twisted pair: UTP and STP
o UTP: faster, popular, cheap
o Color: orange, green, blue, brown

10BASE-F

5a-41


Straight: devices having different function: Cross: devices having same functions or
 uplinks between switches.
 router to a hub or switch.
 hubs to switches or another hub.
 server to a hub or switch.
 PC to PC or a Router
 workstations to a hub or switch
 2 routers together without hub or switch
10BASE-F

Rollover: for device configuration:
 need a console cable for same.
 is connected to console port of the router/SW would
5a-42
be connected to NIC port of your laptop or PC

21


10/03/2020

10/03/2020



43

Straight

Hub or Switch



Crossover



Rollover

10/03/2020

Host or Router

44

22


10/03/2020

Connector

Hub:

10/03/2020



Switch

45


NIC

10/03/2020

46

23


10/03/2020

Ethernet 10Base5

Ethernet 10BaseT
5a-47

Ethernet 10Base-T with
Hubs, Switchs

5a-48

24


10/03/2020







Used in 10BaseT, 10Base2
Each bit has a transition – 1: up to down, 0: down to up
Allows clocks in sending and receiving nodes to
synchronize to each other
o no need for a centralized, global clock among nodes!



Hey, this is physical-layer stuff!
5a-49





use standard Ethernet frame format
the nominal rate of 100 Mbit/s
Most switches and other networking devices with ports
capable of Fast Ethernet can perform autonegotiation
o standard specifies the use of CSMA/CD



A full-duplex mode is also specified

10/03/2020

50


25