[SOLVED] 程序代写代做代考 scheme DHCP algorithm dns Chapter 1. Introduction to Data Communications

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 host’s
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 1’s remains even

– Odd parity: number of 1’s 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 doesn’t 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 1’s 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

1’s 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 EDV–could 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 A’s 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 B’s IP address – assume A knows IP address of first hop router, R – assume A knows R’s 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 Metcalfe’s 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 Google’s 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 client’s 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  demux’ed 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 life…TCP 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