Transcript Chap. 5 - WINSLab

Ch 5. The Link Layer and Local Area
Networks
Myungchul Kim
[email protected]
–
–
–
–
Frame
Error detection, retransmission, flow control, random access
Ethernet, IEEE 802.11 wireless LAN (WiFi), Token Ring, PPP,
ATM
Services offered by a link-layer protocol







–
Framing
Link access: Medium Access Control (MAC) protocol
Reliable delivery
Flow control
Error detection
Error correction
Half-duplex and full-duplex
The services by the link layer vs the transport layer
2
3
–
–
The link layer is implemented in a network adaptor known as a
network interface card (NIC)
LAN-on-motherboard configuration
4
Error-Detection and –Correction
Techniques
5

Parirty checks
6
–

Forward error correction (FEC)
Checksumming methods
–
–
The receiver checks the checksum by taking the 1s complement
of the sum of the received data (including the checksum).
Why checksumming at the Transport layer and CRC at the link
layer?
7

Cyclic Redundancy Check (CRC)
-
generator: The sender and receiver must agree on an r+1 bit pattern
D * 2 r XOR R = nG
D * 2 r = nG XOR R
R = remainder D * 2 r / G
The CRC standards can detect burst errors of fewer than r+1 bits.
8
9
Multiple access protocols
–
–
–
–
Point-to-point link
Broadcast link: medium access problem
Multiple access protocols
Channel partitioning protocols, random access rptocols and
taking-turns protocols
10
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
11

Channel partitioning protocols
–
Code Division Multiple Access (CDMA)
12
–
ALOHA





All frames L bits
Time slots of size L/R seconds
The nodes are synchronized so that each node knows when the
slots begin.
If two or more frames collide in a slot, then all the nodes detect the
collision event before the slot ends.
Max efficiency of the protocol 1/e = 0.37
13
–
ALOHA

Max efficiency of the protocol 1/2e
14
–
Carrier Sense Multiple Access (CSMA)



Listen before speaking: carrier sensing
If someone else begins talking at the same time, stop talking:
collision detection
CSMA, CSMA/CD
15
16
17

Taking-Turns protocols
–
–

Polling protocols: a master node
Token-passing protocol: no master node
Local Area Networks (LANs)
–
–
–
Ethernet: IEEE 802.3
Token Ring: IEEE 802.5
Fiber Distribution Data Interface (FDDI)
18
Link-layer addressing

MAC address
–
–
Link-layer address, LAN address, MAC address
6 bytes long = 2 48 possible MAC addresses
19
–
–

No two adaptors have the same address
A flat structure
Address Resolution Protocol (ARP)
–
–
–
–
To send a datagram, the source node must give its adapter not
only the IP datagram but also the MAC address for destination
node.
An ARP module in the sending node takes any IP address on the
same LAN as input, and returns the corresponding MAC address.
DNS vs ARP
ARP query and response
20
21
–
Sending a datagram to a node off the subnet
22








A creates IP datagram with source A, destination B
A uses ARP to get R’s MAC address for 111.111.111.110
A creates link-layer frame with R's MAC address as dest, frame
contains A-to-B IP datagram
A’s NIC sends frame
R’s NIC receives frame
R removes IP datagram from Ethernet frame, sees its destined to B
R uses ARP to get B’s MAC address
R creates frame containing A-to-B IP datagram sends to B
88-B2-2F-54-1A-0F
74-29-9C-E8-FF-55
A
E6-E9-00-17-BB-4B
111.111.111.111
222.222.222.220
111.111.111.110
111.111.111.112
222.222.222.221
1A-23-F9-CD-06-9B
R
222.222.222.222
B
49-BD-D2-C7-56-2A
CC-49-DE-D0-AB-7D
23
Ethernet
–
Success factors



–
First widely deployed
Simple and cheap
Kept up with speed race
Hub: whenever a hub receives a bit from one of its interfaces, it
sends a copy of the bit to all of its other interfaces.
24
–
Ethernet frame structure






–
–
Data field (46 to 1,500 bytes): MTU
Destination address (6bytes)
Source address (6 bytes)
Type field (2 bytes): IP and other network layer protocols
CRC (4 bytes)
Preamble (8 bytes)
Connectionless service
Unreliable service
25

CSMA/CD: Ethernet’s Multiple Access Protocol
1.
2.
3.
4.
An adapter may begin to transmit at any time.
An adapter never transmits a frame when it senses that some
other adapter is transmitting. (carrier sensing)
A transmitting adapter aborts its transmission as soon as it
detects that another adapter is also transmitting. (collision
detection)
Before attempting a retransmission, and adapter waits a
random time that is typically samll compared with the time to
transmit a frame. (exponential backoff)
26
–

Ethernet efficiency = 1 / (1 + 5 d prop / d trans ) where
d prop = max time to propagate between any two adapters and
d trans = the time to transmit a maximum-size Ethernet fame.
Ethernet Technologies
–
–
Repeater
Point-to-point linkes use switches (no collision, no MAC protocol)
while broadcast channels use hubs
27
Link-layer switches
–
–
–
–
The role of the switch is to receive incoming link-layer frames
and forward them onto outgoing links.
Filtering
Forwarding
Switch table
28
29
–
Suppose a frame arrives at the switch on interface x, the switch
does



–
If there is no entry for the destination address, the switch
broadcasts the frame.
There is an entry in the table with interface x, the switch performs
the filtering by discarding the frame.
There is an entry in the table with interface y ≠ x, the switch
performs its forwarding.
As long as the switch table is complete and accurate, the switch
forwards frames towards destination without any broadcasting.
30

Self-Learning
–
–
–
–
The switch table is initially empty.
For each incoming frame received on an interface, the switch
stores in its table …
Aging time
Plug-and-play devices
31

Properties of link-layer switching
–
–
–

Elimination of collisions
Heterogeneous links
Management
Switches vs routers
–
–
–
Switch: layer 2, router: layer 3
Switch: plug-and-play, a spanning tree, hundreds hosts
Router: hierachical, thousands of hosts
32
PPP: The Point-to-Point Protocol
–
Error detection
No flow control
No sequencing
Single point link
–
Information: max length 1,500 bytes
–
–
–
33
34
Link Virtualization: A Network as a Link
Layer
–

ATM, MPLS: packet-switched, virtual-circuit networks
Asynchronous Transfer Mode (ATM) networks
35
–
An ATM inferface will have an IP address and an ATM address.
36

Mulitprotocol Label Switching (MPLS)
–
–
–
Like a switched LAN or ATM network, the MPLS-capable
routers do without ever touching the IP header of a packet.
Traffic engineering
Virtual private network
37
38