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 < 5S.
• 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