Transcript lecture

Link Layer 3
Mozafar Bag-Mohammadi
University of Ilam
1
Token Ring Overview

Examples


16Mbps IEEE 802.5 (based on earlier IBM ring)
100Mbps Fiber Distributed Data Interface (FDDI)
2
Token Ring (cont)

Idea







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
Frame Format
8
8
48
48
Start of
frame
Control
Dest
addr
Src
addr
32
Body
8
CRC End of
frame
24
Status
3
Timed Token Algorithm

Token Holding Time (THT)


Token Rotation Time (TRT)



upper limit on how long a station can hold the token
how long it takes the token to traverse the ring.
TRT <= ActiveNodes x THT + RingLatency
Target Token Rotation Time (TTRT)

agreed-upon upper bound on TRT
4
Algorithm (cont)

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
Two classes of traffic
 synchronous: can always send
 asynchronous: can send only if token is early
5
Token Maintenance

Lost Token




no token when initializing ring
bit error corrupts token pattern
node holding token crashes
Generating a Token (and agreeing on TTRT)




execute when join ring or suspect a failure
send a claim frame that includes the node’s TTRT bid
when receive claim frame, update the bid and forward
if your claim frame makes it all the way around the ring:
 your bid was the lowest


everyone knows TTRT
you insert new token
6
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
7
Wireless LANs


IEEE 802.11
Physical Media


spread spectrum radio (2.4GHz)
diffused infrared (10m)
8
Spread Spectrum

Idea




spread signal over wider frequency band than required
originally designed to thwart jamming
Frequency Hopping
Direct Sequence
9
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
10
Direct Sequence




for each bit, send XOR of that bit and n
random bits
random sequence known to both sender and
receiver
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
11
Glossary of 802.11 Wireless Terms







Station (STA): A computer or device with a wireless network
interface.
Access Point (AP): Device used to bridge the wireless-wired
boundary, or to increase distance as a wireless packet repeater.
Ad Hoc Network: A temporary one made up of stations in mutual
range.
Infrastructure Network: One with one or more Access Points.
Channel: A radio frequency band, or Infrared, used for shared
communication.
Basic Service Set (BSS): A set of stations communicating
wirelessly on the same channel in the same area, Ad Hoc or
Infrastructure.
Extended Service Set (ESS): A set BSSs and wired LANs with
Access Points that appear as a single logical BSS.
12
Supporting Mobility


Case 1: ad hoc networking
Case 2: access points (AP)


tethered
each mobile node associates with an AP
Distribution system
AP-1
AP-3
F
AP-2
A
B
G
H
C
E
D
13
Overview, 802.11 Architecture
ESS
Existing
Wired LAN
AP
STA
BSS
AP
STA
STA
BSS
STA
Infrastructure
Network
STA
Ad Hoc
Network
STA
BSS
BSS
STA
Ad Hoc
Network
STA
14
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 tethered network
When


active: when join or move
passive: AP periodically sends Beacon frame
15
MACAW



Sender transmits
RequestToSend (RTS) frame
Receiver replies with
ClearToSend (CTS) frame
Neighbors…



Receiver sends ACK when it
has frame


see CTS: keep quiet
see RTS but not CTS: ok to
transmit
neighbors silent until see ACK
Collisions



no collisions detection
known when don’t receive CTS
exponential backoff
16
Hidden & Exposed nodes
17
Collisions Avoidance


Similar to Ethernet
Problem: hidden and exposed nodes
Hidden node
Exposed
node
A
B
C
D
Sending
node
18
Point to Point Data Link Control

one sender, one receiver, one link: easier than broadcast link:
 no Media Access Control
no need for explicit MAC addressing
 e.g., dialup link, ISDN line
popular point-to-point Data Link Control protocols:
 PPP (point-to-point protocol)
 Protocol choice for dialup link.


19
Point-to-Point (serial) links

Many data link connections are
point-to-point serial links:



Dial-in or DSL access connects hosts to
access routers
Routers are connected by
high-speed point-to-point links
IP hosts and routers are connected
by a serial cable
 Data link layer protocols for pointto-point links are simple:


Access
Router
Modems
Dial-Up Access
Router
Main role is encapsulation of IP
datagrams
No media access control needed
Router
Router
Point-to-Point Links
Router
20
Data Link Protocols for Point-to-Point links

SLIP (Serial Line IP)



PPP (Point-to-Point Protocol):
•
•

First protocol for sending IP datagrams over dial-up
links (from 1988)
Encapsulation, not much else
Successor to SLIP (1992), with added functionality
Used for dial-in and for high-speed routers
HDLC (High-Level Data Link) :
•
•
•
Widely used and influential standard (1979)
Default protocol for serial links on Cisco routers
Actually, PPP is based on a variant of HDLC
21
PPP - IP encapsulation

The frame format of PPP is similar to HDLC and the 802.2 LLC frame
format:
flag



addr ctrl
7E
FF
03
1
1
1
protocol
data
CRC
flag
7E
2
<= 1500
0021
IP datagram
C021
link control data
8021
network control data
PPP assumes a duplex circuit
Note: PPP does not use addresses
Usual maximum frame size is 1500
2
1
22
Additional PPP functionality

In addition to encapsulation, PPP supports:
 multiple network layer protocols (protocol multiplexing)
 Link configuration
 Link quality testing
 Error detection
 Option negotiation
 Address notification
 Authentication

The above functions are supported by helper protocols:
 LCP
 PAP, CHAP
 NCP
23
PPP Support protocols
 Link
management: The link control protocol (LCP) is
responsible for establishing, configuring, and negotiating a
data-link connection. LCP also monitors the link quality and is
used to terminate the link.
 Authentication:
Authentication is optional. PPP supports two
authentication protocols: Password Authentication Protocol
(PAP) and Challenge Handshake Authentication Protocol
(CHAP).
 Network
protocol configuration: PPP has network control
protocols (NCPs) for numerous network layer protocols. The IP
control protocol (IPCP) negotiates IP address assignments
and other parameters when IP is used as network layer.
24