Chapter 1. Introduction to Data Communications
Networks, Security, and Privacy
158.235
A/Prof. Julian Jang-Jaccard
Massey University
Data Link
Layer
Reading: Chapter 4 in the prescribed textbook
Introduction
Layer 2 in the Internet
model
Responsible for moving
messages (datagram) from
one device (node) to
another physically adjacent
node over a link
Major functions of a data
link layer protocol
Error Control
Flow Control
Link layer addressing
Application
Transport
Network
Data Link
Physical
Internet Model
terminology:
hosts and routers: nodes
communication channels
that connect adjacent
nodes along
communication path: links
wired links
wireless links
LANs
layer-2 packet: frame,
encapsulates datagram
global ISP
Introduction
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
eachlink protocol
provides different
services
e.g., may or may not
provide reliable data
transfer over link
transportation analogy:
trip from Palmerston North
to Disney Land, LA
Taxi: City center to PN
airport
Plane: PN to Auckland
Plane: Auckland to LAX
Bus: LAX to Disney Land
tourist = datagram
transport segment =
communication link
transportation mode =
link layer protocol
travel agent = routing
algorithm
Introduction
Link layer services
framing, link access:
encapsulate datagram into frame, adding
header, trailer
MAC addresses used in frame headers to
identify source, dest(different from IP address!)
flow control:
pacing between adjacent sending and receiving nodes
error detection:
errors caused by signal attenuation, noise.
receiver detects presence of errors:
error correction:
receiver identifies and corrects bit error(s) without
resorting to retransmission
Where is the link layer
implemented?
in each and every host
link layer implemented in
adaptor (aka network
interface card NIC) or on
a chip
Ethernet card, 802.11
card; Ethernet chipset
implements link,
physical layer
attaches into hosts
system buses
combination of hardware,
software, firmware
controller
physical
transmission
cpu memory
host
bus
(e.g., PCI)
network adapter
card
application
transport
network
link
link
physical
Data Link Layer
Error Control
Flow Control
Link Addressing
Error Control
Network errors
Types
Corrupted data
Lost data
Caused by problems in transmission (not
humans)
Networks should be designed with:
Error prevention
Error detection
Error correction
Sources of Network Errors
Line noise and distortion
Major reason for errors and caused by several
sources
More likely on electrical media and lower-end
cables (e.g. twisted pair)
Undesirable electrical signal
Degrades performance of a circuit
Manifestation
Extra bits
Flipped bits
Missing bits
Sources of Errors and Prevention
Source of Error What Causes It How to Prevent or Fix
White Noise Movement of electrons Increase signal strength
Impulse Noise Sudden increases in electricity (e.g.,
lightning)
Shield or move the wires
Cross-talk Multiplexer guardbands too small or
wires too close together
Increase the guardbands
or move or shield the wires
Echo
Poor (misaligned) connections
Fix the connections or tune
equipment
Attenuation Gradual decrease in signal over
distance
Use repeaters
Intermodulation noise Signals from several circuits
combine
Move or shield the wires
Error Detection
Receivers need to know when the data
transmitted is not correct
Add check value (error detection value)
to message
Check value produced by mathematical
formula
Message
Check
Value
Error Detection
Mathematical
calculations
?
=
Mathematical
calculations
Data to be
transmitted
Sender calculates an
Error Detection Value
(EDV) andtransmits
it along with data
Receiver recalculates
EDV and checks it
against the received EDV
If the same No
errors in transmission
If different Error(s)
in transmission
EDV
Error Detection Techniques
Parity checks
Checksum
Cyclic Redundancy Check (CRC)
Parity Checking
One of the oldest and simplest
A single bit added to each character
Even parity:number of 1s remains even
Odd parity: number of 1s remains odd
Receiving end recalculates parity bit
If one bit has been transmitted in error the received
parity bit will differ from the recalculated one
Simple, but doesnt catch all errors
If two (or an even number of) bits have been transmitted
in error at the same time, the parity check appears to be
correct
Detects about 50% of errors
Examples of Using Parity
sender receiver
01101010
EVEN parity
parity
Add a bit so that the
number of all
transmitted 1s is
EVEN
To be sent: Letter V in 7-bit ASCII: 0110101
sender receiver
01101011
ODD parity
parity
Add a bit so that the
number of all transmitted
1s is ODD
Checksum
A checksum (usually 1 byte) is added to the end
of the message
It is 95% effective
Method:
Add decimal values of each character in the message
Divide the sum by 255
The remainder is the checksum value
CRC
Cyclic redundancy check (CRC)
Treats message as a single binary number
Divides by a preset number
Uses remainder as the check value
Preset number is chosen so that
remainder is the correct number of bits
Modes:
CRC-16 (~99.998% error detection rate)
CRC-32 (>99.99999% error detection rate)
P / G = Q + R / G
Cyclic Redundancy Check (CRC)
Most powerful and most common
Detects 100% of errors (if number of errors <= size of R) Otherwise: CRC-16 (99.998%) and CRC-32 (99.9999%) Message (treated as one long binary number) A fixed number (divisor) which determines the length of the R Remainder: added to the message as EDVcould be 8 bits, 16 bits, 24 bits, or 32 bits long CRC16 has R of 16 bits Quotient (whole number) Example: P = 58 G = 8 Q = 7 R= 2 Error Correction Once detected, the error must be corrected Error correction techniques Retransmission (or, backward error correction) Simple and most common Automatic Repeat reQuest (ARQ) This can also provide flow control by limiting the number of messages sent Forward Error Correction Receiving device can correct incoming messages without retransmissionAutomatic Repeat reQuest (ARQ) Process of requesting a data transmission be resent Main ARQ protocols Stop and Wait ARQ(A half duplex technique) Sender sends a message and waits for acknowledgment, then sends the next message Receiver receives the message and sends an acknowledgement, then waits for the next message Continuous ARQ (A full duplex technique) Sender continues sending packets without waiting for the receiver to acknowledge Receiver continues receiving messages without acknowledging them right away Stop and Wait ARQ Sends Packet A, then waits to hear from receiver. Sendsacknowledgement Sends negative acknowledgement Resends the packetagain Sends the next packet (B) Sender Receiver Sendsacknowledgement Continuous ARQ Sender sends packets continuously without waiting for receiver to acknowledge Notice that acknowledgments nowidentify the packet being acknowledged.Receiver sends back a NAK for a specific packet to be resent. Data Link Layer Error Control Flow Control Link Addressing Flow Control with ARQ Ensuring that sender is not transmitting too quickly for the receiver Stop-and-wait ARQ Receiver sends an ACK or NAK when it is ready to receive more packets Continuous ARQ: Both sides agree on the size of the sliding window Number of messages that can be handled by the receiver without causing significant delays Flow Control Example receiver sender 0 1 2 3 ACK 0 4 ACK 4 5 6 7 8 ACK 7 set window size to 2 99 8 window size =40 1 2 3 4 5 6 7 8 9(slide window)0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9(slide window) (slide window) (timeout) Forward Error Correction Receiving device can correct incoming messages itself (without retransmission) Requires extra corrective information Sent along with the data Allows data to be checked and corrected by the receiver Amount of extra information:usually 50-100% of the data Used in the following situations: One way transmissions (retransmission not possible) Transmission times are very long (satellite) In this situation, relatively insignificant cost of FEC Hamming Code An FEC Example A scheme by adding parity bit intelligently such that one erroneous bit can be detected and corrected Bit position is split into parity bit position and data bit position: parity bit occupies position 1, 2, 4, 8, 16, 32, data bit occupies the remaining positions (3, 5, 6, 7, 9,) parity bit value calculation: position 1 check 1 bit, skip 1 bit, and so forth (1, 3, 5, ) position 2 check 2 bits, skip 2 bits (2, 3, 6, 7, 10, 11,) position 4 check 4 bits, skip 4 bits ( 4-7, 12-15, ) Hamming Code ExampleData: 11011010 Even Parity 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 0 1 0 1 0 1 0 1 0 Position Data P1: data at position 3, 5, 7, 9, 11 11111 (odd 1s) Parity bit: 1 P2: data at position 3, 6, 7, 10, 11 10101 (odd 1s) Parity bit: 1 P4: data at position 5, 6, 7, 12 1010 (even 1s) Parity bit: 0 P8: data at position 9, 10, 11, 12 1010 (even 1s) Parity bit: 0Data sent: 111010101010 P1 P2 P4 P8 Hamming Code ExampleData Received: 111010101110 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 0 1 0 1 0 1 1 1 0 Position Data Check P1: data at position 3, 5, 7, 9, 11 11111 (odd 1s) Parity bit: 1 – OK Check P2: data at position 3, 6, 7, 10, 11 10111 (even 1s) Parity bit: 0 Not OK Check P4: data at position 5, 6, 7, 12 1010 (even 1s) Parity bit: 0- OK Check P8: data at position 9, 10, 11, 12 1110 (odd 1s) Parity bit: 1- Not OK P1 P2 P4 P8 Parity bit at position 2 and 8 are incorrect.The erroneous bit is placed at bit position 2+8 = 10 Data Link Layer Error Control Flow Control Link Addressing Address Resolution Addresses exist at different layers Addresses may be translated (resolved) from one layer to anotherAddress Type Example Example Address Application layer Web address (URL) www.indiana.edu Network layer IP address 129.79.78.193 (4 bytes) Data link layer MAC address 1C-6F-65-F8-33-8A (6 bytes) Address Resolution Data Link Layer Address Resolution Identifying the MAC address of the next node (that packet must be forwarded) Uses Address Resolution Protocol (ARP)ARP name resolution Identifying the MAC address by IP address Operation Broadcast an ARP message to all nodes on a LAN asking which node has a certain IP address Host with that IP address then responds by sending back its MAC address Store this MAC address in its address table Send the message to the destination node ARP: same LAN A broadcasts ARP query packet, containing B’s IP address dest MAC address = FF-FF-FF-FF-FF-FF all nodes on LAN receive ARP query (broadcast) B receives ARP packet, replies to A with its (B’s) MAC address frame sent to As MAC address (unicast) Question: how to determine a MAC address knowing its IP address? 58-23-D7-FA-20-B0 71-65-F7-2B-08-53LAN 137.196.7.23 137.196.7.14 A B ARP query ARP reply Src IP address 137.196.7.23 137.196.7.14 Dest IP address 137.196.7.14 137.196.7.23 Src MAC address 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 Dest MAC address FF-FF-FF-FF-FF-FF 71-65-F7-2B-08-53 walkthrough: send datagram from A to B via R focus on addressing at IP (datagram) and MAC layer (frame) assume A knows Bs IP address assume A knows IP address of first hop router, R assume A knows Rs MAC address Addressing: routing to another LAN R 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 A 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.221 88-B2-2F-54-1A-0F B R 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 A 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.221 88-B2-2F-54-1A-0F B Addressing: routing to another LAN IP Eth Phy IP src: 111.111.111.111IP 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 dest, frame contains A-to-B IP datagram MAC src: 74-29-9C-E8-FF-55MAC dest: E6-E9-00-17-BB-4B R 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 A 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.221 88-B2-2F-54-1A-0F B Addressing: routing to another LAN IP Eth Phy frame sent from A to R IP Eth Phy frame received at R, datagram removed, passed up to IP MAC src: 74-29-9C-E8-FF-55MAC dest: E6-E9-00-17-BB-4B IP src: 111.111.111.111IP dest: 222.222.222.222 IP src: 111.111.111.111IP dest: 222.222.222.222 R 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 A 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.221 88-B2-2F-54-1A-0F B Addressing: routing to another LAN IP src: 111.111.111.111IP 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 dest, frame contains A-to-B IP datagram MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2AIP Eth Phy IP Eth Phy R 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 A 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.221 88-B2-2F-54-1A-0F B 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.111IP dest: 222.222.222.222 MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2AIP Eth Phy IP Eth Phy R 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 A 222.222.222.222 49-BD-D2-C7-56-2A 222.222.222.221 88-B2-2F-54-1A-0F B 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.111IP dest: 222.222.222.222 MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2AIP Eth Phy Ethernet dominant wired LAN technology: cheap $20 for NIC first widely used LAN technology simpler, cheaper than token LANs and ATM kept up with speed race: 10 Mbps 10 Gbps Metcalfes Ethernet sketch Ethernet frame structure sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet framepreamble: 7 bytes with pattern 10101010 followed by one byte with pattern 10101011 used to synchronize receiver, sender clock rates dest. address source address data (payload) CRC preamble type Ethernet frame structure 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., Novell IPX, AppleTalk) CRC: cyclic redundancy check at receiver error detected: frame is dropped dest. address source address data (payload) CRC preamble type 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, 10G bps different physical layer media: fiber, cableapplication transport network link physical 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 Transmission EfficiencyTransmission efficiency =# of information bits .# of information + overhead bits A day in the life: scenario Comcast network68.80.0.0/13 Googles network64.233.160.0/1964.233.169.105 web server DNS serverschool network68.80.2.0/24 web page browser router (runs DHCP) A day in the life connecting to the Internet connecting laptop needs to get its own IP address, addr of first-hop router, addr of DNS server: use DHCP DHCP UDP IP Eth Phy DHCP DHCP DHCP DHCP DHCP DHCP UDP IP Eth Phy DHCP DHCP DHCP DHCP DHCP DHCP request encapsulated in UDP, encapsulated in IP, encapsulated in 802.3 Ethernet Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, received at router running DHCP server Ethernet demuxed to IP demuxed, UDP demuxed to DHCProuter (runs DHCP) DHCP server formulates DHCP ACK containing clients IP address, IP address of first-hop router for client, name & IP address of DNS serverDHCP UDP IP Eth Phy DHCP DHCP DHCP DHCP DHCP UDP IP Eth Phy DHCP DHCP DHCP DHCP DHCP encapsulation at DHCP server, frame forwarded (switch learning) through LAN, demultiplexing at clientClient now has IP address, knows name & addr of DNSserver, IP address of its first-hop router DHCP client receives DHCP ACK reply A day in the life connecting to the Internet router (runs DHCP) A day in the life ARP (before DNS, before HTTP) before sending HTTP request, need IP address of www.google.com:DNS DNS UDP IP Eth Phy DNS DNS DNS DNS query created, encapsulated in UDP, encapsulated in IP, encapsulated in Eth.To send frame to router, need MAC address of router interface: ARP ARP query broadcast, received by router, which replies with ARP reply giving MAC address of router interface client now knows MAC address of first hop router, so can now send frame containing DNS queryARP query Eth Phy ARP ARP ARP reply router (runs DHCP) DNS UDP IP Eth Phy DNS DNS DNS DNS DNS IP datagram containing DNS query forwarded via LAN switch from client to 1st hop router IP datagram forwarded from campus network into comcast network, routed (tables created by RIP, OSPF, IS-IS and/or BGP routing protocols) to DNS server demuxed to DNS server DNS server replies to client with IP address of www.google.comComcast network68.80.0.0/13 DNS serverDNS UDP IP Eth Phy DNS DNS DNS DNS A day in the life using DNS router (runs DHCP) A day in the lifeTCP connection carrying HTTP HTTP TCP IP Eth Phy HTTP to send HTTP request, client initiate TCP handshake protocol TCP SYN segment (step 1 in 3-way handshake) inter-domain routed to web server TCP connection established! 64.233.169.105 web server SYN SYN SYN SYNTCP IP Eth Phy SYN SYN SYN SYNACK SYNACK SYNACK SYNACK SYNACK SYNACK SYNACK web server responds with TCP SYNACK (step 2 in 3-way handshake) router (runs DHCP) A day in the life HTTP request/replyHTTP TCP IP Eth Phy HTTP HTTP request sent into TCP socket IP datagram containing HTTP request routed to www.google.com IP datagram containing HTTP reply routed back to client 64.233.169.105 web server HTTP TCP IP Eth Phy web server responds with HTTP reply (containing web page) HTTP HTTP HTTP HTTP HTTP HTTP HTTP HTTP HTTP HTTP HTTP HTTP HTTP web page finally (!!!) displayed END
Reviews
There are no reviews yet.