Transcript Local Area Networks

An Introduction
to
Computer Networks
Lecture 5: Direct Link Networks
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
1
Outline





Issues
ALOHA Network
Ethernet
Token Ring
Wireless
Univ. of Tehran
Introduction to computer Network
2
Main Issues


Local Area Network (LAN) : Three or more
machines are physically connected and
communicating.
Problems:

How to connect them? Topology



How to address each machine? Addressing
How to regulate accessing to the media?




Sharing links
MAC (Media Access method or protocol)
Collision!
Different technology address each problem in
different way.
Problems are not independent
Univ. of Tehran
Introduction to computer Network
3
LAN Technologies.
Session
Transport
Network
Link
Physical
The 7-layer OSI Model
TCP
TFTP
HTTP
NNTP
Presentation
Telnet
FTP
SMTP
Application
UDP
IP
LAN-LINK
The 4-layer Internet Model
Link layer can have two types of technologies;
• Point to point link like PPP where there are only 2 nodes.
• Broadcast link like Ethernet when there are more than 2
nodes.
Univ. of Tehran
Introduction to computer Network
4
Data link sublayers
Our focus will be on
MAC sublayer.
MAC = “Medium Access Control”
Multiplexing
Media Access (MAC)
Error Detection
Framing
• The link is shared among different sender and receivers.
• Since every frame is simultaneously accessed by different nodes;
•They are called multiaccess links.
•They are called broadcast links. (important)
•LAN because of limited area.
• We need some type of medium access rules to avoid collision.
• Multicast capability of LANs.
Univ. of Tehran
Introduction to computer Network
5
Ideal Multiple Access Protocol
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:


no special node to coordinate transmissions
no synchronization of clocks, slots
4. Simple
Univ. of Tehran
Introduction to computer Network
6
Goals of MAC Protocols
MAC Protocols arbitrate access to a
common shared channel among a
population of nodes
Goals:
1. Fair among users
2. High efficiency
3. Low delay
4. Fault tolerant
Univ. of Tehran
Introduction to computer Network
7
Simple
Random
Examples of MAC Protocols
Packet-Switched Radio Network
Aloha
Carrier Sense Multiple Access/Collision Detection
Complex
Deterministic
Ethernet (IEEE 802.3)
Token Passing
Token Ring (IEEE 802.5)
Fiber Distributed Data Interface (FDDI)
Wireless
Univ. of Tehran
Introduction to computer Network
8
MAC Protocols
Three broad classes:
 Channel Partitioning



Random Access



divide channel into smaller “pieces” (time slots,
frequency, code)
allocate piece to node for exclusive use
channel not divided, allow collisions
“recover” from collisions
Taking turns

Nodes take turns, but nodes with more to send
can take longer turns
Univ. of Tehran
Introduction to computer Network
9
Channel Partitioning: TDMA
TDMA: time division multiple access





access to channel in "rounds"
each station gets fixed length slot (length = pkt trans
time) in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle
TDM (Time Division Multiplexing): channel divided into N
time slots, one per user; inefficient with low duty cycle
Univ. of Tehran
Introduction to computer Network
10
Channel Partitioning: FDMA
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 pkt, frequency bands 2,5,6
idle
frequency bands

Univ. of Tehran
Introduction to computer Network
11
Random Access Protocols

When node has packet to send




two or more transmitting nodes ➜ “collision”,
random access MAC protocol specifies:



transmit at full channel data rate R.
no a priori coordination among nodes
how to detect collisions
how to recover from collisions (e.g., via delayed
retransmissions)
Examples of random access MAC protocols:



ALOHA
slotted ALOHA
CSMA,
CSMA/CD, CSMA/CA
Univ. of Tehran
Introduction to computer Network
12
Pure (unslotted) ALOHA


unslotted Aloha: simpler, no synchronization
when frame first arrives


transmit immediately
collision probability increases:

frame sent at t0 collides with other frames sent in [t01,t0+1]
Univ. of Tehran
Introduction to computer Network
13
Implemented Aloha
All nodes transmit on one freq.
Central Node
Central node relays packets on
the other frequency
f0
f1
If more than one node transmit at the same time
Collision!
If there is a collision, both nodes re-transmit packets
Univ. of Tehran
Introduction to computer Network
14
Slotted ALOHA
Assumptions





Operation
all frames same size
time is divided into equal
size slots, 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 slot, all nodes detect
collision
Univ. of Tehran



when node obtains fresh
frame, it transmits in next
slot
no collision, node can send
new frame in next slot
if collision, node retransmits
frame in each subsequent
slot with prob. p until
success
Introduction to computer Network
15
Slotted ALOHA
Pros



Cons
single active node can
continuously transmit at
full rate of channel
highly decentralized:
only slots in nodes need
to be in sync
simple
Univ. of Tehran




collisions, wasting slots
idle slots
nodes may be able to
detect collision in less
than time to transmit
packet
clock synchronization
Introduction to computer Network
16
Slotted Aloha efficiency
Efficiency is the long-run
fraction of successful slots
when there are many nodes,
each with many frames to send


Suppose N nodes with
many frames to send,
each transmits in slot
with probability p
prob that node 1 has
success in a slot
= p(1-p)N-1

prob that any node has
a success = Np(1-p)N-1
Univ. of Tehran


For max efficiency with
N nodes, find p* that
maximizes
Np(1-p)N-1
For many nodes, take
limit of Np*(1-p*)N-1 as
N goes to infinity, gives
1/e = .37
At best: channel
used for useful
transmissions 37%
of time!
Introduction to computer Network
17
Pure Aloha efficiency
P(success by given node) = P(node transmits) .
P(no other node transmits in
[t0-1,t0] .
[t0,t0 +1]
P(no other node transmits in
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)
Even worse !
infty ...
… choosing optimum p and then letting n ->
= 1/(2e) = .18
Univ. of Tehran
Introduction to computer Network
18
CSMA/CD Protocol
All nodes transmit & receive on one channel
Packets are of variable size.
1. Carrier Sense: Check if the line is idle before transmitting.
2. Collision Detection: If more than one node transmit.
Collision!
All nodes detect collision, wait for random delay. Goto 1.
binary exponential backoff
Univ. of Tehran
Introduction to computer Network
19
CSMA/CD Network Size Restriction
Node must be able to hear that there is
a collision before its packet is transmitted completely.
i.e. Packet Transmission Time > Round trip propagation time
i.e. TRANSP > 2.PROP
Univ. of Tehran
Introduction to computer Network
20
Performance of CSMA/CD
Assume time-slotted channel
1. Find  ( p): Probability that exactly one node transmits in
a given slot, where:
p = Prob{a node tries to transmit a packet in a time slot},
N = number of nodes
N
 ( p)    p(1  p) N 1
1 
d
 N (1  p ) N 1  pN ( N  1)(1  p ) N  2
dp
 max  36%  40%
when : p  1 / N
Univ. of Tehran
Introduction to computer Network
21
Ethernet Overview

History
developed by Xerox PARC in mid-1970s
 roots in Aloha packet-radio network
 standardized by Xerox, DEC, and Intel in 1978
 similar to IEEE 802.3 standard
Uses CSMA/CD technique for Media access.
Uses 10Mbps physical link originally and now
extended to 100Mbps, Fast Ethernet, and recently
to 1000Mbps, Gigabit Ethernet.
Uses variable frame length, 64-1500 bytes.




Univ. of Tehran
Introduction to computer Network
22
The Original Ethernet
Repeaters
every
500m
10Mb/s
l  1500m
PROPmax  l / c  1500 / 2.5 108  6s
Thick copper
coaxial cable
TRANSP  2 PROP  TRANSP  12s
 Packetsize  12s 10Mb / s  120bits
In practice, minimum packet size = 512 bits.
• allows for extra time to detect collisions.
• allows for “repeaters” that can boost signal.
Univ. of Tehran
Introduction to computer Network
23
The Original Ethernet
Original picture drawn by Bob Metcalfe,
inventor of Ethernet (1972 – Xerox PARC)
The Ethernet protocol is implemented in Contoroler (Adaptor)
Univ. of Tehran
Introduction to computer Network
24
The Original Ethernet
Original picture drawn by Bob Metcalfe,
inventor of Ethernet (1972 – Xerox PARC)
The Ethernet protocol is implemented in Contoroler (Adaptor)
Univ. of Tehran
Introduction to computer Network
25
Ethernet Frame Format
Bytes:
7
1
6
6
Preamble SFD
DA
SA
2
Type
0-1500
Data
0-46 4
Pad CRC
1. Preamble: trains clock-recovery circuits
2. Start of Frame Delimiter: indicates start of frame
3. Destination Address: 48-bit globally unique address
assigned by manufacturer.
1b: unicast/multicast
1b: local/global address
4. Type: Indicates protocol of encapsulated data (e.g. IP
= 0x0800)
5. Pad: Zeroes used to ensure minimum frame length
6. Cyclic Redundancy Check: check sequence to detect
of Tehran
Introduction to computer Network
26
bitUniv.
errors.
Ethernet Addresses






Unique, 6 bytes or 48-bit address assigned to each
adapter by manufacturer.
It is read in : notation, for example: 8:0:e4:b1:2
An address with all 1s is a broadcast address.
multicast: first bit is 1
In order to make the address unique, first 24 bits
are assigned to manufacturers and the last 24 bits
are assigned locally.
Each adaptor accept the packet if the destination
address is its own address, broadcast address or
multicast to which this adaptor belongs.
Univ. of Tehran
Introduction to computer Network
27
The 10Mb/s Ethernet Standard
IEEE 802.3
Ethernet MAC Protocol
10Base-5
Different
physical layer
options
10Base-2
10: 10Mbs
10Base-T
10Base-F
Base: baseband 5: 500 Meter
10Base-5: Original Ethernet: large thick coaxial cable.
10Base-2: Thin coaxial cable version.
10Base-T: Voice-grade unshielded twisted-pair
Category-3 telephone cable.
10Base-F: Two optical fibers in a single cable.
Univ. of Tehran
Introduction to computer Network
28
10Base-T
“Twisted pair Ethernet”
Repeater
“Hub”
100m max cable length
Router



Designed to run over existing voice-grade “Category3” twisted pair telephone wire.
Centralized management (“managed hubs”) lead to
more reliability.
Created a huge increase in Ethernet usage.
Univ. of Tehran
Introduction to computer Network
29
Transmit Algorithm
If line is idle…
send immediately
upper bound message size of 1500 bytes
must wait 9.6us between back-to-back frames
If line is busy…
wait until idle and transmit immediately
called 1-persistent (special case of p-persistent)
(sending with probability of p)
Univ. of Tehran
Introduction to computer Network
30
Algorithm (cont)
If collision…
jam for 32 bits, then stop transmitting frame
(minimum frame is 64 bytes (header + 46 bytes of data))
delay and try again
1st time: 0 or 51.2us
2nd time: 0, 51.2, or 102.4us
3rd time51.2, 102.4, or 153.6us
nth time: k x 51.2us, for randomly selected k=0..2n - 1
give up after several tries (usually 16)
exponential backoff
Univ. of Tehran
Introduction to computer Network
31
Increasing the data rate
Increasing the data rate create the following
Problem:
 E.g. CSMA/CD at 100Mb/s over 1500m of
TRANSP  2PROP
cable:
8
PROP  1500 / 2.5 10  6s
TRANSP  12s  Packetsize  1200bits

To overcome this two techniques used:


Cable length limited to 100m:
PROP  200 / 2.5 108  Packetsize  160bits
Increase the minimum packet length.
Univ. of Tehran
Introduction to computer Network
32
Ethernet Switch
Ethernet
Switch/Bridge
Router
• If
only one computer per port, no collisions can take
place (each cable is now a self-contained point-to-point
Ethernet link).
• Capacity is increased: the switch can forward multiple
frames to different computers at the same time.
• An Ethernet switch must contain buffers to hold
Univ. of Tehran
Introduction to computer Network
33
frames
during times of
congestion.
Extending LANs
Ethernet
Switch/Bridge
Router
Ethernet
Hub
• Combinations
of Hub, switch and router
•Broadcasts by Hub is sensed by switch
Univ. of Tehran
Introduction to computer Network
34
Token Ring
Listen:
Talk:
Data
l4
l1
l3
l2
Token/Data
PROP  i li / c  TRTmin
TRT=Token Rotation Time
Univ. of Tehran
Introduction to computer Network
35
Token Ring (cont)


It is like people talking in a ring in the round
robin manner.
Common features.




Frames flow in one direction: upstream to
downstream
special bit pattern (token) rotates around ring
must capture token before transmitting
release token after done transmitting




immediate release
delayed release
remove your frame when it comes back around
stations get round-robin service
Univ. of Tehran
Introduction to computer Network
36
Release After Reception (RAR)


Computer captures token, transmits data, waits for
data to successfully travel around ring, then releases
token again.
Allows computer to detect errored frames and
retransmit them.
Example time evolution in which host 1 and host 3 have packets to transmit:
TRANSP
PROP
TRANST
Data
Token
l1/c l2/c
Token arrives
at host 1
Univ. of Tehran
TRANST
lN/c
TRANSP
Data
Token
l1/c
l2/c
Token departs Token arrives
at host 3
from host 1
Token arrives
at host 2
Introduction to computer Network
l3/c
time
37
Release After Transmission
(RAT)


Computer captures token, transmits data, then
releases token again.
FDDI uses this technique.
Example time evolution in which host 1 and host 3 have packets to
transmit:
TRANSP
Data
TRANST TRANST
Token
l1/c
Token arrives
at host 1
Univ. of Tehran
Token departs
from host 1
Token
TRANSP
Data
l2/c
Token arrives
at host 3
Token
time
Token arrives
at host 2
Introduction to computer Network
38
Timed Token Algorithm

Token Holding Time (THT)


Token Rotation Time (TRT)


how long it takes the token to traverse the ring.
ActiveNodes x THT + RingLatency  TRT
Target Token Rotation Time (TTRT) (FDDI)


upper limit on how long a station can hold the token
agreed-upon upper bound on TRT
Each node measures TRT between successive
tokens


if measured-TRT > TTRT: token is late so don’t send
if measured-TRT < TTRT: token is early so OK to send
Univ. of Tehran
Introduction to computer Network
39
Token Maintenance

Lost Token



no token when initializing ring
bit error corrupts token pattern
node holding token crashes
Solution- have a monitor

Monitor role in the link



Generating Tokens
Announces its presence periodically
Check for the corrupt or orphaned frames and
remove them from the ring. Orphaned frame are
those whose sending station have died. Sets the
monitor bit to 0 in sending and to 1 when pass
the monitor.
Univ. of Tehran
Introduction to computer Network
40
Token Maintenance (cont)


How about when the monitor dies? Or the network
just powered up?
Any station tries to become monitor



send a claim frame that includes the node’s TTRT bid
if your claim frame makes it all the way around the ring:
 Everyone has accepted you as the monitor
 everyone knows TTRT
 you insert new token
How about receiving another monitor claim at the
same time? Break the tie with



The lowest TTRT bid wins.
The highest address wins.
Etc.
Univ. of Tehran
Introduction to computer Network
41
Maintenance (cont)

Monitoring for a Valid Token



should periodically see valid transmission
(frame or token)
maximum gap = ring latency + max frame <
= 2.5ms
set timer at 2.5ms and send claim frame if it
fires
Univ. of Tehran
Introduction to computer Network
42
Frame format
Bytes 1
Start
Delimt.




1
Access
control
1
Frame
control
6
6
Dest.
Addr
Src.
Addr
Variable
Body
4
Checks
um
1
1
End
Delimt.
Frame
status
Access control is for priority.
Frame control is a Demux key for the higher layer
protocol.
Addresses are like Ethernet. They can also be 16 bit.
Frame Status include two A and C bits.


A, Active bit, is set by the receiver indicating the station is alive
and has seen the frame.
C, Copy bit, is also set by the receiver indicating the frame has
been copied.
Univ. of Tehran
Introduction to computer Network
43
FDDI: Fiber Distributed






It is a Dual counter-rotating ring for fault
tolerance. It can be also Single Attachment
(SAS- Single Attachment Station).
100 Mbps on optical fibers
Up to 500 nodes
Total length less than or equal to 200 km
Uses 4B/5B encoding.
Modulation: non-return to zero with inversion
(NRZI)
Univ. of Tehran
Introduction to computer Network
44
FDDI Timed Token Rotation
Protocol
1. All hosts agree on a common Target Token Rotation
Time (TTRT). They will aim to make the token rotate
around the network at least once per TTRT. Hence,
they can each expect to see the token once
TTRT.
2. Each host on the network maintains a timed token
Rotation (TRT) timer, that indicates when the token is
next expected to arrive.
3. If the token arrives before TRT expires, we say it is
“Early”. If the token arrives after TRT expires, we say
it is “Late”.
4. A host can only transmit if it receives the token, AND
the token is Early.
Univ. of Tehran
Introduction to computer Network
45
Wireless LANs




It is shared media like Ethernet
The standard is IEEE 802.11
Bandwidth: 1 or 2 Mbps
Physical Media


spread spectrum radio (Up to 2.4GHz)spread signal over a wider frequency band
diffused infrared (10m), sender and receiver
do not have to aimed at each (up to 10m,
bluetooth tech).
Univ. of Tehran
Introduction to computer Network
46
Spread Spectrum


Idea is to spread signal over wider frequency
band than required
Frequency Hopping


transmit over random sequence of frequencies
sender and receiver share…



pseudorandom number generator
seed
802.11 uses 79 x 1MHz-wide frequency bands
Univ. of Tehran
Introduction to computer Network
47
Spread Spectrum (cont)

Direct Sequence




for each bit, send XOR of that bit and n random
bits
random sequence known to both sender and
receiver
The sent code is called n-bit chipping code
802.11 defines an 11-bit chipping code
1
0
Data stream: 1010
1
0
Random sequence: 0100101101011001
1
0
XOR of the two: 1011101110101001
Univ. of Tehran
Introduction to computer Network
48
Collisions Avoidance


It is similar to Ethernet, but there is mobility
problem here and also
Problem: hidden and exposed nodes



B can exchange data with A and C, but not D.,
How A and C send to B, they are not aware, this is the
hidden node problem.
If B send to A, C can send to D, exposed problem.
A
Univ. of Tehran
B
C
Introduction to computer Network
D
49
MACA


MACA- Multiple Access with Collision
Avoidance
The idea is the sender and receiver to
exchange control information.
Univ. of Tehran
Introduction to computer Network
50
MACA (cont)



Sender transmits RequestToSend (RTS) frame
Receiver replies with ClearToSend (CTS) frame
Neighbors…



Receiver sends ACK when has the frame


see CTS: keep quiet
see RTS but not CTS: OK to transmit
neighbors silent until see this ACK
Collisions if two sender transmit RTS at the same
time.



no collisions detection
known when don’t receive CTS
exponential backoff
Univ. of Tehran
Introduction to computer Network
51
Supporting Mobility


Case 1: ad hoc networking when node may or
may not be able to communicate.
Case 2: access points (AP) connected node to
wire
 each mobile node associates with an AP
Distribution system
AP-1
AP-3
F
AP-2
A
B
G
H
C
Univ. of Tehran
D
Introduction to computer Network
E
52
Mobility (cont)

Scanning (selecting an AP)






node sends Probe frame
all AP’s w/in reach reply with ProbeResponse frame
node selects one AP; sends it AssociateRequest
frame
AP replies with AssociationResponse frame
new AP informs old AP via network
When


active: when join or move
passive: AP periodically sends Beacon frame
Univ. of Tehran
Introduction to computer Network
53
Network Adaptors

All functionalities are implemented in
Adaptors or network cards.
Each vender has it own adaptor.
Host I/o bus

Univ. of Tehran
Bus
interface
Link
Interface
Network
Adaptor
Introduction to computer Network
54
Network Adaptors (cont)




Adaptor, like other devices, are programmed
by CPU.
Adaptor has a Control Status Register
(CSR), usually located in the memory.
CPU communicate with Adaptor through
CSR.
Two methods for Communication, polling
and interrupt.
Univ. of Tehran
Introduction to computer Network
55
Network Adaptors (cont)



How to transfer data? Direct memory access
(DMA) and programmed I/O (PIO)
Device drivers are routines to connect OS
with the network hardware.
Memory is bottleneck. Each frame might be
written/read several times from the memory.

It has limited Bandwidth, usually 32 bit x 300
MHz, (around 10 Gbps), however, each packet
goes at least two time and there are overheads.
Univ. of Tehran
Introduction to computer Network
56