1

Pertemuan 13Teknik Akses Jaringan - Random

Matakuliah : H0174/Jaringan Komputer

Tahun : 2006

Versi : 1/0

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa akan mampu :

• Menjelaskan teknik akses ke jaringan secara random

3

Outline Materi

• ALOHA• Slotted ALOHA• Reservation ALOHA

4

Medium Sharing Techniques

Allocation Principles

• Channel partitioning (Multiple Access)– Divide channel into smaller pieces (time

slots, frequency)– Allocate piece to node for exclusive use

• Random access– Allow collisions and Recover from collisions

• Scheduled /Taking turns – Tightly coordinate shared access to avoid

collisions

5

/Broadcast Networks

• N senders and receivers connected by a shared medium (copper wire, atmosphere, water)

• Shared local access to the same media• Multiple Access Protocol Determine which host is

allowed to transmit next to a shared medium• Channel partition: TDMA, FDMA, CDMA• Random access: ALOHA, CSMA/CD, CSMA/CA

• Local Area Network (LAN)• Ethernet, Fast Ethernet, Gigabit

Ethernet, Wireless Ethernet, or 802.11 b/a, or WiFi

6

Multiple-access protocols

7

Medium Access Methods

8

• General principles:• No Carrier Sensing• Carrier Sensing

• Wait for silence• Then talk (transmit)• Listen while talking• Backoff if there is transmission .• Repeat

• Protocols also add a random increasing timeout

Random Access Protocols

9

No Carrier Sensing

ALOHA

– Useful in which uncoordinated users are competing for the use of a single shared channel.

– Pure Aloha (no global time synchronization) and Slotted Aloha (global time synch. required)

10

ALOHA Network

11

Pure ALOHA

PURE ALOHA– Stations transmit whenever they have

information to send at all times.– Collision will occur when two hosts try to

transmit packets at the same time– If first bit of a frame overlaps with last bit of an

earlier frame then both will be destroyed– Colliding frames destroyed detected by listening

to the channel– Such a system is called a contention system

12

– If no ACK by timeout, then wait a randomly selected delay to avoid repeated collisions, then retransmit

– Too short : large number of collisions– Too long : underutilization

– Frames are the same size – In LAN feedback is immediate. For satellite

broadcast 270msec delay

Pure ALOHA

13

Pure ALOHA - Collision

• No synchronization• Send without awaiting for beginning of slot• Collision of packets can occur when a packet

overlaps another packet:– Packet sent at t0 collide with packets sent at [t0-1]

or at [t0+1]

time

Collision

Wasted Time Colliding with B

Packet C

Packet B

Packet A

t0t0-1 t0+1

Collision

Overlap with start of

packet B

Overlap with end of packet B

14

• Rather than sending a packet at any time, send along time slot boundaries• Collisions are confined to one time slot

Slotted ALOHA

time

Collision

Wasted Time Colliding with

B

Packet CPacket B

Packet A

t0t0-1 t0+1

15

Efficiency of ALOHA

16

Pertemuan 14Teknik Akses Jaringan – Carrier Sense

Matakuliah : H0174/Jaringan Komputer

Tahun : 2006

Versi : 1/0

17

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa akan mampu :

• Menjelaskan teknik akses ke jaringan dengan carrier sense

18

Outline Materi

• CSMA• Back-off strategy

19

Carrier Sense Multiple Access

• ALOHA & Slotted ALOHA are inefficient because stations don’t take into account what other stations are doing before they transmit (Talk-before-listen)

• Sense for carriers (see if anyone else is transmitting) before begin transmitting

• Carrier Sense Multiple Access (CSMA) is Listen Before Talk

• In LAN’s it is possible for stations to detect what other stations are doing and reactively change.

• CSMA can improve performance• These protocols are called carrier sense protocols. • They are named 1-persistent CSMA, non-persistent

CSMA, p-persistent CSMA

20

• When station has data to send, it listens to channel

• Channel idle: station transmits packet • Channel busy: station waits till channel is idle• When channel becomes free, a host transmits

its packet immediately (with probability 1)

1- Persistent

Packet Atime

Station Blistens

Packet B

delay

Station Bsends

21

• Propagation delay II

– If propagation delay is small zero, collision may still occur

– Station A transmits, Stations B, X, Y simultaneously realize that line is busy and wait

– When line is free, stations B transmits then station X, Y simultaneously transmit. Collision.

Collision in CSMA

Packet Atime

Station Blistens

Packet B Packet Y

delay Collision still possibleover long propagation delays

Packet X

Station Bsends

22

• Before sending, station senses channel • If no transmission, station starts sending.• If channel is busy it does not continuously sense the

channel in order to start transmitting• Wait/sleep a random interval before sensing again• As soon as channel is idle, then send a packet

• Random interval reduces collisions• Higher throughput than 1-persistent CSMA when

many senders

Non Persistent

Packet Atime

Station Blistens

Packet B

Randomdelay

Station Bsends

23

• Generalization of 1-persistent CSMA• Typically applied to slotted channels• Slot length is chosen as maximum propagation delay

• A station senses the channel, and• If slot is idle, transmit with probability p, or defer with

probability q=1-p• If next slot is idle, transmit with probability p, or defer

with probability 1-p, repeat…• If channel is initially busy, it waits until the next slot

then sense channel continuously until it becomes free and applies the above algorithm

p-Persistent

24

• IEEE 802.3 is a standard for a 1-persistent CSMA/CD LAN– If cable is busy, station waits until cable is idle.– If 2 or more stations simultaneously transmit

on an idle cable, they will collide.– All colliding stations then terminate their

transmission and, wait random time and then start process again.

• Ethernet is a specific implementation.

CSMA with Collision Detection

25

• Ethernet uses CSMA/CD• Listen-while-talk protocol• A station listens even while it is transmitting, and

if a collision is detected, stops transmitting

Ethernet - CSMA/CD

Packet Atime

Station Blistens

Packet B

delay

Packet B size

Not transmitted

Station Bsends

Packet B

Station B detects collision,Stops sending

26

• Ethernet CSMA/CD requires a minimum size packet • If packet B arrives at A and A is no longer transmitting, then

Host A will• Fail to detect the collision• Thinks its packet got through• Thinks the incoming packet is a new packet

• Therefore, to detect a collision:• Minimum packet size >= 2*(prop. delay)*BW

A

Ethernet

Packet A t

d=propagation delay

B

Packet A

Packet B

Packet B

t+d

B transmit at t+d, just before packet A arrives. B sees collision and transmits a runt” packet Packet arrives at t+2d

Minimum size Ethernet packet

27

Comparison of multiple access

G (transmission attempts per packet time)