代写代考 BB-76-09-AD

3rd Edition: Chapter 4

Computer Networking: A Top Down Approach

Copyright By PowCoder代写 加微信 powcoder

7th edition
April 2016
The Link Layer and LANs

The Powerpoint slides are from Kurose and Ross’s book’s website.

Chapter 6: Link layer and LANs
our goals:
understand principles behind link layer services:
error detection, correction
sharing a broadcast channel: multiple access
link layer addressing
local area networks: Ethernet
instantiation, implementation of various link layer technologies
Link Layer

Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request

Link Layer

Link layer: introduction
terminology:
hosts and routers: nodes
communication channels that connect adjacent nodes along communication path: links
wired links
wireless links
layer-2 packet: frame, encapsulates datagram

link layer has responsibility of
transferring datagram from one node
to physically adjacent node over a link

Link Layer

Link layer: context
datagram transferred by different link protocols over different links:
e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link
each link protocol provides different services
e.g., may or may not provide rdt over link
Link Layer

Link layer services
framing, link access:
encapsulate datagram into frame, adding header, trailer
channel access if shared medium
“MAC” addresses used in frame headers to identify source, destination
different from IP address!
reliable delivery between adjacent nodes
seldom used on low bit-error link (fiber, some twisted pair)
may be needed for high error rate link (wireless)
Link Layer

flow control:
control transmission rate between adjacent sending and receiving nodes
error detection:
errors caused by signal attenuation, noise
receiver detects presence of errors:
signals sender for retransmission or drops frame
error correction:
receiver identifies and corrects bit error(s) without resorting to retransmission
half-duplex and full-duplex
with half duplex, nodes at both ends of link can transmit, but not at same time
Link layer services (more)
Link Layer

Where is the link layer implemented?
in every host, link layer is implemented in “adaptor” (aka network interface card NIC) or on a chip
Ethernet card, 802.11 card; Ethernet chipset
implement link, physical layer
attach to host’s system buses
combination of hardware, software, firmware

controller

(e.g., PCI)

network adapter card

application

transmission
Link Layer

Adaptors communicating
sending side:
encapsulates datagram in frame
adds error checking bits, rdt, flow control, etc.
receiving side
looks for errors, rdt, flow control, etc.
extracts datagram, passes to upper layer

controller

controller

sending host
receiving host

Link Layer

Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request

Link Layer

Error detection

EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields

Error detection not 100% reliable!
protocol may miss some errors, but rarely
larger EDC field yields better detection and correction

Link Layer

Parity checking

single bit parity:
detect single bit errors

two-dimensional bit parity:
detect and correct single bit errors

parity error
Link Layer

Internet checksum (review)
treat segment contents as sequence of 16-bit integers
checksum: addition (1’s complement sum) of segment contents
sender puts checksum value into UDP checksum field

compute checksum of received segment
check if computed checksum equals checksum field value:
NO – error detected
YES – no error detected. But maybe errors nonetheless?
goal: detect “errors” (e.g., flipped bits) in transmitted packet (note: used at transport layer only)

Link Layer

Cyclic redundancy check
more powerful error-detection coding, widely used in practice (Ethernet, 802.11 WiFi)
view data bits, D, as a binary number
choose r+1 bits (generator), G
goal: choose r CRC bits, R, such that
exactly divisible by G (modulo 2)
receiver knows G, divides by G. If non-zero remainder: error detected!
can detect all burst errors less than r+1 bits

Link Layer

CRC example
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by G, we want remainder R to satisfy:
R = remainder[ ]

Link Layer

Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request

Link Layer

Multiple access links
two types of “links”:
point-to-point
dial-up access
point-to-point link between Ethernet switch and host
broadcast (shared wire or wireless medium)
old-fashioned Ethernet
802.11 wireless LAN

shared wire (e.g.,
cabled Ethernet)
(e.g., 802.11 WiFi)
(satellite)

Link Layer

Multiple access protocols
multiple users share single broadcast channel
single shared broadcast channel
two or more simultaneous transmissions by nodes: interference
collision if node receives two or more signals at the same time

multiple access protocol
distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit
inbound channel for coordination (no out-of-band channel)
use channel itself for communication about how channel is shared!
Link Layer

MAC protocols
three broad classes:
channel partitioning
divide channel into smaller “pieces” (time slots, frequency, code)
allocate one piece to one node for exclusive use
random access
channel not divided, allow collisions
“recover” from collisions
“taking turns”
nodes take turns, and nodes with more to send can take longer turns
Link Layer

Channel partitioning MAC protocols: TDMA
TDMA: time division multiple access
channel time divided into fixed length slots
each station gets a slot (slot length = packet transmission time) in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have packets to send, slots 2,5,6 idle

Link Layer

FDMA: frequency division multiple access
channel spectrum divided into frequency bands
each station assigned a fixed frequency band
unused transmission time in frequency bands go idle
example: 6-station LAN, 1,3,4 have packet to send, frequency bands 2,5,6 idle

frequency bands

Channel partitioning MAC protocols: FDMA
Link Layer

Random access protocols
when node has packet to send
transmit at full channel data rate
no a priori coordination among nodes
two or more nodes transmitting ➜ collision
random access MAC protocol specifies
how to detect collisions
how to recover from collisions (e.g., via delayed retransmissions)
examples of random access MAC protocols:
ALOHA, slotted ALOHA
CSMA, CSMA/CD, CSMA/CA

Link Layer

Pure (unslotted) ALOHA
stations access channel at will and may cause collisions when two or more stations access the channel at some overlapped time instant
simpler, no synchronization

Link Layer

Slotted ALOHA

channel time is divided into slots
stations access channel at beginning of each slot
frame transmission occupies the entire slot
if one or more other stations access the same slot, collision occurs; frame is wiped out by collision

Link Layer

CSMA (carrier sense multiple access)
CSMA: listen before transmit:
if channel sensed idle, transmit entire frame
if channel sensed busy, defer transmission
collisions can still occur:
propagation delay will cause two nodes not to hear each other’s transmission at the same time
when collision occurs, entire packet transmission time wasted

spatial layout of nodes

Link Layer

CSMA/CD (collision detection)
CSMA/CD: carrier sensing, deferral as in CSMA
collisions detected within short time
colliding transmissions aborted, reducing channel wastage
collision detection:
easy in wired LANs: measure signal strengths, compare transmitted, received signals
difficult in wireless LANs: received signal strength overwhelmed by local transmission strength
better performance than ALOHA, and simple, cheap, decentralized!
Link Layer

CSMA/CD (collision detection)

spatial layout of nodes

Link Layer

“Taking turns” MAC protocols
channel partitioning MAC protocols:
share channel efficiently and fairly at high load
inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node!
random access MAC protocols
efficient at low load: single node can fully utilize channel
high load: collision overhead
“taking turns” protocols
look for best of both worlds!
Link Layer

master node “invites” slave nodes to transmit in turn
typically used with “dumb” slave devices
polling overhead
single point of failure (master)

“Taking turns” MAC protocols
Link Layer

token ring:
control token passed from one node to next sequentially.
token overhead
single point of failure (token)

“Taking turns” MAC protocols
Link Layer

Summary of MAC protocols
channel partitioning, by time, frequency or combination
Time Division, Frequency Division
random access (dynamic)
ALOHA, Slotted-ALOHA, CSMA, CSMA/CD
carrier sensing: easy in some technologies (wire), hard in others (wireless)
CSMA/CD used in Ethernet
taking turns
polling from central site
token ring
Link Layer

Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request

Link Layer

MAC addresses
32-bit IP address:
network-layer address for interface
used for layer 3 (network layer) forwarding
MAC (or LAN or physical or Ethernet) address:
function: used ‘locally” to send frame from one interface to another physically-connected interface (same network)
48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
e.g.: 1A-2F-BB-76-09-AD

hexadecimal (base 16) notation
(each “numeral” represents 4 bits)

Link Layer

LAN addresses
each adapter on LAN has unique LAN address

1A-2F-BB-76-09-AD

58-23-D7-FA-20-B0

0C-C4-11-6F-E3-98

71-65-F7-2B-08-53

Network Layer: Data Plane

LAN addresses (more)
MAC address allocation administered by IEEE
manufacturer obtains portion of MAC address space (to assure uniqueness)
MAC flat address is portable
can move LAN card from one LAN to another
IP hierarchical address not portable
address depends on IP subnet to which node is attached

Network Layer: Data Plane

Translation of Addresses
Network Layer: Data Plane
Translation between IP addresses and MAC addresses
Address Resolution Protocol (ARP) for mapping an IP address to a MAC address
Reversed ARP (RARP) for mapping a MAC address to an IP address

IP address
MAC address

IP address
MAC address

ARP: address resolution protocol
ARP table: each node (host, router) on LAN has table
IP/MAC address mappings for some LAN nodes:
< IP address; MAC address; TTL>
TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)
Question: how to determine
interface’s MAC address, knowing its IP address?

1A-2F-BB-76-09-AD

58-23-D7-FA-20-B0

0C-C4-11-6F-E3-98

71-65-F7-2B-08-53
137.196.7.23

137.196.7.78

137.196.7.14

137.196.7.88

Network Layer: Data Plane

ARP protocol: same LAN
A wants to send datagram to B
B’s MAC address not in A’s ARP table.
A broadcasts ARP query packet, containing B’s IP address
destination MAC address =
FF-FF-FF-FF-FF-FF
all nodes on LAN receive ARP query
B receives ARP packet, replies to A with its (B’s) MAC address
frame sent to A’s MAC address (unicast)
A caches (saves) IP-to-MAC address pair in its ARP table until information becomes stale (times out)
soft state: information that times out unless refreshed
ARP is “plug-and-play”:
nodes create their ARP tables without intervention from net administrator

Network Layer: Data Plane

walkthrough: send datagram from A to B via R
focus on addressing – at IP (datagram) and MAC layer (frame)
assume A knows B’s IP address
assume A knows IP address of first hop router, R (via DCHP)
assume A knows R’s MAC address (via ARP)
Addressing: routing to another LAN

1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55

222.222.222.222
49-BD-D2-C7-56-2A

222.222.222.221
88-B2-2F-54-1A-0F

Network Layer: Data Plane

1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55

222.222.222.222
49-BD-D2-C7-56-2A

222.222.222.221
88-B2-2F-54-1A-0F

Addressing: routing to another LAN

IP src: 111.111.111.111
IP dest: 222.222.222.222

A creates IP datagram with IP source A, destination B
A creates link-layer frame with R’s MAC address as destination address, frame contains A-to-B IP datagram
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B

Network Layer: Data Plane

1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55

222.222.222.222
49-BD-D2-C7-56-2A

222.222.222.221
88-B2-2F-54-1A-0F

Addressing: routing to another LAN

frame sent from A to R

frame received at R, datagram removed, passed up to IP
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B

IP src: 111.111.111.111
IP dest: 222.222.222.222

IP src: 111.111.111.111
IP dest: 222.222.222.222

Network Layer: Data Plane

1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55

222.222.222.222
49-BD-D2-C7-56-2A

222.222.222.221
88-B2-2F-54-1A-0F

Addressing: routing to another LAN

IP src: 111.111.111.111
IP dest: 222.222.222.222

R forwards datagram with IP source A, destination B
R creates link-layer frame with B’s MAC address as destination address, frame contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A

Network Layer: Data Plane

1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55

222.222.222.222
49-BD-D2-C7-56-2A

222.222.222.221
88-B2-2F-54-1A-0F

Addressing: routing to another LAN
R forwards datagram with IP source A, destination B
R creates link-layer frame with B’s MAC address as destination address, frame contains A-to-B IP datagram

IP src: 111.111.111.111
IP dest: 222.222.222.222

MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A

Network Layer: Data Plane

1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B
CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55

222.222.222.222
49-BD-D2-C7-56-2A

222.222.222.221
88-B2-2F-54-1A-0F

Addressing: routing to another LAN
R forwards datagram with IP source A, destination B
R creates link-layer frame with B’s MAC address as dest, frame contains A-to-B IP datagram

IP src: 111.111.111.111
IP dest: 222.222.222.222

MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A

Network Layer: Data Plane

Reverse Address Resolution Protocol (RARP)
RARP can find a machine’s logical address by using its physical address
an RARP request messages is created and broadcast on the local network
broadcasting is done at data link layer
broadcast request does not pass the boundaries of a network
the machine on the local network that knows the logical address will respond with an RARP reply

Network Layer: Data Plane

RARP: request and reply

Network Layer: Data Plane

Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request

Link Layer

“dominant” wired LAN technology:
single chip, multiple speeds (e.g., Broadcom BCM5761)
first widely used LAN technology
simpler, cheap
kept up with speed race: 10 Mbps – 10 ’s Ethernet sketch

Link Layer

Ethernet: physical topology
bus: popular through mid 90s
all nodes in same collision domain (can collide with each other)
star: prevails today
active switch in center
each link runs a (separate) Ethernet protocol (nodes do not collide with each other)

bus: coaxial cable

Link Layer

Ethernet frame structure
sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame

7 bytes with pattern 10101010 followed by one byte with pattern 10101011
used to synchronize receiver, sender clock rates

Link Layer

Ethernet frame structure (more)
addresses: 6 byte source, destination MAC addresses
if adapter receives frame with matching destination address, or with broadcast address (e.g. ARP packet), it passes data in frame to network layer protocol
otherwise, adapter discards frame
type: indicates higher layer protocol (mostly IP but others possible, e.g., PX, AppleTalk)
CRC: cyclic redundancy check at receiver
error detected: frame is dropped

Link Layer

Ethernet: unreliable, connectionless
connectionless: no handshaking between sending and receiving NICs
unreliable: receiving NIC doesn’t send acks or nacks to sending NIC
data in dropped frames recovered only if initial sender uses higher layer rdt (e.g., TCP), otherwise dropped data lost
Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff

Link Layer

Ethernet CSMA/CD algorithm
1. NIC receives datagram from network layer, creates frame
2. If NIC senses channel idle, starts frame transmission. If NIC senses channel busy, waits until channel idle, then transmits.
3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
4. If NIC detects another transmission while transmitting, aborts
5. After aborting, NIC enters binary (exponential) backoff:
after mth collision, NIC chooses K at random from {0,1,2, …, 2m-1}. NIC waits K·512 bit times, returns to Step 2
longer backoff interval with more collisions

Link Layer

802.3 Ethernet standards: link & physical layers
many different Ethernet standards
common MAC protocol and frame format
different speeds: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10 Gbps, 40 Gbps
different physical layer media: fiber, cable

application

MAC protocol
and frame format
100BASE-TX
100BASE-T4
100BASE-FX

100BASE-T2
100BASE-SX
100BASE-BX

fiber physical layer

copper (twister
pair) physical layer

Link Layer

Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request

Link Layer

Ethernet switch
link-layer device: takes an active role
store, forward Ethernet frames
examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on those links, uses CSMA/CD to access links

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com