Transcript The ALOHA Protocol

The ALOHA Protocol
• “Free for all”: whenever station has a frame to send,
it does so.
– Station listens for maximum RTT for an ACK.
– If no ACK after a specified amount of time (how long?),
re-sends frame after waiting a random amount of time
(otherwise?)
– It continues to retry for a number of times and then gives
up. (What happens then?)
– Receivers check FCS and destination address to ACK.
• 0.18 the peak utilization with an average of 0.5 frame
attempted every frame time. (Wait a minute.)
Slotted Aloha Performance
How long does it take to send a frame?
The probabilit y that it takes exactly k tries : pk   e
G
1  e 
G k 1
one success k-1 failures

k 1
kr

k 1
Expected
number of
transmissions
d k d  k d 1
1
  r  r 

2
dr
dr
dr
1

r


1

r
k 1
k 1



k 0
k 0
E   kpk    ke
e
G
 k 1  e

k 1

G k 1
G
1  e 
e
G k 1
G
1
1  1  e 
G
2
 eG
Carrier Sense Multiple Access
(CSMA)
• Stations sense the medium before
transmitting.
• This can reduce the vulnerable period.
CSMA
• 1-persistent
– If medium is idle, then transmit.
– If medium is not idle, then wait until it is and then transmit.
• p-persistent (for slotted channels only)
– If medium is idle, then transmit.
– If medium is not idle, then wait until it is idle
– Once idle then transmit with probability p. And wait for the next
slot with probability 1-p and repeat.
• Problem: when a collision occurs, it lasts for a long time,
the whole frame transmission time. We shall see that for
10Mbps Ethernet, the max frame time is 1.2ms, but the
max time to detect collision is 50microsec.
Carrier Sense Multiple Access
with Collision Detection
CSMA/CD
When transmitting, detect if a collision is occurring. If a
collision is occurring, abort as soon as possible and wait a
random amount of time before retrying.
After beginning transmission, how long until we know that we
have control of the channel? Twice the propagation delay.
CSMA/CD
After beginning transmission, how long until we know that we
have control of the channel? Twice the propagation delay.
Let T be the propagation delay.
At t=0, node 1 begins transmission.
Suppose that at t=T- node 2 begins to transmit.
At t=T, node 2 detects the collision.
At t=2T-, node 1 detects the collision.
Keeping propagation delay small can improve efficiency.
After a collision is detected, often a jamming signal is applied.
This slightly increases the contention interval.
CSMA/CD
What happens if the propagation is too long and frame too short?
Frame transmission time must be at least twice as long as the propagation delay.
10Mbps ethernet – one bit takes ?
Propagation sec/meter = ?
10base max length is 2500 meters (with repeaters).
So minimum frame size is ?
But the the repeaters add some time,
so roundtrip propagation delay < 50microsec.
So minimum frame = ?
What would be the minimum frame for 100Mbps, 1Gbps?
CSMA/
CD
Ethernet
• <data rate><Signaling method><Max segment
length>
•
•
•
•
•
•
10Base5
10Base2
Medium Coaxial
Coaxial
SignalingBaseband Baseband
ManchesterManchester
TopologyBus
Bus
Nodes 100
30
10Base-T
10Base-FP
UTP
Baseband
Manchester
Star
-
850nm fiber
Manchester
On/Off
Star
33
Frame Layout
Preamble = 101010….10 for 56 bits – allows the PLL to synchronize
Start of Frame – 1 byte
DA - destination address – MAC address
SA - source address – MAC address
Length – 2 bytes
Data – so that total length is at least 64 bytes no more than 1500.
CRC 4 bytes.
Efficiency = (1500-26)/1500
Ethernet Address
MAC address
6 bytes = 7x1013 address
Each interface has its own address. There are no duplicate
address.
Types of destination address
• All bits are one then broadcast, all card on LAN read this packet.
This is used to learn about which other machines are on LAN,
DHCP and also can be used in a network attack (but not anymore).
• Unicast address.
• Multicast address. If the first bit is one, then the address corosponds
to a multicast group. All the members of the group read this packet.
CSMA/CD with Exponential Backoff
Time is divided into 51.2 micro sec slots.
If a collision occurs, then each host waits either 0 or 1 slot times before trying again.
If this fails, they wait either 0, 1, 2, or 3 slot times…..
However, the maximum slot times to wait is 1023.
And after 16 total tries, it gives up and signals upper layer.
Performance – with large frames, Ethernet get about 85% efficiency.
Hubs and Switches
Hub
10base-T
To the hosts, the wires
appear to be connected.
But there may be so
circuitry there.
Fewer collisions
Switches
No collisions
In the switch there can be much intelligence. The packets are
buffered and the packets only go to the correct card or set of
cards.
This stops packet sniffing.