Transcript Shared Access Networks

CSS432 Shared Access Networks
Textbook Ch2.6 - 2.7
Prof. Athirai Irissappane
http://courses.washington.edu/css432/athirai/
[email protected]
CSS 432
1
Ethernet

local area networking (LAN) technology of last 20 years.



Developed by Xerox PARC in mid-1970s
Similar to IEEE 802.3 standard
Uses CSMA/CD technology





Carrier Sense Multiple Access with Collision Detection.
Multiple access network
A set of nodes send and receive frames over a shared link.
Carrier sense means that all nodes can distinguish between an
idle and a busy link.
Collision detection means that a node listens as it transmits and
can therefore detect when a frame it is transmitting has collided
with a frame transmitted by another node.
Ethernet transceiver (sends and receives signal) and adaptor
CSS 432
2
Ethernet


Ethernet segment is implemented on a coaxial cable of up to 500 m
Bandwidth: 10Mbps (10Base2=Thin Coax 200m, 10B5=Yellow Thick Coax
500m, 10BT=Twisted pair 100m), 100Mbps(10BaseT), 1Gbps





Multiple Ethernet segments can be joined together by repeaters.
A repeater is a device that forwards digital signals (only 4 allowed)
Hub:multiway repeater,repeats data it hears on one port to all others
Data from one host reaches all other hosts
Drawback: Contention for the same Ethernet link
Ethernet repeater (l = 500 * 4 seg + 500 = 2500 m)
CSS 432
Ethernet Hub
3
Access Protocol for Ethernet


Multiple access network, access control to the shared Ethernet link
Media Access Control (MAC).
implemented in Hardware on the network adaptor.

Frame format (Similar to HDLC framing protocol)

Preamble (64bit): allows the receiver to synchronize with the signal (sequence of
alternating 0s and 1s).
 Host and Destination Address (48bit each).
 Packet type (16bit): demux key to identify the higher level protocol where
message should be delivered
 Data (up to 1500 bytes)



Minimally a frame must contain at least 46 bytes of data.
Frame must be long enough to detect collision.
CRC (32bit)
bytes
8
Preamble
6
Dest
addr
6
Src
addr
2
Type
Used by layer 3
IP: 0x0800
ARP: 0x0806
IPv6: 0x86DD
46 ~ 1500 4 Inter-frame gap
Next
Body
CRC 12
frame
Min: 64bytes (512bits) ~ Max: 1518bytes
Ethernet (MAC) Address



Each host on an Ethernet has a unique Address.
The (unicast) address belongs to the adaptor, not the host.
MAC Address
 sequence of six numbers separated by colons
 each number corresponds to 1 byte of the 6 byte (48 bit)
address and is given by a pair of hexadecimal digits, one for
each of the 4-bit nibbles in the byte
 Leading 0s are dropped.



E.g., 8:0:2b:e4:b1:2 = 00001000 00000000 00101011 11100100 10110001 00000010
address consisting of all 1s a broadcast address.
 All adaptors pass frames addressed to the broadcast address
up to the host.
an address with first bit set to 1 but is not the broadcast address is
called a multicast address.
 host can program its adaptor to accept multicast addresses.
CSS 432
5
Ethernet Transmit Algorithm

If line is idle…

Adapter sends frame immediately
 Upper bound message size of 1500 bytes: MTU (Maximum
Transmission Unit)
 Must wait 9.6usec between back-to-back frames Why? (See the
next slide.)

If line is busy…



Adapter waits until idle and transmit immediately
Called 1-persistent
 Transmit a packet with probability 1.
 (special case of p-persistent: transmitting a packet with P
percent, where 0 < p ≤ 1)
Collision of frames

2 or more two (or more) adaptors to begin transmitting at the
same time,
CSS 432
6
Transmit Algorithm (cont)

If collision…
 Ethernet
10Mbps
means 10bits/usec.
supports collision detection, each
sender
is
96bits needs 9.6usec
able to determine that a collision is in progress
 Send a 32-bit jamming sequence, and then stop
transmitting frame (64bit preamble + 32bit jam = 96bits)
1010101… 64bits 1010.. 32bits
 Hosts are close 96 bits enough
 Hosts are at opposite ends (2500 m)?
 Minimum frame is 64 bytes (header + 46
bytes data + 4
bytes CRC) = 512bits Why? (See the next slide.)
 The farther the nodes, the longer the time it takes for a
frame sent by one to reach the other, and the network
is vulnerable to collision during this time
CSS 432
7
Collisions
500m x 5 = 2500m (with 4 repeaters)
latency
A
Time t
A
Ethernet
A sends a frame at time t
Arrives at B at time t + d
B
B
Time t + d
(d = 25.6us: approx. 0.01us/m)
Token Ring
A
30%
B sends frame at t + d
Network load
Time t + 2d
(2d = 51.2us)
B
A collision occurred
Jam seq
A
Jamming seq arrives at t + 2d
B
Bandwidth
10Mbps
100Mbps
1Gbps
Bits/usec
10bits/usec
100bits/usec
1000bits/usec
Jamming sequence
96bits => 9.6usec
96bits => 0.96usec
96bits => 0.096usec (96nsec)
Max delay (RTT)
512bits => 51.2usec
512bits => 5.12usec
512bits => 0.512usec
Speed
51.2usec/5000m = 10.2nsec/m
51.2usec/200~400m = 12.8nsec/m
0.512usec/25m (cupper) =
20.5nsec/m
CSS 432
8
Collisions

2500 m long Ethernet, and there may be up to four
repeaters between any two hosts, RTT= 51.2 s
10 Mbps Ethernet corresponds to 512 bits
 10Mbps x 51.2us (bandwidth * delay) = 10 x 106 x 51.2 x 10-6 =
512bits = (64bytes)
limit the Ethernet’s maximum latency to a fairly small value (51.2 s)
for the access algorithm to work, thus length = 2500 m
On collision detection, adapter stops transmission, delays and tries
again. Doubles delay interval between retransmission (Exponential
Backoff)
 1st time: waits for 0 or 51.2us (selected at random)
 2nd time: 0, 51.2, 102.4us or 153.6us (random)
 3rd time: waits for k * 51.2, k = 0…23 – 1 (random)
 nth time: wait for k x 51.2us, for randomly selected k=0..2n - 1
 give up after several tries (usually 16)



9

2500 m long Ethernet, and there may be up to four
repeaters between any two hosts, RTT= 51.2 s
10 Mbps Ethernet corresponds to 512 bits
 10Mbps x 51.2us (bandwidth * 2*delay) = 10 x 106 x 51.2 x 10-6 =
512bits = (64bytes)
 RTT 51.2 us
 2*2500 m, 51.2us
 Speed: time taken for travelling 1m  51.2 us / 5000m= 10.2
ns/m, i.e, time/cable length
RTT for 100Mbps? min frame size =512 bits
 (bandwidth * 2*delay) = 512 bts
 2*delay= RTT = 512/100 Mbps = 5.12us
 If speed = 10.2 ns/m, cable length = time/speed = 5.12us/10.2
ns/m = 500 m round trip (or) 250 m one way



The higher network bandwidth, the more sensitive the NICs should be to
detect a collision.
CSS 432
10
Token Ring Overview




LAN technology (common features to Ethernet)
Ring is a single shared medium, algorithm to determine
which host can transmit onto the medium
Ethernet: Bus topology; Token ring: Loop
Examples


16Mbps IEEE 802.5 (based on earlier IBM ring)
100Mbps Fiber Distributed Data Interface (FDDI)
CSS 432
11
Token Maintenance


Medium access control is provided by a small frame, the token
When a station wishes to transmit, it must wait for token to pass by
and seize the token



change one bit in token which transforms it into a “start-of-frame sequence” and
appends frame for transmission
Each station examines passing frame, if destination, it copies the
frame into local buffer
Re-inserting token on the ring
 After sender has completed transmission of the frame.
 After frame has returned to the sending station.
*http://www.cse.wustl.edu/~jain/
cis677-98/ftp/e_6lan.pdf
CSS 432
12
Token Ring Overview

Idea




Frames flow in one direction: upstream to downstream
Special bit pattern (token) rotates around ring
Each node saves a copy and forwards the token
Release token after done transmitting





Immediate release: FDDI
Delayed release (after a sent frame came back) IEE802.5
Sender removes token when it comes back around
Stations get round-robin service
Frame Format
8
8
48
48
Start of
frame
Control
Dest
addr
Src
addr
32
Body
8
CRC End of
frame
24
Status
Priority bits
CSS 432
13
Token Maintenance



THT: How long may a node hold on to the token (time spent at node)
TRT Token rotation time, The amount of time it takes a token to circulate
once and come back to sender
TTRT: Max TRT = Num stations * THT + Ring latency
CSS 432
14
Token Maintenance

Lost Token

No node emits a token when initializing ring.
 A bit error corrupts token pattern.
 A node holding token crashes.

Lost Token Detection

IBM Token Ring: No more presence message from a monitor station
 FDDI: No more message for more than 2.5ms

Election Procedure

A station transmits a claim token with its MAC address if doubting the
existence of a monitor station.
 The highest address wins.
 FDDI: the largest TTRT(Target Token Rotation Time) wins.

Token Generation

Wait for NumStations x THT(Token Hold Time) + RingLatency
CSS 432
15
Wireless Network


No physical medium for transmission
Transmission through electromagnetic signals


Wireless links (WIFI, Bluetooth, FM radio) all share the
same medium (electromagnetic spectrum)



Radio, microwave, infrared
Share medium efficiently without interference
Dividing the medium using frequency and space dimensions
Allocations of bands (frequency) ranges determined by
government agencies such as FCC in USA



Bands for government use, AM radio, FM radio, televisions,
satellite communications, cell phones,
Specific frequencies within these bands are then allocated to
individual organizations for use within certain geographical areas.
Several bands set aside for
a license is not needed
16
CSSwhich
432
Wireless Network

Devices that use license-exempt frequencies are still
subject to certain restrictions
1.
Limitation on transmission power: limits the range of signal,
making it less likely to interfere with another signal


For example, a cordless phone might have a range of about 100 feet.
Baby monitors, home security systems, even WIFI..
Use Spread Spectrum Technique:
2.


Sharing spectrum without interference
While using the same constant frequency for transmission results in
interference from other signals, easy to intercept (not secure)
CSS 432
17
Wireless Network

Spread Spectrum technique: spread the signal over a
wider frequency band

Frequency hopping: Transmit signal over a random set of frequencies





Transmit at one frequency, then a second, then a third…
Sequence of frequencies is not truly random, instead computed
algorithmically by a pseudorandom number generator
Receiver uses the same algorithm
Hop frequencies in sync with the transmitter to correctly receive the frame
Direct sequence: Represents each bit in the frame by multiple
bits in the transmitted signal.



For each bit, the sender sends the XOR of that bit and n random bits
random bit generator known to both the sender and the receiver.
The transmitted values, known as an n-bit chipping code, spread the signal
across a frequency band that is n times wider
CSS 432
18
Wireless Network

A second spread spectrum technique called Direct
sequence


Represents each bit in the frame by multiple bits in the
transmitted signal.
For each bit the sender wants to transmit



It actually sends the exclusive OR of that bit and n random bits
The sequence of random bits is generated by a pseudorandom
number generator known to both the sender and the receiver.
The transmitted values, known as an n-bit chipping code,
spread the signal across a frequency band that is n times wider
4-bit chipping code
CSS 432
19
Wireless Network

CDMA: Code Division Multiple Access (Cellular-3G)
 Multiplexing
technique different from Time/Frequency
Division multiplexing
 Sender uses entire bandwidth the whole time
 Differentiated using chipping codes
 Each cell phone sends data with a different (but preassigned chipping code.)
 A base station distinguish many cell phones using their
unique chipping code.
CSS 432
20
Wireless Network

Topology



Wireless Network with Base Station
Mesh or Ad-hoc network
Wireless Network with Base Station

Two end-points are usually different kinds of nodes






One end-point usually has no mobility, but has wired connection to the Internet (known as base station)
The node at the other end of the link is often mobile
Wireless communication supports point-to-multipoint communication
Communication between non-base (client) nodes is routed via the base station
Three levels of mobility for clients
 No mobility: the receiver must be in a fix location to receive a directional transmission
from the base station (initial version of WiMAX)
 Mobility is within the range of a base (Bluetooth)
 Mobility between bases (Cell phones and Wi-Fi)
Mesh or Ad-hoc network (no base station)
 Nodes are peers
 Messages may be forwarded via a chain of peer nodes
CSS 432
21
Wireless Network

Ad-hoc Network

CSS 432
Base Stations
22
Wireless Network

Wireless technologies differ in a variety of dimensions



How much bandwidth they provide
How far apart the communication nodes can be
Four prominent wireless technologies




Bluetooth
Wi-Fi (more formally known as 802.11)
WiMAX (802.16)
3G cellular wireless
CSS 432
23
IEEE 802.11 (WIFI)


Wireless Link Technology
Like its Ethernet and token ring siblings, 802.11 is
designed for use in a limited geographical area (homes,
office buildings, campuses)


Primary challenge is to mediate access to a shared
communication medium – in this case, signals propagating
through space
Operates in the license exempt band 2.4 GHz or 5 GHz
CSS 432
24
Collision

Ethernet:
Every node receives every other node’s transmissions
 Every node can transmit and receive at the same time
WIFI
 Cannot transmit and receive at the same time on the same
frequency, power generated by transmitter is much higher than
receiver; WIFI runs at half-duplex
 Every node cannot received transmissions from the other node
because of the WIFI range, distance between the nodes,
blockage between the nodes


CSS 432
25
Collision Avoidance




B can exchange frames with A and C, but it cannot reach D; C can
reach B and D but not A; A and C are said to hidden nodes
Hidden Node Problem: Signals from A and C can collide at B
Exposed Node Problem: B sends signal to A; C becomes aware and
stops sending to D thinking it will interfere with A
MACA Multiple Access with Collision Avoidance Alg.
 Sender and receiver exchange control frames (Request to Send
RTS, Clear to Send CTS) with each other before the sender
actually transmits any data.
 Any node that sees the CTS frame is close to the receiver,
therefore cannot transmit for the period of time it takes to send a
frame of the specified length
 Any node that sees the RTS but not CTS is free to transmit
 Receiver sends an ACK to the sender after successfully receiving
a frame All nodes must wait
26
CSS for
432 this ACK before trying to transmit
Distribution System



802.11 is suitable for an ad-hoc configuration
Nodes are free to move around
additional structures on a set of nodes

some nodes are allowed to roam

some are connected to a wired network infrastructure
- they are called Access Points (AP) and they are connected to each
other by a so-called distribution system


The fig. illustrates a distribution system that connects three access
points, each of which services the nodes in the same region
Each of these regions is analogous to a cell in a cellular phone
system with the APs playing the same role as a base station
CSS 432
27
Distribution System

Each nodes associates itself with one access point


For node A to communicate with node E, A first sends a frame to its AP-1
which forwards the frame across the distribution system to AP-3, which
finally transmits the frame to E
The technique for selecting an AP is called scanning

The node sends a Probe frame
 All APs within reach reply with a Probe Response frame
 The node selects one of the access points and sends that AP an
Association Request frame
 The AP replies with an Association Response frame
CSS 432
28
Bluetooth (802.15.1)






Used for very short range communication between mobile phones,
PDAs, notebook computers and other personal or peripheral devices
Operates in the license-exempt band at 2.45 GHz
Has a range of only 10 m
Communication devices belong to one person or group, Bluetooth is
categorized as Personal Area Network (PAN)
Version 2.0 provides speeds up to 2.1 Mbps
Power consumption is low
active
slave
7
parked
slave
Request
:
Reponses
:
master
active
slave
TDM
255
parked
slave
o
e
o
e
CSS 432
o
e
o
e
29
Bluetooth (802.15.1)

Bluetooth network configuration is called a piconet





Consists of a master device and up to seven slave devices
Any communication is between the master and a slave
The slaves do not communicate directly with each other
A slave can be parked: set to an inactive, low-power state (255
parked slaves allowed in a piconet)
Synchronous Time division multiplexing: Master transmits in odd
time slot, slave in the even time slot. Slave transmits as a response to
request in the previous master slot (avoids contentions between slaves)
active
slave
7
parked
slave
Request
:
Reponses
:
master
active
slave
TDM
255
parked
slave
o
e
o
e
CSS 432
o
e
o
e
30
Cell Phone Technology



Wireless Technology
Use Licensed Spectrum, owned by cellular phone operators (AT & T,
Verizon, T-Mobile) – costly
Topology: Relies on a wired network of base stations

Geographic area served by a base station is a cell
Base station can server one or more cells
Cells overlap
A phone is in control of only one base station at a time
When phones moves to an area of overlap, the base station senses the
weakening of signal from phone and gives control to another base
station which receives the strongest signal.
If the phone is involved in a call, this transfer is called handoff





Handoff
1
P
2
Call
3
Base satations
CSS 432
P
31
Network Adapters
Host Computer
Example
Interrupt  Myrinet Lanai series

CPU
Network Interface Card (NIC)
Network
Processor I/Omemory
Programmed
I/O bus
Controller
System Bus
DMA
PCI
Bus
Network
Link
FIFO
Bus
Interface
FIFO
Link
Interface
Memory
32bit, 33MHz = 1056Mbps
633Mbps STS-12
1000Mbps Ehternet
CSS 432
32




Network interface cards act as the physical interface or connection
between the computer and the network cable
Computers manufactured today use 32/64-bit buses. When data
travels on a computer's bus, it is said to be traveling in parallel
because the 32/64 bits are moving along side by side.
On the network cable, however, data must travel in a single stream
of bits. When data travels on a network cable it is said to be
traveling as a serial transmission because one bit follows another.
The NIC takes data that is traveling in parallel as a group and
restructures it so that it will flow through the 1-bit-serial path of the
network cable.
CSS 432
33
Memory Bottleneck


PCI(33bit, 33MHz) = 1056Mbps
System Bus = 235MBps = 1880Mbps (Text example) ≈ real
throughput

Memory Bus Controller



Data copy:



Arbitration among CPU and DMA
DRAM setup time
Application memory space to OS
OS memory space to NIC DMA-manageable space
Zero copy/pin-downed communication

Bypassing OS


Application
Reducing memory-copying overhead
Reducing interrupts
OS
DMA-manageable memory
CSS 432
34








33 Mhz * 64 bit PCI = 1056 Mbps
Memory bandwidth (rate at which data can be read from or stored into
memory) = 1000 Mbps
Bandwidth that needs to be considered is 1000 Mbps as it is < 1056 Mbps
Say if the NIC is attached to 100 Mbps coaxial cable
How many such NIC’s can be handled at a time?
Maximum Bounded Bandwidth = 1000 Mbps
Considering RTT Maximum Bounded Bandwidth = 1000/2 = 500Mbps
Number of NIC’c that can be supported = 500Mbps/100 Mbps = 5 NIC’s
CSS 432
35
Performance Considerations
in Layer 2: Data Link Layer






Network interface cards provides operations up to layer 2 of the OSI
model
DMA
 Initializing DMA channels versus programming CPU I/O
Frame Size
 Stuffing a full frame versus distinguishing one-time small-frame
transfer and burst frame transfer channels
Frame Transfer Strategy
 Individual transfers versus pipelined transfers
Fragmentation/Aggregation
 Frame fragmentation versus frame aggregation
Multicast through a switch
 Software emulation or hardware implementation
CSS 432
36

Reviews
 Ethernet:
k-persistent, exponential back off, and the
relationship between the minimum frame size and
collisions.
 Token ring network: immediate/delayed release, THT,
TRT, and TTRT
 Network adapters: writev/readv and memory bottleneck

Exercises in Chapter 2
 Ex.
42 (Ethernet)
 Ex. 46 (Ethernet)
 Ex. 53 (Wi-Fi)
 Ex. 54 (Wi-Fi)
CSS 432
37