Transcript Physical Layer - Duke Computer Science

Lecture 3: Hardware and physical
links
Chap 1.4, 2 of [PD]
Based partly on lecture notes by Xiaowei Yang, Rodrigo Fonseca, David Mazières, Phil Levis, John Jannotti
Overview
• Sockets Programming Revisited
• Network Architectures
• Examples of Networking Principles
• Hardware and physical layer
– Nuts and bolts of networking
– Nodes
– Links
• Bandwidth, latency, throughput, delay-bandwidth product
• Physical links
IPs V. Ports : Server V. App.
Plus: 43
Gmail: 23
Server has ..
12.32.43.23
Google
Bing: 43
Xbox: 23
Server has ..
34.232.23.99
microsoft
The
Internet
Client has ..
12.32.43.23
Socket
• What is a socket?
– The point where a local application process attaches to the
network
– An interface between an application and the network
– An application creates the socket
• The interface defines operations for
–
–
–
–
Creating a socket
Attaching a socket to the network
Sending and receiving messages through the socket
Closing the socket
Creating a Socket
int sockfd = socket(address_family, type, protocol);
• The socket number returned is the socket
descriptor for the newly created socket
• int sockfd = socket (PF_INET, SOCK_STREAM, 0);
• int sockfd = socket (PF_INET, SOCK_DGRAM, 0);
The combination of PF_INET and
SOCK_STREAM implies TCP
Socket
• Socket Family
– PF_INET denotes the Internet family
– PF_UNIX denotes the Unix pipe facility
– PF_PACKET denotes direct access to the network
interface (i.e., it bypasses the TCP/IP protocol stack)
• Socket Type
– SOCK_STREAM is used to denote a byte stream
– SOCK_DGRAM is an alternative that denotes a
message oriented service, such as that provided by
UDP
Client-Server Model with TCP
Server
– Passive open
– Prepares to accept connection, does not
actually establish a connection
Server invokes
int bind (int socket, struct sockaddr *address,
int addr_len)
int listen (int socket, int backlog)
int accept (int socket, struct sockaddr *address,
int *addr_len)
Client-Server Model with TCP
Bind
– Binds the newly created socket to the
specified address i.e. the network address of
the local participant (the server)
– Address is a data structure which combines IP
and port
Listen
– Defines how many connections can be
pending on the specified socket
Client-Server Model with TCP
Accept
– Carries out the passive open
– Blocking operation
• Does not return until a remote participant
has established a connection
• When it does, it returns a new socket that
corresponds to the new established
connection and the address argument
contains the remote participant’s address
Client-Server Model with TCP
Client
– Application performs active open
– It says who it wants to communicate with
Client invokes
int connect (int socket, struct sockaddr *address,
int addr_len)
Connect
– Does not return until TCP has successfully
established a connection at which application is
free to begin sending data
– Address contains remote machine’s address
Client-Server Model with TCP
Once a connection is established, the
application process invokes two operation
int send (int socket, char *msg, int msg_len,
int flags)
int recv (int socket, char *buff, int buff_len,
int flags)
Overview
• Sockets Programming Revisited
• Network Architectures
• Examples of Networking Principles
• Hardware and physical layer
– Nuts and bolts of networking
– Nodes
– Links
• Bandwidth, latency, throughput, delay-bandwidth product
• Physical links
Network architectures
• Layering is an abstraction that captures important
aspects of the system, provides service interfaces,
and hides implementation details
Protocols
Layer N+1
Layer N+1
Layer N
Layer N
Layer N-1
Layer N-1
• The abstract objects that make up the layers of a network
system are called protocols
• Each protocol defines two different interfaces
– Service interface
– Peer interface
Network architectures
• A protocol graph represents protocols that make up a
system
– Nodes are protocols
– Links are depend-on relations
• Set of rules governing the form and content of a
protocol graph are called a network architecture
• Standard bodies such as IETF govern procedures for
introducing, validating, and approving protocols
The protocol graph of Internet
Applicatoin layer
Transport layer
Network layer
Link layer
• No strict layering. One can do cross-layer design
• Hourglass shaped: IP defines a common method for exchanging packets
among different networks
• To propose a new protocol, one must produce both a spec and one/two
implementations
Encapsulation
• Upper layer sends a message using the service
interface
• A header, a small data structure, to add information
for peer-to-peer communication, is attached to the
front message
– Sometimes a trailer is added to the end
• Message is called payload or data
• This process is called encapsulation
Multiplexing & Demultiplexing
• Same ideas apply up and down the protocol graph
Overview
• Sockets Programming Revisited
• Network Architectures
• Examples of Networking Principles
• Hardware and physical layer
– Nuts and bolts of networking
– Nodes
– Links
• Bandwidth, latency, throughput, delay-bandwidth product
• Physical links
An Example
A simple TCP/IP Example
argon.tcpip-lab.edu
("Argon")
neon.tcpip-lab.edu
("Neon")
Web request
Web page
Web client
Web server
• A user on host argon.tcpip-lab.edu (“Argon”) makes
web access to URL
http://neon. tcpip-lab.edu/index.html.
• What actually happens in the network?
HTTP Request and HTTP response
Argon
HTTP client
Neon
HTTP request
HTTP server
HTTP response
• Web server runs an HTTP server program
• HTTP client Web browser runs an HTTP client
program
• sends an HTTP request to HTTP server
• HTTP server responds with HTTP response
HTTP Request
GET /example.html HTTP/1.1
Accept: image/gif, */*
Accept-Language: en-us
Accept-Encoding: gzip, deflate
User-Agent: Mozilla/4.0
Host: 192.168.123.144
Connection: Keep-Alive
HTTP Response
HTTP/1.1 200 OK
Date: Sat, 25 May 2002 21:10:32 GMT
Server: Apache/1.3.19 (Unix)
Last-Modified: Sat, 25 May 2002 20:51:33 GMT
ETag: "56497-51-3ceff955"
Accept-Ranges: bytes
Content-Length: 81
Keep-Alive: timeout=15, max=100
Connection: Keep-Alive
Content-Type: text/html
<HTML>
<BODY>
<H1>Internet Lab</H1>
Click <a href="http://www.tcpip-lab.net/index.html">here</a> for the Internet Lab
webpage.
</BODY>
</HTML>
• How does the HTTP request get from Argon to Neon?
From HTTP to TCP
Argon
Neon
HTTP client
HTTP request / HTTP response
HTTP server
TCP client
TCP connection
TCP server
• To send request, HTTP client program
establishes an TCP connection to the HTTP
server Neon.
• The HTTP server at Neon has a TCP server
running
Resolving hostnames and port
numbers
• Since TCP does not work with hostnames and
also would not know how to find the HTTP
server program at Neon, two things must happen:
1. The name “neon.tcpip-lab.edu” must be
translated into a 32-bit IP address.
2. The HTTP server at Neon must be identified
by a 16-bit port number.
Translating a hostname into an IP
address
neon.tcpip-lab.edu
HTTP client
128.143.71.21
argon.tcpip-lab.edu
DNS Server
128.143.136.15
• The translation of the hostname neon.tcpip-lab.edu into an IP
address is done via a database lookup
– gethostbyname(host)
• The distributed database used is called the Domain Name
System (DNS)
• All machines on the Internet have an IP address:
argon.tcpip-lab.edu
128.143.137.144
neon.tcpip-lab.edu
128.143.71.21
Finding the port number
• Note: Most services on the Internet are reachable via well-known
ports. E.g. All HTTP servers on the Internet can be reached at
port number “80”.
• So: Argon simply knows the port number of the HTTP server at a
remote machine.
• On most Unix systems, the well-known ports are listed in a file
with name /etc/services. The well-known port numbers of some of
the most popular services are:
ftp
21
finger 79
telnet
23
http
80
smtp
25
nntp 119
Requesting a TCP Connection
argon.tcpip-lab.edu
connect(s, (struct sockaddr*)&sin, sizeof(sin))
HTTP client
Establish a TCP connection
to port 80 of 128.143.71.21
TCP client
• The HTTP client at argon.tcpip-lab.edu requests the TCP client to establish
a connection to port 80 of the machine with address 128.141.71.21
Invoking the IP Protocol
argon.tcpip-lab.edu
TCP client
Send an IP datagram to
128.143.71.21
IP
ip_output()
• The TCP client at Argon sends a request to establish a connection to port 80 at
Neon
• This is done by asking its local IP module to send an IP datagram to
128.143.71.21
• (The data portion of the IP datagram contains the request to open a
connection)
Sending the IP datagram to the
default router
• Argon sends the IP datagram to its default router
• The default gateway is an IP router
• The default gateway for Argon is
Router137.tcpip-lab.edu (128.143.137.1).
Invoking the device driver
argon.tcpip-lab.edu
IP module
Send an Ethernet frame
to 00:e0:f9:23:a8:20
Ethernet
ether_output
• The IP module at Argon, tells its Ethernet device driver to send an
Ethernet frame to address 00:e0:f9:23:a8:20
• Ethernet address of the default router is found out via ARP
The route from Argon to Neon
• Note that the router has a different name for each of its interfaces.
Sending an Ethernet frame
• The Ethernet device driver of Argon sends the
Ethernet frame to the Ethernet network interface
card (NIC)
• The NIC sends the frame onto the wire
Forwarding the IP datagram
•
The IP router receives the Ethernet frame at interface 128.143.137.1
1. recovers the IP datagram
2. determines that the IP datagram should be forwarded to the interface
with name 128.143.71.1
•
The IP router determines that it can deliver the IP datagram directly
Invoking the Device Driver at the
Router
router71.tcpip-lab.edu
IP module
Send a frame to
00:20:af:03:98:28
Ethernet
• The IP protocol at Router71, tells its Ethernet device
driver to send an Ethernet frame to address
00:20:af:03:98:28
Sending another Ethernet frame
• The Ethernet device driver of Router71 sends
the Ethernet frame to the Ethernet NIC, which
transmits the frame onto the wire.
Data has arrived at Neon
• Neon receives the Ethernet frame
• The payload of the Ethernet frame is an
IP datagram which is passed to the IP
protocol.
• The payload of the IP datagram is a TCP
segment, which is passed to the TCP
server
neon.tcpip-lab.edu
HTTP server
TCP server
IP module
Ethernet
Overview
• Sockets Programming Revisited
• Network Architectures
• Examples of Networking Principles
• Hardware and physical layer
– Nuts and bolts of networking
– Nodes
– Links
• Bandwidth, latency, throughput, delay-bandwidth product
• Physical links
Layers, Services, Protocols
Application
Transport
Network
Link
Physical
Service: move bits to other node across link
Physical Layer (Layer 1)
• Responsible for specifying the physical
medium
– Type of cable, fiber, wireless frequency
• Responsible for specifying the signal
(modulation)
– Transmitter varies something (amplitude,
frequency, phase)
– Receiver samples, recovers signal
• Responsible for specifying the bits (encoding)
– Bits above physical layer -> chips
Modulation
• Specifies mapping between digital signal
and some variation in analog signal
• Why not just a square wave (1v=1; 0v=0)?
– Not square when bandwidth limited
• Bandwidth – frequencies that a channel
propagates well
– Signals consist of many frequency
components
– Attenuation and delay frequency-dependent
Components of a Square Wave
Graphs from Dr. David Alciatore, Colorado State Univers
Approximation of a Square
Wave
Graphs from Dr. David Alciatore, Colorado State Univers
Idea: Use Carriers
• Only use frequencies that transmit well
• Modulate the signal to encode bits
Specifying
M
Specifying
theSignal:
Signal:
Modulation
odulationShift
OOK:
On-Off the
ASK:
Amplitude
Keying
Keying
11
00
11
On-Off
On-Off Keying
Keying
(OOK)
(OOK)
11
00
11
Amplitude
Amplitude Shift
Shift
Keying
Keying (ASK)
(ASK)
Idea: Use Carriers
• Only use frequencies that transmit well
• Modulate the signal to encode bits
FSK: Frequency
Shift
M
Continued
Modulation,
odulation,
Continued
PSK
: Phase Shift Keying
Keying
11
00
11
Frequency
Frequency Shift
Shift
11
00
Phase
Phase Shift
Shift
11
How Fast Can You Send?
• Encode information in some varying
characteristic of the signal.
• If B is the maximum frequency of the signal
C = 2B bits/s
(Nyquist, 1928)
Can we do better?
• So we can only change 2B/second, what if we
encode more bits per sample?
– Baud is the frequency of changes to the physical channel
– Not the same thing as bits!
• Suppose channel passes 1KHz to 2KHz
–
–
–
–
1 bit per sample: alternate between 1KHz and 2KHz
2 bits per sample: send one of 1, 1.33, 1.66, or 2KHz
Or send at different amplitudes: A/4, A/2, 3A/4, A
n bits: choose among 2n frequencies!
• What is the capacity if you can distinguish M
levels?
Hartley’s Law
C = 2B log2(M) bits/s
Great. By increasing M, we can have as
large a capacity as we want!
Or can we?
The channel is noisy!
The channel is noisy!
• Noise prevents you from increasing M
arbitrarily!
• This depends on the signal/noise ratio (S/N)
• Shannon: C = B log2(1 + S/N)
– C is the channel capacity in bits/second
– B is the bandwidth of the channel in Hz
– S and N are average signal and noise power
– Signal-to-noise ratio is measured in dB =
10log10(S/N)
Putting it all together
• Noise limits M!
2B log2(M) ≤ B log2(1 + S/N)
M ≤ √1+S/N
• Example: Telephone Line
– 3KHz b/w, 30dB S/N = 10ˆ(30/10) = 1000
– C = 3KHz log2(1001) ≈ 30Kbps
Encoding
• Now assume that we can somehow
modulate a signal: receiver can decode our
binary stream
• How do we encode binary data onto
signals?
• One approach: 1 as high, 0 as low!
– Called Non-return to Zero (NRZ)
0
NRZ
(non-return to zero)
Clock
0
1
0
1
0
1
1
0
Drawbacks of NRZ
• No signal could be interpreted as 0 (or viceversa)
• Consecutive 1s or 0s are problematic
• Baseline wander problem
– How do you set the threshold?
– Could compare to average, but average may drift
• Clock recovery problem
– For long runs of no change, could miscount
periods
Alternative Encodings
• Non-return to Zero Inverted (NRZI)
– Encode 1 with transition from current signal
– Encode 0 by staying at the same level
– At least solve problem of consecutive 1s
NRZI
(non-return to zero
intverted)
Clock
0
0
1
0
1
0
1
1
0
Manchester
• Map 0  chips 01
• Maps 1  chips 10
– Transmission rate now 1 bit per two clock cycles
• Solves clock recovery, baseline wander
• But cuts transmission rate in half
0
Manchester
Clock
0
1
0
1
0
1
1
0
4B/5B
• Can we have a more efficient encoding?
• Every 4 bits encoded as 5 chips
• Need 16 5-bit codes:
– selected to have no more than one leading 0 and
no more than two trailing 0s
– Never get more than 3 consecutive 0s
• Transmit chips using NRZI
• Other codes used for other purposes
– E.g., 11111: line idle; 00100: halt
• Achieves 80% efficiency
4B/5B Table
Encoding Goals
•
•
•
•
DC Balancing (same number of 0 and 1 chips)
Clock synchronization
Can recover some chip errors
Constrain analog signal patterns to make signal
more robust
• Want near channel capacity with negligible errors
– Shannon says it’s possible, doesn’t tell us how
– Codes can get computationally expensive
• In practice
– More complex encoding: fewer bps, more robust
– Less complex encoding: more bps, less robust
Last Example: 802.15.4
• Standard for low-power, low-rate wireless
PANs
– Must tolerate high chip error rates
• Uses a 4B/32B bit-to-chip encoding
Questions so far?
Photo: Lewis Hine
Layers, Services, Protocols
Application
Transport
Network
Link
Physical
Service: user-facing application.
Application-defined messages
Service: multiplexing applications
Reliable byte stream to other node (TCP),
Unreliable datagram (UDP)
Service: move packets to any other node in th
IP: Unreliable, best-effort service model
Service: move frames to other node across lin
May add reliability, medium access control
Service: move bits to other node across link
Framing
• Given a stream of bits, how can we
represent boundaries?
• Break sequence of bits into a frame
• Typically done by network adaptor
Representing Boundaries
Approaches
• Sentinels
• Length counts
• Clock-based
Characteristics
• Bit- or byte oriented
• Fixed or variable length
• Data-dependent or independent
Sentinel-based Framing
• Byte-oriented protocols (e.g. BISYNC, PPP)
– Place special bytes (SOH, ETX,…) in the beginning,
end of messages
• What if ETX appears in the body?
– Escape ETX byte by prefixing DEL byte
– Escape DEL byte by prefixing DEL byte
– Technique known as character stuffing
Bit-Oriented Protocols
• View message as a stream of bits, not
bytes
• Can use sentinel approach as well (e.g.,
HDLC)
– HDLC begin/end sequence 01111110
• Use bit stuffing to escape 01111110
– Always append 0 after five consecutive 1s in
data
Representing Boundaries
Approaches
• Sentinels
• Length counts
• Clock-based
Characteristics
• Bit- or byte oriented
• Fixed or variable length
• Data-dependent or independent
Length-based Framing
• Drawback of sentinel techniques
– Length of frame depends on data
• Alternative: put length in header (e.g., DDCMP)
• Danger: Framing Errors
– What if high bit of counter gets corrupted?
– Adds 8K to length of frame, may lose many frames
– CRC checksum helps detect error
Representing Boundaries
Approaches
• Sentinels
• Length counts
• Clock-based
Characteristics
• Bit- or byte oriented
• Fixed or variable length
• Data-dependent or independent
Clock-based Framing
• E.g., SONET (Synchronous Optical
Network)
– Each frame is 125μs long
– Look for header every 125μs
– Encode with NRZ, but first XOR payload
with 127-bit string to ensure lots of transitions
Representing Boundaries
Approaches
• Sentinels
• Length counts
• Clock-based
Characteristics
• Bit- or byte oriented
• Fixed or variable length
• Data-dependent or independent
Error Detection
• Basic idea: use a checksum
– Compute small checksum value, like a hash of
packet
• Good checksum algorithms
– Want several properties, e.g., detect any single-bit
error
– Details in a later lecture
Summary
• Network architectures
• Application Programming Interface
• Hardware and physical layer
– Nuts and bolts of networking
– Nodes
– Links
• Bandwidth, latency, throughput, delay-bandwidth product
• Physical links