Collision-free and Limited- contention Protocols

CISC 7332X T6

Collision-free and Limited-

contention Protocols

Hui Chen

Department of Computer & Information Science

CUNY Brooklyn College

10/22/2019 1CUNY | Brooklyn College

Outline

• Channel allocation problem

• Multiple Access Protocols

• Discussed

• ALOHA

• CSMA (Carrier Sense Multiple Access)

• CSMA/CD

• Collision-free protocols

• Limited-contention protocols

• To discuss next week

• Ethernet protocols

• Wireless LAN protocols

10/22/2019 CUNY | Brooklyn College 2

Medium Access Control

• Two types of network links

• Point-to-point

• Multiple access (broadcast)

• Key issue

• Who gets to use the channel when there is a

competition to it?

• Multiaccess channel/random access channel

• Medium Access Control (MAC)

10/22/2019 CUNY | Brooklyn College 3

The MAC Sublayer

• The protocols used to

determine who goes next on a

multiaccess channel

• Especially important for LAN,

particularly wireless LANs

• In contrast, WANs general use

point-to-point links, excepts

for satellite networks

10/22/2019 CUNY | Brooklyn College 4

Physical

Link

Network

Transport

Application

MAC is in here!

Multiple Access Protocols

• Discussed

• ALOHA

• CSMA (Carrier Sense Multiple Access)

• Collision-free protocols

• Limited-contention protocols

• To discuss next week

• Ethernet protocols

• Wireless LAN protocols

10/22/2019 CUNY | Brooklyn College 5

Collision Free Protocols

• Collision-free protocols avoid collisions

entirely

• Senders must know when it is their turn to

send

• Bitmap

10/22/2019 CUNY | Brooklyn College 6

Bitmap

• The basic bit-map protocol:

• The protocol consists of two phases

• Contention

• There are a fixed number of content slots.

• Sender set a bit in contention slot if they have data

• Sending frames

• Senders send in turn; everyone knows who has data

• Protocols like this, in which, the desire to

transmit is broadcast before actual

transmission is called reservation protocols

10/22/2019 CUNY | Brooklyn College 7

Basic Bitmap: Example

• Each station announces whether it has

data frame to transmit in its content slot

• After contention slots, transmit if any

station has a frame to transmit

10/22/2019 CUNY | Brooklyn College 8

Basic Bitmap: Efficiency

• Channel efficiency/utilization: assume N

slots, d bits per frame

• Low load: ~ d/(d+N)

• High load: ~ d/(d + 1)

• Mean delay

• > (N-1)d/2 + N

10/22/2019 CUNY | Brooklyn College 9

Token Passing

• Token sent round ring defines the

sending order

• Station with token may send a frame before

passing

• Idea can be used without ring too, e.g.,

token bus

10/22/2019 CUNY | Brooklyn College 10

Token Passing: Example

10/22/2019 CUNY | Brooklyn College 11

Station

Direction of

transmission

Token

Token Passing: Example

Protocols

• IEEE 802.5/Token Ring

• FDDI (Fiber Distributed Data Interface)

• IEEE 802.17/RPR (Resilient Packet Ring)

10/22/2019 CUNY | Brooklyn College 12

Count Down

• An improvement over basic Bitmap

• Stations send their address in contention slot

(log N bits instead of N bits), one bit at a time

• Medium ORs bits; stations give up when they

send a “0” but see a “1”

• Station that sees its full address is next to send

• Requirement on physical layer?

• Transmitting while receiving …

10/22/2019 CUNY | Brooklyn College 13

Count Down: Example

10/22/2019 CUNY | Brooklyn College 14

Limited-Contention Protocols

• To divide stations into groups within

which only a very small number are likely

to want to send

• Avoids wastage due to idle periods and

collisions

10/22/2019 CUNY | Brooklyn College 15

Already too many contenders for a

good chance of one winner

Adaptive Tree Walk:

Motivating Example

• U.S. Army adopted a method to test soldiers for syphilis

during World War II aiming at reducing tests.

1. Took a blood sample from N soldiers

2. Pour a portion of each to a test tube

3. If the mixed sample is clean with antibodies, the N

soldiers are declared healthy

4. Otherwise, divided N into two groups, each with N/2

soldiers

5. Repeat the testing protocol starting at step 1 (albeit for

each group of N/2 soldiers) recursively until the

infected soldier is found.

10/22/2019 CUNY | Brooklyn College 16

Limited Contention: Adaptive

Tree Walk

• Tree divides stations into groups (nodes)

to poll

• Depth first search under nodes with poll

collisions

• Start search at lower levels if >1 station

expected

10/22/2019 CUNY | Brooklyn College 17

Limited Contention: Adaptive

Tree Walk: Example Tree

• 8 stations; time slots conveniently numbered 1, 2, … 7 as the

node numbers in the tree; nodes are grouped accordingly

• If contention fails at time slot 1, nodes under 2 contends at slot

2, and nodes under 3 contends at slot 3 …

10/22/2019 CUNY | Brooklyn College 18

Level 0

Level 1

Level 2

Questions?

• Collision-free protocols

• Limited-contention protocols

10/22/2019 CUNY | Brooklyn College 19