Transcript lecture

Link Layer 3
Mozafar Bag-Mohammadi
University of Ilam
Token Ring Overview
 Examples
 16Mbps IEEE 802.5 (based on earlier IBM ring)
 100Mbps Fiber Distributed Data Interface (FDDI)
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
Timed Token Algorithm
 Token Holding Time (THT)
 upper limit on how long a station can hold the token
 Token Rotation Time (TRT)
 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
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
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
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
Wireless LANs
 IEEE 802.11
 Physical Media
 spread spectrum radio (2.4GHz)
 diffused infrared (10m)
Spread Spectrum
 Idea
 spread signal over wider frequency band than required
 originally designed to thwart jamming
 Frequency Hopping
 Direct Sequence
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
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
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.
Supporting Mobility
ad hoc networking
 Case 2: access points (AP)
 Case 1:


tethered
each mobile node associates with an AP
Distribution system
AP-1
AP-3
F
AP-2
A
B
G
H
C
E
D
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
STA
Ad Hoc
Network
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
 State of operation:
 active: when join or move
 passive: AP periodically sends Beacon frame
MACAW
 Sender transmits
RequestToSend (RTS) frame
 Receiver replies with
ClearToSend (CTS) frame
 Neighbors…


see CTS: keep quiet
see RTS but not CTS: ok to
transmit
 Receiver sends ACK when it
has frame

neighbors silent until see
ACK
 Collisions



no collisions detection
known when don’t receive
CTS
exponential backoff
Hidden & Exposed nodes
Hidden node
Exposed node
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.
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
Access
Router
Modems
Dial-Up Access
 IP hosts and routers are connected
by a serial cable

Data link layer protocols for pointto-point links are simple:
• Main role is encapsulation of IP
datagrams
• No media access control needed
Router
Router
Router
Point-to-Point Links
Router
Data Link Protocols for Point-to-Point links
 HDLC (High-Level Data Link) :
 Widely used and influential standard (1979)
 Default protocol for serial links on Cisco routers
 SLIP (Serial Line IP)


First protocol for sending IP datagrams over dial-up links
(from 1988)
Encapsulation, not much else
 PPP (Point-to-Point Protocol):

Successor to SLIP (1992), with added functionality
Used for dial-in and for high-speed routers

Actually, PPP is based on a variant of HDLC

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
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
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.