Transcript Document

Communication Networks
A Second Course
Jean Walrand
Department of EECS
University of California at Berkeley
Review of TCP/IP
•
•
•
•
•
Networks
History
Key Ideas
Protocols
Technology
Networks
WAN
MAN
Networks
WAN
MAN
LAN
Networks
WAN
LAN
History
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
1962 – L. Kleinrock proposes Packet Switching
1966 – L. Roberts proposes architecture to Darpa
1969 – First demonstration of packet switching: 4-node Arpanet
1969 – S. Croker introduces RFCs (managed by J. Postel)
1972 – R. Kahn proposes an open architecture: Inter-networking
with stateless routers, best effort, no control plane
1973 – Kahn and V. Cerf propose early ideas of IP (32-bit address)
and TCP (end-to-end ACKs with a window scheme)
1973 – R. Metcalfe invents Ethernet
1982 – IGP and EGP
Late 1970s, early 1980s – Berkeley develops BSD, a modified
implementation of UNIX that includes TCP/IP
1983 – Arpanet switches to TCP/IP
1983 – P. Mockapetris invents DNS
1988 – Van Jacobson fixes TCP
1985 – 1995 – Internet supported by NSF and other agencies
1993? – T. Berners-Lee invents WWW
1995 – Internet is privatized
2000… - WiFi,VoIP, P2P
See http://www.isoc.org/internet/history/brief.shtml
Key Ideas
•
•
•
•
•
•
•
Packet Switching
End-to-End error and flow control
Internetworking
Multiple Access
DNS
P2P
VoIP
Packet Switching
A | B | ….
A | C | ….
A | B | ….
A | B | ….
B
A
A | C | ….
A | C | ….
C
End-to-End Error and Flow Control
Error control field
A | B | n | … | EC
A
A | B | m | … | EC
B
B | A| k | m | … | EC
ACKs all packets from A
up to packet m
A can have up to N packets for B that have not been acknowledged
Selecting N adjusts the rate of transmissions: limit congestion
If ACK is late, A retransmits packets
Internetworking
• Goal: Connect different networks
a  c|1.1  2.2 | X
ROUTER
1.0
c
1.1
a
a  b|1.1  1.2 | Y
1.2
b
2.0
d
2.1
e
2.2
f
d  f |1.1  2.2 | X
Router looks at IP addresses (1.1, …)
Each network uses local addresses (e.g., a, b, c, …)
Multiple Access
• Goal: Share one medium (e.g., WiFi)
“Collision”
Wait random time after collision
C|A|
C|A|
A|B|
A|B|
“Busy”
A
B
time
Wait until idle
C
DNS: Domain Name Service
• Translate Name into IP address
(e.g., google.com into 216.239.57.99)
• Directory of DNS is distributed:
.com, .edu, …
.edu: berkeley.edu, stanford.edu, …
• Mapping can depend on source address
• Mapping can be done to multiple addresses
P2P: Peer-to-peer
• Goal: All peers become servers
• Example:
• Each peer knows the addresses of a set of peers: his
“friends”
• To find a file, peer A asks his friends who in turn ask their
friends, and so on, until someone, B, says he has the file…
(can limit search); A then asks B for the file.
• Many variations are possible. The key idea is that there is no
specialized server; every client becomes a server.
VoIP: Voice over IP
• Goal: Place phone calls over Internet
(Should be cheaper because the Internet
infrastructure is much lighter than that of the phone
network.)
• Steps:
• Gateway converts phone signal into IP packets and viceversa
• Protocol to convert phone number into gateway IP address
• Gateway converts usual control signals (dial tone, ringing,
busy, …) into IP packets and vice-versa
Protocols:
•
•
•
•
•
•
IP: Internet Protocol
TCP: Transmission Control Protocol
UDP: User Datagram Protocol
HTTP: Hypertext Transfer Protocol
FTP: File Transfer Protocol
ARP: Address Resolution Protocol
HTTP
FTP
TCP
UDP
IP
Protocols:
Application
Application
HTTP, FTP, …
UDP - TCP
Data
Transport
TH
Data
Asynchronous routed path
Network
Data Link
Control
Physical
Interface
PH
Data
IP
Asynchronous reliable bit pipe
FH
Data
Asynchronous routed path
Network
Data Link
Control
Eth.
Synchronous unreliable bit pipe
Fiber, Wires, WL
Physical
Interface
Physical Link
End Node
Transport
PH
Network
Data
Asynchronous reliable bit pipe
FH
Data
Synchronous unreliable bit pipe
Data Link
Control
Physical
Interface
Physical Link
Router
End Node
IP: Internet Protocol
• Delivers packets between any two hosts
• Organizes address, manages routing tables
• Addresses: 32 bits, arranged so that prefix determines
next router toward destination
• Routing algorithm: Essentially shortest path. Done in
two levels: nodes are grouped; shortest path inside
each group and across groups.
• Tables updated periodically to adjust to changes
TCP: Transmission Control Protocol
• Implements reliable delivery of byte stream
between hosts
• Multiplexes multiple connections to and from a
host: adds a “port” number
• End-to-end retransmissions
• Regulates flow to avoid congesting
• Destination (flow control)
• Routers (congestion control)
• Method: ACKs, control number of
unacknowledged packets
TCP Service:
ports
HTTP ftp DNS
Application
p1
p2
p1 p2
p3
p1
p2
Transport
IP
A
B
C
[A | B | p1 | p2 | …]
TCP: Byte Stream  Ordered, reliable, well-paced
Congestion Control:
• Flows share links:
How to share the links bandwidth?
TCP Algorithm: AIMD
• Try to be fair
A
D
C
C
x
B
y
E
y
Limit rates:
x=y
x
TOC – Congestion Control - TCP Algorithm – AIMD
TCP: Summary
64KB
W
0.5
3DA
3DA
0.5
X
X
0.5
X
1
TO
SS
3
TO
0.5
X
3
CA
SS
CA
Flow Control
• Objective: Avoid saturating destination
• Algorithm: Receiver avertizes window RAW
window = min{RAW – OUT, W}
where
OUT = Oustanding = Last sent – last ACKed
W = Cong. Window from AIMD + refinements
RAW
[ACK | RAW | …]
TCP Phases:
SYN k
3-way handshake
SYN n; ACK k+1
DATA k+1; ACK n+1
ACK k+n+1
data exchange
FIN
½ close
FIN ACK
FIN
FIN ACK
½ close
UDP: User Datagram Protocol
• Unreliable delivery of packets with error
detection
• Multiplexes multiple connections to and from a
host: adds a “port” number
• Adds error detection code for the packet
• No retransmission, no flow control
FTP: File Transfer Protocol
• Reliable delivery of file between hosts
• Converts file into byte stream for TCP
HTTP
• Transfer of html files
• Sets up TCP connections and FTP to transfer
files
• Closes connections after transfer
ARP: Address Resolution Protocol
• Discovers local address from IP address
• Example: In “Internetworking” slide, host 1.1 uses ARP
to discover local address b of 1.2
• Protocol:
• Host 1.1 broadcasts request on local network: Who is 1.2?
• Host 1.2 replies to 1.1; local address of source (b) is in the
packet.
Technology
• Communication Links
• Switches
Communication Links
Fibers
Cat5 Unshielded
Twisted Pairs
Coaxial Cable
Wireless
Communication Links
• Convert bits string into signals that propagate as
electromagnetic waves
• Optical: Typically ON/OFF  pulses of light; encoding makes
sure there are enough transitions for the receiver to remain in
sync
• Fibers: up to 10Gbps over 100 km per wavelength; up to 128
wavelengths per fiber
• Wired and wireless: Typically pulses of sine waves at different
frequencies or phases to encode groups of bits
• Wires: 100 Mbps over 100 m
• Wireless: 100 Mbps over 30 m with multiple antennas (802.11n)
• Error control codes: typically to detect errors
Telephone Switch
Router
Switches
• Various links: optical, cable, wires
• Looks up destination address and sends packet
to corresponding output port
• May perform some traffic policing (limit rate)
and some differentiated service (e.g., priority to
VoIP packets)
• Fast router: total throughput of 500 Gbps
• From a few to 128 ports