Transcript ppt - The Fengs

CSE524: Lecture 17
Data-link layer
Specific link layers and devices
1
Where we’re at…
•
•
•
•
•
•
Internet architecture and history
Internet protocols in practice
Application layer
Transport layer
Network layer
Data-link layer
– Functions
– Specific link layer examples and devices
• Physical layer
2
DL/NL: ATM
• ATM
– Replace existing Internet protocols with a more “robust”
architecture
– Network architecture to support
• Multiple service classes and per-flow guarantees
• Virtual circuits to support real-time applications
• Explicit rate signaling and resource allocation
• Covered as a data-link layer…
3
DL/NL: Internet vs. ATM
• Internet
– “elastic” datagram service,
no strict timing req.
– Computer communication
only
– “smart” end systems
(computers)
• can adapt, perform control,
error recovery
• simple inside network,
complexity at “edge”
• ATM
– evolved from telephony,
strict timing and reliability
requirements
– Computer and human
communication
• need for guaranteed service
– “dumb” end systems
• telephones
• complexity inside network
– many link types
• different characteristics
• uniform service difficult
4
DL/NL: ATM Layer: Virtual Circuits
• VC transport: cells carried on VC from source to dest
– call setup, teardown for each call before data can flow
– each packet carries VC identifier (not destination ID)
– every switch on source-dest path maintain “state” for each
passing connection
– link, switch resources (bandwidth, buffers) may be
allocated to VC: to get circuit-like perf.
• Permanent VCs (PVCs)
– long lasting connections
– typically: “permanent” route between to IP routers
• Switched VCs (SVC):
– dynamically set up on per-call basis
5
DL/NL: ATM VCs
• Advantages of ATM VC approach:
– QoS performance guarantee for connection mapped to VC
(bandwidth, delay, delay jitter)
• Drawbacks of ATM VC approach:
– Overhead in call setup for SVCs
• SVC introduces call setup latency, processing overhead for short lived
connections
– Lack of scalability for PVCs
• one PVC between each source/dest pair does not scale (N*2 connections
needed)
6
DL/NL: ATM Layer: ATM cell
• 5-byte ATM cell header
• 48-byte payload (fixed)
– Why?: small payload -> short cell-creation delay for digitized
voice
– halfway between 32 and 64 (compromise!)
Cell header
Cell format
7
DL/NL: ATM cell header
• VCI: virtual channel ID
– will change from link to link thru net
• PT: Payload type (e.g. RM cell versus data cell)
• CLP: Cell Loss Priority bit
– CLP = 1 implies low priority cell, can be discarded if
congestion
• HEC: Header Error Checksum
– cyclic redundancy check
8
DL: ATM: network or link layer?
• Vision
– ATM end-to-end from desktop
to desktop
• Both a network and a data-link
layer technology
• Reality
– Used mostly as a switched
link-layer to connect IP routers
• “IP over ATM”
• replace IP network+routers with
ATM network+switches
• At edges, map ATM addresses to
IP addresses and vice-versa
9
DL: ATM and “IP switching”
• ATM advantages
– Lookup of VCID = O(1), Lookup of IP routes O(log n)
– One-time route lookup and circuit establishment, all subsequent traffic
switched
• ATM disadvantages
– Complex signaling and routing for establishing communication
– Difficulty in mapping IP traffic dynamically onto ATM circuits
• Goal
– Maintain IP infrastructure
– Accelerate it with labels to support O(1) lookups a la ATM
• Solution
– Ipsilon and “IP switching”
– http://pnewman.org/papers/infocom96.pdf
10
IP over ATM versus IP switching
IP network control
IP routing
IP network control
IP routing
ATM network control
ATM label switching
IP network control
IP routing
IP network control
ATM label switching
IP network control
IP routing
11
DL: ATM and “IP switching”
• In a nutshell
–
–
–
–
Start with ATM switch
Rip out ATM signaling and routing
Add IP routing software
Add Flow classifier to map unknown flows to underlying ATM virtual circuit
ID
– Attach VCID and allow downstream nodes to do the same
• Operation
– Upon arrival of first packet in flow
• Record unknown incoming VCID
• Lookup IP flow and map it to an outgoing virtual circuit ID (label) using IP
routing software
• Create incomingVCID to outgoingVCID table entry for subsequent packets
– Subsequent packets
• Switched in hardware using VCID after flow classified at edge
• IP packet forwarding done as label index lookup O(1) versus IP route lookup
12
O(log n)
DL: ATM and “IP switching”
• Later generalized as MPLS (multi-protocol label
switching)
–
–
–
–
“Layer 2 ½”
Not tied to ATM
Extensible to IPv6
Half-way in between data-link addresses and IP addresses
• Labeling done within a cloud versus link-local (data-link addresses)
and global (IP addresses)
– http://www.rfc-editor.org/rfc/rfc3031.txt
• Used as a tool for traffic engineering
– http://www.rfc-editor.org/rfc/rfc2702.txt
13
DL: X.25 and Frame Relay
Like ATM:
• wide area network technologies
• virtual circuit oriented
• origins in telephony world
• Not really a link layer but....
– Viewed as link layers by IP protocol
– Used mostly to carry IP datagrams between IP routers
• Going the way of the dinosaurs....
14
DL: X.25
• X.25 builds VC between source and destination for each user connection
• Per-hop control along path
– error control (with retransmissions) on each hop using LAP-B
• variant of the HDLC protocol
• developed when bit error rates over long-haul copper links were
orders of magnitude higher
– per-hop flow control using credits
• congestion arising at intermediate node propagates to previous node
on path
• back to source via back pressure
15
DL: IP versus X.25
• X.25: reliable in-sequence end-end delivery from endto-end
– “intelligence in the network”
– built for dumb terminals accessing mainframes
• IP: unreliable, out-of-sequence end-end delivery
– “intelligence in the endpoints”
• 2000
– gigabit routers: limited processing possible
– CPU capacity at end-hosts
– IP wins
16
DL: Frame Relay
• Designed in late ‘80s, widely deployed in the ‘90s
– Second-generation X.25
• Frame relay service:
–
–
–
–
no error control
no flow control
End-to-end congestion control
Some QoS mechanisms
17
DL: Frame Relay (more)
• Designed to interconnect corporate customer LANs
– typically permanent VC’s: “pipe” carrying aggregate
traffic between two routers
– switched VC’s: as in ATM
• corporate customer leases FR service from public
Frame Relay network (eg, Sprint, ATT)
18
DL: Frame Relay (more)
flags
address
data
CRC
flags
• Flag bits, 01111110, delimit frame
• address:
– 10 bit VC ID field
– 3 congestion control bits
• FECN: forward explicit congestion notification (frame
experienced congestion on path)
• BECN: congestion on reverse path
• DE: discard eligibility
– Precursor to IP DiffServ and ECN
19
DL: Frame Relay -VC Rate Control
• Committed Information Rate (CIR)
– defined, “guaranteed” for each VC
– negotiated at VC set up time
– customer pays based on CIR
• DE bit: Discard Eligibility bit
– Edge FR switch measures traffic rate for each VC; marks DE
bit
– DE = 0: high priority, rate compliant frame; deliver at “all
costs”
– DE = 1: low priority, eligible for discard when congestion
– Precursor to IP DiffServ
– Can be used to support higher layer QoS mechanisms
20
DL: Link-layer devices
Q: Why not just one big LAN?
• Limited amount of supportable traffic: on single LAN, all
stations must share bandwidth
• limited length: 802.3 specifies maximum cable length
• large “collision domain” (can collide with many stations)
• limited number of stations: 802.5 have token passing
delays at each station
21
DL: Hubs
• Effectively a physical layer device
– Multi-port repeater
– Repeater operating at bit level
– Repeat received bits on one interface to all other interfaces
• Hubs can be arranged in a hierarchy (or multi-tier design), with backbone
hub at its top
22
DL: Hubs (more)
• Each connected LAN referred to as LAN segment
• Hubs do not isolate collision domains: node may collide
with any node residing at any segment in LAN
• Hub Advantages:
– simple, inexpensive device
– Multi-tier provides graceful degradation: portions of the LAN
continue to operate if one hub malfunctions
– extends maximum distance between node pairs
23
DL: Hub limitations
• single collision domain results in no increase in max
throughput
– multi-tier throughput same as single segment throughput
• individual LAN restrictions pose limits on
– number of nodes in same collision domain
– total allowed geographical coverage
• cannot connect different Ethernet types (e.g., 10BaseT
and 100baseT)
24
DL: Bridges
• Link Layer devices: operate on Ethernet frames,
examining frame header and selectively forwarding
frame based on its destination
• Bridge isolates collision domains since it buffers frames
• When frame is to be forwarded on segment, bridge uses
CSMA/CD to access segment and transmit
25
DL: Bridges (more)
• Bridge advantages:
– Isolates collision domains resulting in higher total max
throughput, and does not limit the number of nodes nor
geographical coverage
– Can connect different type Ethernet since it is a store and
forward device
– Transparent: no need for any change to hosts LAN adapters
26
DL: Backbone Bridge
27
DL: Interconnection Without Backbone
• Not recommended for two reasons:
– - single point of failure at Computer Science hub
– - all traffic between EE and SE must path over CS segment
28
DL: Bridges: frame filtering, forwarding
• Bridges filter packets
– same-LAN -segment frames not forwarded onto other LAN
segments
• Forwarding:
– how to know which LAN segment on which to forward frame?
– looks like a routing problem
• Solution: Learning bridges
– Monitor traffic to build a cache of which nodes are downstream
of which ports
– Selectively forward frames based on cache entries
– Flood network for frames with unknown (MAC) destinations
29
DL: Bridge Filtering
• Bridges maintain filtering tables
– Indicate which hosts can be reached through which interfaces
– When frame received, bridge “learns” location of sender
• Records sender port location in filtering table
• Filtering table entry:
– (Node LAN Address, Bridge Interface, Time Stamp)
– Stale entries in Filtering Table dropped (TTL can be 60 minutes)
30
DL: Bridge Filtering
• filtering procedure:
if destination is on LAN on which frame was received
then drop the frame
else { lookup filtering table
if entry found for destination
then forward the frame on interface indicated;
else flood; /* forward on all but the interface on
which the frame arrived*/
}
31
DL: Bridge Learning: example
• C sends frame to D
– Bridge has no info about D
– Bridge notes that C is on LAN segment #1
– Bridge floods to both LAN segments #2 and #3
• frame ignored on upper LAN
• frame received by D
• D replies back with frame to C
– Bridge knows C is on LAN segment #1
– Bridge notes that D is on LAN segment #2
– Bridge forwards frame only on to LAN segment #1
32
DL: Bridges and Spanning Trees
• for increased reliability, desirable to have redundant, alternate
paths from source to destination
• with multiple simultaneous paths, cycles result - bridges may
multiply and forward frame forever
• solution: organize bridges in a spanning tree by disabling
subset of interfaces
Disabled
33
DL: Switching
• Switches
–
–
–
–
“multi-port bridge”
Each port acts as a bridge
Each port determines MAC addresses connected to itself
Master list within switch determines forwarding behavior
34
DL: Ethernet Switches
• Switching faster:
– A-to-B and A’-to-B’
simultaneously, no collisions
– layer 2 (frame) filtering using
LAN addresses
– large number of interfaces
versus bridges (which typically
have only two)
– Flexibly support multiple
speeds (10/100/1000)
– often: individual hosts, starconnected into switch
– Ethernet, but no collisions!
35
DL: Switched Network Advantages
• Higher link bandwidth
– Point to point electrically simpler than bus
• Much greater aggregate bandwidth
– Data backplane of switches typically large to support
simultaneous transfers amongst port
• Can go faster via “cut-through switching”
– Frame forwarded from input to output port without awaiting
for assembly of entire frame
– Slight reduction in latency
36
DL: Bridges vs. Routers
• both store-and-forward devices
– routers: network layer devices (examine network layer headers)
– bridges are Link Layer devices
• routers maintain routing tables, implement routing algorithms
• bridges maintain filtering tables, implement filtering, learning and
spanning tree algorithms
• why can't the Internet be one great big bridge?
37
DL: Routers vs. Bridges
Bridges + and + Bridge operation is simpler requiring less processing bandwidth
- Topologies are restricted with bridges: a spanning tree must be built to avoid
cycles
- Bridges do not offer protection from broadcast storms (endless broadcasting by a
host will be forwarded by a bridge)
38
DL: Routers vs. Bridges
Routers + and + arbitrary topologies can be supported, cycling is
limited by TTL counters (and good routing protocols)
+ provide protection against broadcast storms
- require IP address configuration (not plug and play)
- require higher processing bandwidth
• bridges do well in small (few hundred hosts) while
routers used in large networks (thousands of hosts)
39
Data-link layer summary
• principles behind data link layer services:
– error detection, correction
– sharing a broadcast channel: multiple access
– link layer addressing, ARP
• various link layer implementations
–
–
–
–
–
–
•
802.3 Ethernet
802.5 Token-ring
802.11 LANs
PPP
ATM
X.25, Frame Relay
various link layer devices
– hubs, bridges, switches
40
Physical Layer
• Plethora of physical media
–
–
–
–
Fiber, copper, air
Specifies the characteristics of transmission media
Too many to cover in detail, not the focus of the course
Many data-link layer protocols (i.e. Ethernet, Token-Ring, FDDI.
ATM run across multiple physical layers)
– Physical characteristics dictate suitability of data-link layer
protocol and bandwidth limits
41
PL: Common Cabling
• Copper
– Twisted Pair
• Unshielded (UTP)
– CAT-1, CAT-2, CAT-3, CAT-4, CAT-5, CAT-5e
• Shielded (STP)
– Coaxial Cable
• Fiber
– Single-mode
– Multi-mode
42
PL: Twisted Pair
• Most common LAN interconnection
• Multiple pairs of twisted wires
• Twisting to eliminate interference
– More twisting = Higher data rates, higher cost
• Standards specify twisting, resistance, and
maximum cable length for use with particular
data-link layer
43
PL: Twisted pair
• 5 categories
– Category 1
• Voice only (telephone wire)
– Category 2
• Data to 4Mbs (LocalTalk)
– Category 3
• Data to 10Mbs (Ethernet)
– Category 4
• Data to 20Mbs (16Mbs Token Ring)
– Category 5 (100 MHz)
• Data to 100Mbs (Fast Ethernet)
– Category 5e (350 MHz)
• Data to 1000Mbs (Gigabit Ethernet)
44
PL: Twisted Pair
• Common connectors for Twisted Pair
– RJ11 (3 pairs)
– RJ45 (4 pairs)
• Allows both data and phone connections
• (1,2) and (3,6) for data, (4,5) for voice
• Crossover cables for NIC-NIC, Hub-Hub connection (Data
pairs swapped)
45
PL: UTP
• Unshielded Twisted Pair
– Limited amount of protection from interference
– Commonly used for voice and ethernet
• Voice: multipair 100-ohm UTP
46
PL: STP
• Shielded Twisted Pair
–
–
–
–
–
Not as common at UTP
UTP susceptible to radio and electrical interference
Extra shielding material added
Cables heavier, bulkier, and more costly
Often used in token ring topologies
• 150 ohm STP two pair (IEEE 802.5 Token Ring)
47
PL: Coaxial cable
• Single copper conductor at center
• Plastic insulation layer
• Highly resistant to interference
– Braided metal shield
– Support longer connectivity distances over UTP
48
PL: Coaxial cable
• Thick (10Base5)
– Large diameter 50-ohm cable
– N connectors
• Thin (10Base2) cables
– Small diameter 50-ohm cable
– BNC, RJ-58 connector
• Video cable
– 75-ohm cable
– BNC, RJ-59 connector
– Not compatible with RJ-58
49
PL: Fiber
• Center core made of glass or plastic fiber
• Transmit light versus electronic signals
– Protects from electronic interference, moisture
• Plastic coating to cushion core
• Kevlar fiber for strength
• Teflon or PVC outer insulating jacket
50
PL: Fiber
• Single-mode fiber
–
–
–
–
–
–
Smaller diameter (12.5 microns)
One mode only
Preserves signal better over longer distances
Typically used for SONET or SDH
Lasers used to signal
More expensive
• Multi-mode fiber
–
–
–
–
Larger diameter (62.5 microns)
Multiple modes
LEDs used to signal
WDM and DWDM
• Photodiodes at receivers
51
PL: Fiber connectors
• ESCON
• Duplex SC
• ST
• MT-RJ (multimode)
• Duplex LC
52
PL: Wireless
• Entire spectrum of transmission frequency ranges
–
–
–
–
–
–
–
–
Radio
Infrared
Lasers
Cellular telephone
Microwave
Satellite
Acoustic (see ESE sensors)
Ultra-wide band
• http://www.ntia.doc.gov/osmhome/allochrt.html
53
54
PL: What runs on them?
Protocol Summary
Protocol
Cable
Speed
Topology
Ethernet
Twisted Pair, Coaxial, Fiber
10 Mbps
Linear Bus, Star, Tree
Fast Ethernet
Twisted Pair, Fiber
100 Mbps
Star
LocalTalk
Twisted Pair
.23 Mbps
Linear Bus or Star
Token Ring
Twisted Pair
4 Mbps - 16 Mbps
Star-Wired Ring
FDDI
Fiber
100 Mbps
Dual ring
ATM
Twisted Pair, Fiber
155-2488 Mbps
Linear Bus, Star, Tree
55
PL: Physical-link lingo
• Specifies capacities over physical media
• Electronic
– T1/DS1=1.54 Mbps
– T3/DS3=45Mbps
• Optical (OC=optical carrier)
–
–
–
–
–
–
OC1=52 Mbps
OC3/STM1=156 Mbps
OC12=622 Mbps
OC48=2488 Mbps
OC192=10 Gbps
OC768=40 Gbps
56