Transcript Networking.
Introduction to Systems Programming
Lecture 10
Networks
Avishai Wool
lecture 10 - 1
Protocols & Layering
Avishai Wool
lecture 10 - 2
First Principles
• Goal: transfer information, as a string of bits,
across space
• Requires interpretation conventions
• Such a convention is called a protocol.
Avishai Wool
lecture 10 - 3
The Layering Approach
A telephone call:
idea
wording
sound
signals
wire
idea
wording
sound
signals
• Each layer obeys strict interface rules
• Each layer “talks” to its counterpart only
Avishai Wool
lecture 10 - 4
The ISO/OSI Model
•
International Standards Organization: ISO
–
•
Open Standards Interconnect: OSI
–
•
•
(A bunch of people).
(A bunch of documents).
A convention of organizing network protocols
into layers
Gives terminology and central roles to various
layers
Avishai Wool
lecture 10 - 5
ISO/OSI Layers
MACHINE #1
DATA Application
|DATA Presentation
||DATA
Session
|||DATA
||||DATA
|||||DATA
||||||DATA
Transport
Network
Data Link
Physical
MACHINE #2
Application
Presentation
DATA
|DATA
Session
Transport
Network
Data Link
||DATA
|||DATA
||||DATA
|||||DATA
Physical
||||||DATA
Avishai Wool
lecture 10 - 6
Layer 1: Physical
• Unit of exchange: Bits
•
•
•
•
•
•
Convert bits to signals, and signals to bits.
Physical interfaces
Power
Frequency, amplitude, phase
Coding
Modulation and demodulation
Avishai Wool
lecture 10 - 7
Layer 2: Data Link
•
•
Also called: MAC: Medium Access Control
Unit of exchange: Frame
–
–
–
Usually over common (broadcast) media
Handles multiple access to shared PHY layer
Controls a Local-Area Network (LAN)
–
–
–
Bit ordering
Error-correction codes (ECC)
May be unreliable due to noise
Avishai Wool
lecture 10 - 8
Layer 3: Network
• Unit of exchange: Packet / Datagram
• Controlling the operation of multiple networks
• Addressing
• Routing: how to get a packet to its destination
• Unreliable
– Packets can arrive out of order or be dropped
Avishai Wool
lecture 10 - 9
Layer 4: Transport
• Transport: create a reliable message channel from
an unreliable packet channel.
•
•
•
•
•
Acknowledgements (ACKs) and retransmissions
Sequencing and re-ordering
Congestion
Source and Destination port numbers
Handshake
Avishai Wool
lecture 10 - 10
Layers 5-7
• Higher level protocols
• Less defined roles
• Not clear where “Application” ends and
“Presentation” begins
• Session examples: SQL (database), NFS (files)
• Presentation examples: MPEG, MIDI
Avishai Wool
lecture 10 - 11
TCP/IP Layers
Each sending layer adds a “wrapper” to message,
corresponding receiving layer “peels” it
5-7. application
4. transport
3. network
2. data-link
1. physical
message
ethernet
header
TCP header message
IP header TCP header message
IP header TCP header message
Avishai Wool
lecture 10 - 12
Local Area Networks
Layer 2
Avishai Wool
lecture 10 - 13
LAN Basics
• Bus/ring: twisted pair, coax, fiber, wireless
(radio)
• Broadcast medium (Multiple Access):
– Everyone hears everyone else
– No routing, no switching, no buffering, no servers
– One sender at a time
• Requires conflict resolution protocol
Avishai Wool
lecture 10 - 14
Ethernet
Avishai Wool
lecture 10 - 15
Ethernet: IEEE 802.3
•
•
•
•
Metcalfe & Boggs (1973) Xerox Digital 3Com
Speed: 10 Mbps / 100Mbps / 1000Mbps
Cabling: coax, twisted-pair
Secret of success: ingenious conflict resolution protocol
“thin ethernet” – coax – BNC
Ethernet – twisted-pair – RJ45
Avishai Wool
lecture 10 - 16
Ethernet
Computer
(a)
Classic Ethernet
(b)
Switched Ethernet
802.3 Protocol Basics
• Addresses: unique 48 bits, up to 1024 on a net
(MAC Address)
• Each vendor has a unique prefix and his own
numbering system
• Devices have MAC address “burned” into them
(not really…)
• Frame size 64-1518 bytes, containing:
– destination (maybe everybody!), source, data,
checksum
Avishai Wool
lecture 10 - 18
Basic Idea
• Bus architecture:
• TX of each connected to RX of all others
(broadcast)
• Problem: simultaneous transmissions (collisions)
overwrite and destroy each other
Avishai Wool
lecture 10 - 19
Ethernet sensing
• When a station wants to transmit:
1. Listen (sense) the wire.
•
If busy: wait
2. Start transmitting – and listen to own
transmission on wire.
3. If (my sensed bits != my transmitted bits)
another station must be transmitting too
collision – start conflict resolution.
Avishai Wool
lecture 10 - 20
Ethernet Conflict Resolution
Suppose 2 or more stations
• collide (transmit at same time) and
• sense (know) they collided.
What to do to avoid livelock?
• Goal: One station should get priority and transmit.
• Solution: CSMA/CD
– Carrier Sense
– Multiple Access
– Collision Detection
Avishai Wool
lecture 10 - 21
Backoff
First idea: use randomization!
• Each colliding station i picks its own random
delay di
• Waits di time units, and try again
• How to pick the range of random values?
• Too small stations will get same value and
collide again
• Too large slows down the communication
Avishai Wool
lecture 10 - 22
Exponential backoff
• If they know how many stations are colliding (n),
each could pick di randomly from, e.g., [1,...2n].
– If range is [1,...2n] then it is very likely that the
minimal di is chosen by only one station
• Second idea: guess number of colliding stations!
• Start with guess n=2; if unsuccessful, double n.
• This is exponential:
– range of random numbers is 2, 4, 8, 16, 32, …
Avishai Wool
lecture 10 - 23
802.3 CSMA/CD Algorithm
new attempt
ready to send
sense
channel
wait MAX_DELAY *
random[0, 2attempts]
busy
free
Carrier Sense
Collision Detection
Exponential Backoff
transmit
and sense
collision
detected
no collision
done
Avishai Wool
lecture 10 - 24
Main properties
• If diameter = 1 km, max_delay < 5S.
• Collisions possible in first 2 •max_delay time
• Minimum packet lengths – ensure that collision
will be sensed
• Extremely flexible!
• Throughput degrades under heavy load
– optimal: 1/e 37%
• Non-deterministic service: real time connections?
• No fixed priorities
Avishai Wool
lecture 10 - 25
Wireless LAN (WiFi)
Avishai Wool
lecture 10 - 26
Wireless LAN: IEEE 802.11
• Uses wireless communication
• Base station / PCMCIA cards for laptops
• Operates in unregulated 2.4GHz range
• Has to deal with interference from microwave
ovens, new cordless phones, etc.
• 802.11b: up to 11Mbps. 802.11g: 54Mbs
• Range of 10-100 meters
• Frequency-hopping (Spread-Spectrum)
Avishai Wool
lecture 10 - 27
Vendor solutions
Avishai Wool
lecture 10 - 28
Hobbyists build antennas from:
Avishai Wool
lecture 10 - 29
And:
Avishai Wool
lecture 10 - 30
Properties of IEEE 802.11
• Home-brew antennas have excellent range: over
350m.
• http://www.turnpoint.net/wireless/has.html
• Uses encryption: Wire-Equivalent Privacy (WEP)
• But: Major security problems
–
–
–
–
Encryption broken
Authentication broken
Data integrity broken
By default WEP is turned OFF…
Avishai Wool
lecture 10 - 31
Connecting networks to each other
Avishai Wool
lecture 10 - 32
Repeaters
Goal: enhance physical layer
network
data-link
physical
network
a2d-d2a
physical
physical
data-link
physical
Avishai Wool
lecture 10 - 33
Bridges/Switches/Hubs
• Goal: connect at the data-link layer
• Can connect different physical layers (WiFi +
Ethernet)
• Multiple ports
• Filter packets: listen and learn location of sources
network
data-link
physical
filter
data-link
physical
data-link
physical
network
data-link
physical
Avishai Wool
lecture 10 - 34
Internet Protocol (IP)
Layer 3
Avishai Wool
lecture 10 - 35
Properties of IP
• Point-to-point, datagram service
• Connect multiple LANs to each other
• Addressing: 32-bit IP-addresses.
– Must be unique in entire network (whole Internet!)
• Get the packets to their destination (routing).
• Connectionless
– each packet carries its source & destination IP addresses
– each packet routed independently through network
• Unreliable
– packets can arrive out of order or be dropped entirely
Avishai Wool
lecture 10 - 36
IP addresses
• 32-bit IP address usually written in “dotteddecimal” notation, each number in 0-255
– 132.66.32.10
• IP addresses are a valuable resource. Allocated by
IANA (Internet Assigned Number Authority)
– http://www.iana.org/
• Allocated hierarchically through delegation
– ARIN : North America
– RIPE : Europe, Middle east
Avishai Wool
lecture 10 - 37
Routers: IP traffic junctions
• Goal: forward IP packets towards destination
• Means: “sit” on more than one network (a few ports);
maintain a routing table; forward according to table
network B
network A
router
destination next hop
192.168.2.4 A
10.0.4.3
A
18.4.*
B
default
C
network C
Avishai Wool
lecture 10 - 38
Routers – more detail
• Routers connect two or more LANs:
Multiple network interface cards (NIC)
Each NIC has its own MAC address
Each NIC has its own IP address!
IP address mapped to NIC, not to computer
Avishai Wool
lecture 10 - 39
Routing to directly connected hosts
• Router decides what to do with packet based on
its destination IP address
• Directly connected == destination on same LAN
as one of the router’s NICs
– Find out the destination MAC address
– Encapsulate packet in Ethernet frame,
– Send to destination via layer 2
IP does NOT modify the destination IP address!
Avishai Wool
lecture 10 - 40
Routing to remote addresses
• If destination IP address not directly connected:
• Router checks routing table
• Finds IP address of next-hop router
– Next-hop router has to be directly connected!
• Finds MAC address of next hop router
• Encapsulate packet & send as before
Avishai Wool
lecture 10 - 41
How to find a MAC address ?
• “ARP”: Address Resolution Protocol
• Layer “2.5”: above Ethernet but below IP
– Broadcast to Ethernet “who is IP a.b.c.d?”
– Owner of that IP responds (or timeout)
– Each station keeps a table of recent mappings
• Windows/Unix: type “arp –a” to see table
Avishai Wool
lecture 10 - 42
Every computer is a “router”
• Every machine running IP is a “router”
– Only one NIC
– Only one IP address
– Usually only one next-hop router (default gateway)
for non-local traffic
• To see contents of routing table:
– Windows (command prompt): “route print”
– Unix: netstat –rn
Avishai Wool
lecture 10 - 43
Concepts for review
•
•
•
•
•
•
•
•
•
•
ISO 7-layer model
Physical layer
DataLink layer
Network layer
Transport layer
Ethernet
MAC Address
Exponential backoff
Wireless LAN (802.11)
Bridge / Hub / Switch
•
•
•
•
•
Internet Protocol (IP)
IP Address
Router
Routing table
Next-hop router
Avishai Wool
lecture 10 - 44