goodfds
Chapter 1: Introduction
Our goal:
get “feel” and terminology
more depth, detail later in course
approach:
use Internet as example
Overview:
what’s the Internet?
what’s a protocol?
network edge; hosts, access net, physical media
network core: packet/circuit switching, Internet structure
performance: loss, delay, throughput
security
protocol layers, service models
history
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
What’s the Internet: “nuts and bolts” view
millions of connected computing devices: hosts = end systems
running network apps
“Cool” internet appliances
What’s the Internet: “nuts and bolts” view
protocols control sending, receiving of msgs
e.g., TCP, IP, HTTP, Skype, Ethernet
Internet: “network of networks”
loosely hierarchical
public Internet versus private intranet
Internet standards
RFC: Request for comments
IETF: Internet Engineering Task Force
What’s the Internet: a service view
communication infrastructure enables distributed applications:
Web, VoIP, email, games, e-commerce, file sharing
communication services provided to apps:
reliable data delivery from source to destination
“best effort” (unreliable) data delivery
What’s a protocol?
human protocols:
“what’s the time?”
“I have a question”
introductions
… specific msgs sent
… specific actions taken when msgs received, or other events
network protocols:
machines rather than humans
all communication activity in Internet governed by protocols
What’s a protocol?
a human protocol and a computer network protocol:
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
A closer look at network structure:
network edge: applications and hosts
The network edge:
end systems (hosts):
run application programs
e.g. Web, email
at “edge of network”
Access networks and physical media
Q: How to connect end systems to edge router?
residential access nets
institutional access networks (school, company)
mobile access networks
Keep in mind:
bandwidth (bits per second) of access network?
shared or dedicated?
Residential access: point to point access
Dialup via modem
up to 56Kbps direct access to router (often less)
Can’t surf and phone at same time: can’t be “always on”
Residential access: cable modems
HFC: hybrid fiber coax
asymmetric: up to 30Mbps downstream, 2 Mbps upstream
network of cable and fiber attaches homes to ISP router
homes share access to router
deployment: available via cable TV companies
Residential access: cable modems
Cable Network Architecture: Overview
Company access: local area networks
company/univ local area network (LAN) connects end system to edge router
Ethernet:
10 Mbs, 100Mbps, 1Gbps, 10Gbps Ethernet
modern configuration: end systems connect into Ethernet switch
LANs: chapter 5
Wireless access networks
shared wireless access network connects end system to router
via base station aka “access point”
wireless LANs:
802.11b/g (WiFi): 11 or 54 Mbps
802.11n/ac/ad(WiFi): 100’s~1’s Gbps Mbps
wider-area wireless access
provided by telco operator
~10’s Mbps over cellular system (4G LTE)
next up (?): 5G (1~10’s Gbps) over wide area
Home networks
Typical home network components:
DSL or cable modem
router/firewall/NAT
Ethernet
wireless access
point
Physical Media
Bit: propagates between
transmitter/rcvr pairs
physical link: what lies between transmitter & receiver
guided media:
signals propagate in solid media: copper, fiber, coax
unguided media:
signals propagate freely, e.g., radio
Twisted Pair (TP)
two insulated copper wires
Category 3: traditional phone wires, 10 Mbps Ethernet
Category 5:
100Mbps Ethernet
Physical Media: coax, fiber
Coaxial cable:
two concentric copper conductors
bidirectional
baseband:
single channel on cable
legacy Ethernet
broadband:
multiple channels on cable
HFC
Physical media: radio
signal carried in electromagnetic spectrum
no physical “wire”
bidirectional
propagation environment effects:
reflection
obstruction by objects
interference
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
The Network Core
mesh of interconnected routers
the fundamental question: how is data transferred through net?
circuit switching: dedicated circuit per call: telephone net
packet-switching: data sent thru net in discrete “chunks”
Network Core: Circuit Switching
End-end resources reserved for “call”
link bandwidth, switch capacity
dedicated resources: no sharing
circuit-like (guaranteed) performance
call setup required
Network Core: Circuit Switching
network resources (e.g., bandwidth) divided into “pieces”
pieces allocated to calls
resource piece idle if not used by owning call (no sharing)
Circuit Switching: FDM and TDM
Numerical example
How long does it take to send a file of 640,000 bits from host A to host B over
a circuit-switched network?
All links are 1.536 Mbps
Each link uses TDM with 24 slots/sec
500 msec to establish end-to-end circuit
Let’s work it out!
Network Core: Packet Switching
each end-end data stream divided into packets
user A, B packets share network resources
each packet uses full link bandwidth
resources used as needed
Packet Switching: Statistical Multiplexing
Sequence of A & B packets does not have fixed pattern, bandwidth shared on
demand statistical multiplexing.
TDM: each host gets same slot in revolving TDM frame.
Packet-switching: store-and-forward
takes L/R seconds to transmit (push out) packet of L bits on to link at R bps
store and forward: entire packet must
arrive at router before it can be transmitted on next link
delay = 3L/R (assuming zero propagation delay)
Example:
L = 7.5 Mbits
R = 1.5 Mbps
transmission delay = 15 sec
Packet switching versus circuit switching
1 Mb/s link
each user:
100 kb/s when “active”
active 10% of time
circuit-switching:
10 users
packet switching:
with 35 users, probability > 10 active at same time is less than .0004
Packet switching allows more users to use network!
Packet switching versus circuit switching
great for bursty data
resource sharing
simpler, no call setup
excessive congestion: packet delay and loss
protocols needed for reliable data transfer, congestion control
Q: How to provide circuit-like behavior?
bandwidth guarantees needed for audio/video apps
still an unsolved problem (chapter 7)
Is packet switching a “slam dunk winner?”
Internet structure: network of networks
roughly hierarchical
at center: “tier-1” ISPs (e.g., Verizon, Sprint, AT&T, Cable and Wireless),
national/international coverage
treat each other as equals
8 Interconnection Regions in US for Tier-1 ISPs
Tier-1 ISP: e.g., Sprint
Internet structure: network of networks
“Tier-2” ISPs: smaller (often regional) ISPs
Connect to one or more tier-1 ISPs, possibly other tier-2 ISPs
Internet structure: network of networks
“Tier-3” ISPs and local ISPs
last hop (“access”) network (closest to end systems)
Internet structure: network of networks
a packet passes through many networks!
Why?
Internet
Better scaling
Network heterogeneity
Incremental expansion/deployment
Decentralized management
No single entity is controlling/operating the entire Internet
Telephone network
Each operator owns and operates its own network
Harder to interoperate
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
Performance Metrics
How fast?
THROUGHPUT
How responsive is the network?
DELAY
How good the packet delivery?
LOSS
How do loss and delay occur?
packets queue in router buffers
packet arrival rate to link exceeds output link capacity
packets queue, wait for turn
Four sources of packet delay
1. nodal processing:
check bit errors
determine output link
Delay in packet-switched networks
3. Transmission delay:
R=link bandwidth (bps)
L=packet length (bits)
time to send bits into link = L/R
4. Propagation delay:
d = length of physical link
s = propagation speed in medium (~2×108 m/sec)
propagation delay = d/s
Caravan analogy
cars “propagate” at
100 km/hr
toll booth takes 12 sec to service car (transmission time)
car~bit; caravan ~ packet
Q: How long until caravan is lined up before 2nd toll booth?
Time to “push” entire caravan through toll booth onto highway = 12*10 = 120 sec
Time for last car to propagate from 1st to 2nd toll both: 100km/(100km/hr)= 1
hr
A: 62 minutes
Caravan analogy (more)
Cars now “propagate” at
1000 km/hr
Toll booth now takes 1 min to service a car
Q: Will cars arrive to 2nd booth before all cars serviced at 1st booth?
Yes! After 7 min, 1st car at 2nd booth and 3 cars still at 1st booth.
1st bit of packet can arrive at 2nd router before packet is fully transmitted
at 1st router!
See Ethernet applet at AWL Web site
Nodal delay
dproc = processing delay
typically a few microsecs or less
dqueue = queuing delay
depends on congestion
dtrans = transmission delay
= L/R, significant for low-speed links
dprop = propagation delay
a few microsecs to hundreds of msecs
Queueing delay (revisited)
R=link bandwidth (bps)
L=packet length (bits)
a=average packet arrival rate
“Real” Internet delays and routes
What do “real” Internet delay & loss look like?
Traceroute program: provides delay measurement from source to router along
end-end Internet path towards destination.
For all i:
sends three packets that will reach router i on path towards destination
router i will return packets to sender
sender times interval between transmission and reply.
“Real” Internet delays and routes
Packet loss
queue (aka buffer) preceding link in buffer has finite capacity
packet arriving to full queue dropped (aka lost)
lost packet may be retransmitted by previous node, by source end system, or not
at all
Throughput
throughput: rate (bits/time unit) at which bits transferred between
sender/receiver
instantaneous: rate at given point in time
average: rate over longer period of time
Throughput (more)
Rs < Rc What is average end-end
throughput?
Throughput: Internet scenario
per-connection end-end throughput: min(Rc,Rs,R/10)
in practice: Rc or Rs is often bottleneck
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
Protocol “Layers”
Networks are complex!
many “pieces”:
hosts
routers
links of various media
applications
protocols
hardware, software
Question:
Is there any hope of organizing structure of network?
Or at least our discussion of networks?
DIVIDE AND CONQUER!
Organization of air travel
a series of steps
Layering of airline functionality
Layers: each layer implements a service
via its own internal-layer actions
relying on services provided by layer below
Why layering?
Dealing with complex systems:
explicit structure allows identification, relationship of complex system’s
pieces
layered reference model for discussion
modularization eases maintenance, updating of system
change of implementation of layer’s service transparent to rest of system
e.g., change in gate procedure doesn’t affect rest of system
layering considered harmful?
Internet protocol stack
application: supporting network applications
FTP, SMTP, HTTP
transport: process-process data transfer
TCP, UDP
network: routing of datagrams from source to destination
IP, routing protocols
link: data transfer between neighboring
network elements
PPP, Ethernet
physical: bits “on the wire”
ISO/OSI reference model
presentation: allow applications to interpret meaning of data, e.g.,
encryption, compression, machine-specific conventions
session: synchronization, checkpointing, recovery of data exchange
Internet stack “missing” these layers!
these services, if needed, must be implemented in application
needed?
Encapsulation
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
Network Security
The field of network security is about:
how bad guys can attack computer networks
how we can defend networks against attacks
how to design architectures that are immune to attacks
Internet not originally designed with (much) security in mind
original vision: “a group of mutually trusting users attached to a transparent
network”
Internet protocol designers playing “catch-up”
Security considerations in all layers!
Bad guys can put malware into hosts via Internet
Malware can get in host from a virus, worm, or trojan horse.
Spyware malware can record keystrokes, web sites visited, upload info to
collection site.
Infected host can be enrolled in a botnet, used for spam and DDoS attacks.
Malware is often self-replicating: from an infected host, seeks entry into
other hosts
Bad guys can put malware into hosts via Internet
Trojan horse
Hidden part of some otherwise useful software
Today often on a Web page (Active-X, plugin)
Virus
infection by receiving object (e.g., e-mail attachment), actively executing
self-replicating: propagate itself to other hosts, users
Bad guys can attack servers and network infrastructure
Denial of service (DoS): attackers make resources (server, bandwidth)
unavailable to legitimate traffic by overwhelming resource with bogus traffic
The bad guys can sniff packets
Packet sniffing:
broadcast media (shared Ethernet, wireless)
promiscuous network interface reads/records all packets (e.g., including
passwords!) passing by
The bad guys can use false source addresses
IP spoofing: send packet with false source address
The bad guys can record and playback
record-and-playback: sniff sensitive info (e.g., password), and use later
password holder is that user from system point of view
Network Security
more throughout this course
chapter 8: focus on security
crypographic techniques: obvious uses and not so obvious uses
Chapter 1: roadmap
1.1 What is the Internet?
1.2 Network edge
end systems, access networks, links
1.3 Network core
circuit switching, packet switching,
network structure
1.4 Delay, loss and throughput in packet-switched networks
1.5 Protocol layers, service models
1.6 Networks under attack: security
1.7 History
Internet History
1961: Kleinrock – queueing theory shows effectiveness of packet-switching
1964: Baran – packet-switching in military nets
1967: ARPAnet conceived by Advanced Research Projects Agency
1969: first ARPAnet node operational
1972:
ARPAnet public demonstration
NCP (Network Control Protocol) first host-host protocol
first e-mail program
ARPAnet has 15 nodes
Internet History
1970: ALOHAnet satellite network in Hawaii
1974: Cerf and Kahn – architecture for interconnecting networks
1976: Ethernet at Xerox PARC
ate70’s: proprietary architectures: DECnet, SNA, XNA
late 70’s: switching fixed length packets (ATM precursor)
1979: ARPAnet has 200 nodes
Cerf and Kahn’s internetworking principles:
minimalism, autonomy – no internal changes required to interconnect networks
best effort service model
stateless routers
decentralized control
define today’s Internet architecture
Internet History
1983: deployment of TCP/IP
1982: smtp e-mail protocol defined
1983: DNS defined for name-to-IP-address translation
1985: ftp protocol defined
1988: TCP congestion control
new national networks: Csnet, BITnet, NSFnet, Minitel
100,000 hosts connected to confederation of networks
Internet History
Early 1990’s: ARPAnet decommissioned
1991: NSF lifts restrictions on commercial use of NSFnet (decommissioned, 1995)
early 1990s: Web
hypertext [Bush 1945, Nelson 1960’s]
HTML, HTTP: Berners-Lee
1994: Mosaic, later Netscape
late 1990’s: commercialization of the Web
Late 1990’s – 2000’s:
more killer apps: instant messaging, P2P file sharing
network security to forefront
est. 50 million host, 100 million+ users
backbone links running at Gbps
Internet History
2007:
~500 million hosts
Voice, Video over IP
P2P applications: BitTorrent (file sharing) Skype (VoIP), PPLive (video)
more applications: YouTube, gaming
wireless, mobility
2010 ~ now:
Data center networks for cloud
Wireless & mobile for smartphones
Internet of Things
Introduction: Summary
Covered a “ton” of material!
Internet overview
what’s a protocol?
network edge, core, access network
packet-switching versus circuit-switching
Internet structure
performance: loss, delay, throughput
layering, service models
security
history
You now have:
context, overview, “feel” of networking
more depth, detail to follow!
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
Chapter 2: Application Layer
Our goals:
conceptual, implementation aspects of network application protocols
transport-layer service models
client-server paradigm
peer-to-peer paradigm
learn about protocols by examining popular application-level protocols
HTTP
FTP
SMTP / POP3 / IMAP
DNS
programming network applications
socket API
Some network apps
e-mail
web
instant messaging
remote login
P2P file sharing
multi-user network games
streaming stored video clips
voice over IP
real-time video conferencing
grid computing
Creating a network app
write programs that
run on (different) end systems
communicate over network
e.g., web server software communicates with browser software
No need to write software for network-core devices
Network-core devices do not run user applications
applications on end systems allows for
rapid app development, propagation
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
2.9 Building a Web server
Application architectures
Client-server
Peer-to-peer (P2P)
Hybrid of client-server and P2P
Client-server architecture
server:
always-on host
permanent IP address
server farms for scaling
clients:
communicate with server
may be intermittently connected
may have dynamic IP addresses
do not communicate directly with each other
Pure P2P architecture
no always-on server
arbitrary end systems directly communicate
peers are intermittently connected and change IP addresses
Highly scalable but difficult to manage
Hybrid of client-server and P2P
Skype
voice-over-IP P2P application
centralized server: finding address of remote party:
client-client connection: direct (not through server)
Instant messaging
chatting between two users is P2P
centralized service: client presence detection/location
user registers its IP address with central server when it comes online
user contacts central server to find IP addresses of buddies
Processes communicating
Process: program running within a host.
within same host, two processes communicate using inter-process communication (defined by OS).
processes in different hosts communicate by exchanging messages
Client process: process that initiates communication
Server process: process that waits to be contacted
Sockets
process sends/receives messages to/from its socket
socket analogous to door
sending process shoves message out door
sending process relies on transport infrastructure on other side of door which
brings message to socket at receiving process
Addressing processes
to receive messages, process must have
identifier
host device has unique 32-bit IP address
Q: does IP address of host suffice for
identifying the process?
Addressing processes
identifier includes both IP address and port numbers associated with process on
host.
Example port numbers:
HTTP server: 80
Mail server: 25
to send HTTP message to gaia.cs.umass.edu web server:
IP address: 128.119.245.12
Port number: 80
more shortly…
to receive messages, process must have
identifier
host device has unique 32-bit IP address
Q: does IP address of host on which
process runs suffice for identifying the process?
A: No, many processes can be running on same host
App-layer protocol defines
Types of messages exchanged,
e.g., request, response
Message syntax:
what fields in messages & how fields are delineated
Message semantics
meaning of information in fields
Rules for when and how processes send & respond to messages
Public-domain protocols:
defined in RFCs
allows for interoperability
e.g., HTTP, SMTP
Proprietary protocols:
e.g., Skype
What transport service does an app need?
Data loss
some apps (e.g., audio) can tolerate some loss
other apps (e.g., file transfer, telnet) require 100% reliable data transfer
Timing
some apps (e.g., Internet telephony, interactive games) require low delay to be
“effective”
Transport service requirements of common apps
Internet transport protocols services
TCP service:
connection-oriented: setup required between client and server processes
reliable transport between sending and receiving process
flow control: sender won’t overwhelm receiver
congestion control: throttle sender when network overloaded
does not provide: timing, minimum throughput guarantees, security
UDP service:
unreliable data transfer between sending and receiving process
does not provide: connection setup, reliability, flow control, congestion
control, timing, throughput guarantee, or security
Q: why bother? Why is there a UDP?
Internet apps: application, transport
protocols
Chapter 2: Application layer
2.1 Principles of network applications
app architectures
app requirements
2.2 Web and HTTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
Web and HTTP
First some jargon
Web page consists of objects
Object can be HTML file, JPEG image, Java applet, audio file,…
Web page consists of base HTML-file which includes several referenced objects
Each object is addressable by a URL
Example URL:
HTTP overview
HTTP: hypertext transfer protocol
Web’s application layer protocol
client/server model
client: browser that requests, receives, “displays” Web objects
server: Web server sends objects in response to requests
HTTP overview (continued)
Uses TCP:
client initiates TCP connection (creates socket) to server, port 80
server accepts TCP connection from client
HTTP messages (application-layer protocol messages) exchanged between browser
(HTTP client) and Web server (HTTP server)
TCP connection closed
HTTP is “stateless”
server maintains no information about past client requests
HTTP connections
Nonpersistent HTTP
At most one object is sent over a TCP connection.
Persistent HTTP
Multiple objects can be sent over single TCP connection between client and
server.
Nonpersistent HTTP
Suppose user enters URL www.someSchool.edu/someDepartment/home.index
1a. HTTP client initiates TCP connection to HTTP server (process) at
www.someSchool.edu on port 80
Nonpersistent HTTP (cont.)
5. HTTP client receives response message containing html file, displays
html. Parsing html file, finds 10
referenced jpeg objects
Non-Persistent HTTP: Response time
Definition of RTT: time for a small packet to travel from client to server and
back.
Response time:
one RTT to initiate TCP connection
one RTT for HTTP request and first few bytes of HTTP response to return
file transmission time
total = 2RTT+transmit time
Persistent HTTP
Nonpersistent HTTP issues:
requires 2 RTTs per object
OS overhead for each TCP connection
browsers often open parallel TCP connections to fetch referenced objects
Persistent HTTP
server leaves connection open after sending response
subsequent HTTP messages between same
client/server sent over open connection
client sends requests as soon as it encounters a referenced object
as little as one RTT for all the referenced objects
HTTP request message
two types of HTTP messages: request, response
HTTP request message:
ASCII (human-readable format)
HTTP request message: general format
Uploading form input
Post method:
Web page often includes form input
Input is uploaded to server in entity body
URL method:
Uses GET method
Input is uploaded in URL field of request line:
Method types
HTTP/1.0
GET
POST
HEAD
asks server to leave requested object out of response
HTTP/1.1
GET, POST, HEAD
PUT
uploads file in entity body to path specified in URL field
DELETE
deletes file specified in the URL field
HTTP response message
HTTP response status codes
200 OK
request succeeded, requested object later in this message
301 Moved Permanently
requested object moved, new location specified later in this message
(Location:)
400 Bad Request
request message not understood by server
404 Not Found
requested document not found on this server
505 HTTP Version Not Supported
Trying out HTTP (client side) for yourself
1. Telnet to your favorite Web server:
User-server state: cookies
Many major Web sites use cookies
Four components:
1) cookie header line of HTTP response message
2) cookie header line in HTTP request message
3) cookie file kept on user’s host, managed by user’s browser
4) back-end database at Web site
Example:
Susan always access Internet always from PC
visits specific e-commerce site for first time
when initial HTTP requests arrives at site, site creates:
unique ID
entry in backend database for ID
Cookies: keeping “state” (cont.)
Cookies (continued)
What cookies can bring:
authorization
shopping carts
recommendations
user session state (Web e-mail)
Web caches (proxy server)
user sets browser: Web accesses via
cache
browser sends all HTTP requests to cache
object in cache: cache returns object
else cache requests object from origin server, then returns object to client
More about Web caching
cache acts as both client and server
typically cache is installed by ISP (university, company, residential ISP)
Why Web caching?
reduce response time for client request
reduce traffic on an institution’s access link.
Internet dense with caches: enables “poor” content providers to effectively
deliver content (but so does P2P file sharing)
Caching example
Assumptions
average object size = 100,000 bits
avg. request rate from institution’s browsers to origin servers = 15/sec
delay from institutional router to any origin server and back to router = 2 sec
Consequences
utilization on LAN = 15%
utilization on access link = 100%
total delay = Internet delay + access
delay + LAN delay
=
2 sec + minutes + milliseconds
Caching example (cont)
possible solution
increase bandwidth of access link to, say, 10 Mbps
consequence
utilization on LAN = 15%
utilization on access link = 15%
Total delay = Internet delay + access
delay + LAN delay
=
2 sec + msecs + msecs
often a costly upgrade
Caching example (cont)
possible solution: install cache
suppose hit rate is 0.4
consequence
40% requests will be satisfied almost immediately
60% requests satisfied by origin server
utilization of access link reduced to 60%, resulting in negligible delays (say 10 msec)
total avg delay = Internet delay +
access delay + LAN delay = .6*(2.01) secs + .4*milliseconds < 1.4 secs
Conditional GET
Goal: don’t send object if cache has up-to-date cached version
cache: specify date of cached copy in HTTP request
If-modified-since: <date>
server: response contains no object if cached copy is up-to-date:
HTTP/1.0 304 Not Modified
Ongoing Effort on HTTP 2.0
The next planned version of HTTP after HTTP 1.1 (RFC 2616 in 1999)
1.4% of Websites support it (Sept. 2015)
Designed to improve throughput of client-server connections.
Based on Google’s SPDY
Backward compatible with transaction semantics of HTTP 1.1
New features:
Multiplexing multiple streams over one HTTP2.0 connection; request-response
pipelining
Header compression
Server push (preemptive transfer to clients)
Web 2.0
No update on the technical specs
But rather to cumulative changes in the way software developers and users use
the Web
Facilitate interactive information sharing, interoperability and user-centric
design and collaboration on the Web
Web-based communities, hosted services, web applications, blogs,
social-networking sites
Web 2.0
“Network as platform” computing
Build applications on Web, not desktops
Use rich, user-friendly interface based on Ajax and similar client-side
interactivity tools
Typically XML + Javascript or Flash
Or full client-server application frameworks such as Flex, Openlaszlo, and ZK…
Standard Web browser uses plugins and software extensions to handle
Web 3.0 (Semantic Web)
Extends the hyperlinked human-readable web pages by inserting machine-readable
metadata about pages and how they are related to each other
Using extensible makeup language (XML), resource description framework (RDF),
web ontology language (OWL)
XML: syntax for content structures within documents
RDF: expressing data models
OWL: adds more vocabularies on describing properties and classes
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
2.9 Building a Web server
FTP: the file transfer protocol
transfer file to/from remote host
client/server model
client: side that initiates transfer (either to/from remote)
server: remote host
ftp: RFC 959
ftp server: port 21
FTP: separate control, data connections
FTP client contacts FTP server at port 21, TCP is transport protocol
client authorized over control connection
client browses remote directory by sending commands over control connection.
when server receives file transfer
command, server opens 2nd TCP connection (for file) to client
after transferring one file, server closes data connection.
FTP commands, responses
Sample commands:
sent as ASCII text over control channel
USER username
PASS password
LIST return list of file in current directory
RETR filename retrieves (gets) file
STOR filename stores (puts) file onto remote host
Sample return codes
status code and phrase (as in HTTP)
331 Username OK, password required
125 data connection already open; transfer starting
425 Can’t open data connection
452 Error writing file
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
Electronic Mail
Three major components:
user agents
mail servers
simple mail transfer protocol: SMTP
User Agent
a.k.a. “mail reader”
composing, editing, reading mail messages
e.g., Eudora, Outlook, elm, Mozilla Thunderbird
outgoing, incoming messages stored on server
Electronic Mail: mail servers
Mail Servers
mailbox contains incoming messages for user
message queue of outgoing (to be sent) mail messages
SMTP protocol between mail servers to send email messages
client: sending mail server
“server”: receiving mail server
Electronic Mail: SMTP [RFC 2821]
uses TCP to reliably transfer email message from client to server, port 25
direct transfer: sending server to receiving server
three phases of transfer
handshaking (greeting)
transfer of messages
closure
command/response interaction
commands: ASCII text
response: status code and phrase
messages must be in 7-bit ASCII
Scenario: Alice sends message to Bob
1) Alice uses UA to compose message and “to” bob@someschool.edu
2) Alice’s UA sends message to her mail server; message placed in message queue
3) Client side of SMTP opens TCP connection with Bob’s mail server
4) SMTP client sends Alice’s message over the TCP connection
5) Bob’s mail server places the message in Bob’s mailbox
6) Bob invokes his user agent to read message
Sample SMTP interaction
Try SMTP interaction for yourself:
telnet servername 25
see 220 reply from server
enter HELO, MAIL FROM, RCPT TO, DATA, QUIT commands
above lets you send email without using email client (reader)
SMTP: final words
SMTP uses persistent connections
SMTP requires message (header & body) to be in 7-bit ASCII
SMTP server uses CRLF.CRLF to determine end of message
Comparison with HTTP:
HTTP: pull
SMTP: push
both have ASCII command/response interaction, status codes
HTTP: each object encapsulated in its own response msg
SMTP: multiple objects sent in multipart msg
Mail message format
SMTP: protocol for exchanging email msgs
RFC 822: standard for text message format:
header lines, e.g.,
To:
From:
Subject:
different from SMTP commands!
body
the “message”, ASCII characters only
Message format: multimedia extensions
MIME: multimedia mail extension, RFC 2045, 2056
additional lines in msg header declare MIME content type
Mail access protocols
SMTP: delivery/storage to receiver’s server
Mail access protocol: retrieval from server
POP: Post Office Protocol [RFC 1939]
authorization (agent <–>server) and download
IMAP: Internet Mail Access Protocol [RFC 1730]
more features (more complex)
manipulation of stored msgs on server
HTTP: gmail, Hotmail, Yahoo! Mail, etc.
POP3 protocol
authorization phase
client commands:
user: declare username
pass: password
server responses
+OK
-ERR
transaction phase, client:
list: list message numbers
retr: retrieve message by number
dele: delete
quit
POP3 (more) and IMAP
More about POP3
Previous example uses “download and delete” mode.
Bob cannot re-read e-mail if he changes client
“Download-and-keep”: copies of messages on different clients
POP3 is stateless across sessions
IMAP
Keep all messages in one place: the server
Allows user to organize messages in folders
IMAP keeps user state across sessions:
names of folders and mappings between message IDs and folder name
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
2.9 Building a Web server
DNS: Domain Name System
People: many identifiers:
SSN, name, passport #
Internet hosts, routers:
IP address (32 bit) – used for addressing datagrams
“name”, e.g., ww.yahoo.com – used by humans
Q: map between IP addresses and name ?
Domain Name System:
distributed database implemented in hierarchy of many name servers
application-layer protocol host, routers, name servers to communicate to
resolve names (address/name translation)
note: core Internet function, implemented as application-layer protocol
complexity at network’s “edge”
DNS
DNS services
hostname to IP address translation
host aliasing
Canonical, alias names
mail server aliasing
load distribution
replicated Web servers: set of IP addresses for one canonical name
Why not centralize DNS?
single point of failure
traffic volume
distant centralized database
maintenance
doesn’t scale!
Distributed, Hierarchical Database
Client wants IP for www.amazon.com; 1st approx:
client queries a root server to find com DNS server
client queries com DNS server to get amazon.com DNS server
client queries amazon.com DNS server to get
IP address for www.amazon.com
DNS: Root name servers
contacted by local name server that can not resolve name
root name server:
contacts authoritative name server if name mapping not known
gets mapping
returns mapping to local name server
TLD and Authoritative Servers
Top-level domain (TLD) servers:
responsible for com, org, net, edu, etc,
and all top-level country domains uk, fr, ca, jp.
Network Solutions maintains servers for com TLD
Educause for edu TLD
Authoritative DNS servers:
organization’s DNS servers, providing authoritative hostname to IP mappings for
organization’s servers (e.g., Web, mail).
can be maintained by organization or service provider
Local Name Server
does not strictly belong to hierarchy
each ISP (residential ISP, company, university) has one.
also called “default name server”
when host makes DNS query, query is sent to its local DNS server
acts as proxy, forwards query into hierarchy
DNS name
resolution example
Host at cis.poly.edu wants IP address for gaia.cs.umass.edu
DNS name
resolution example
DNS: caching and updating records
once (any) name server learns mapping, it caches mapping
cache entries timeout (disappear) after some time
TLD servers typically cached in local name servers
Thus root name servers not often visited
update/notify mechanisms under design by IETF
RFC 2136
http://www.ietf.org/html.charters/dnsind-charter.html
DNS records
DNS: distributed db storing resource records (RR)
Type=NS
name is domain (e.g. foo.com)
value is hostname of authoritative name server for this domain
DNS protocol, messages
DNS protocol : query and reply messages, both with same message format
DNS protocol, messages
Inserting records into DNS
example: new startup “Network Utopia”
register name networkuptopia.com at DNS registrar (e.g., Network Solutions)
provide names, IP addresses of authoritative name server (primary and
secondary)
registrar inserts two RRs into com TLD server:
(networkutopia.com, dns1.networkutopia.com, NS)
(dns1.networkutopia.com, 212.212.212.1, A)
create authoritative server Type A record for www.networkuptopia.com; Type MX
record for networkutopia.com
How do people get IP address of your Web site?
Chapter 2: Application layer
2.1 Principles of network applications
app architectures
app requirements
2.2 Web and HTTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
Pure P2P architecture
no always-on server
arbitrary end systems directly communicate
peers are intermittently connected and change IP addresses
Three topics:
File distribution
Searching for information
Case Study: Skype
File Distribution: Server-Client vs P2P
Question : How much time to distribute file from one server to N peers?
File distribution time: server-client
server sequentially sends N copies:
NF/us time
client i takes F/di time to download
File distribution time: P2P
server must send one copy: F/us time
client i takes F/di time to download
NF bits must be uploaded (aggregate)
File distribution: BitTorrent
BitTorrent (1)
file divided into 256KB chunks.
peer joining torrent:
has no chunks, but will accumulate them over time
registers with tracker to get list of peers, connects to subset of peers (“neighbors”)
while downloading, peer uploads chunks
to other peers.
peers may come and go
once peer has entire file, it may (selfishly) leave or (altruistically) remain
BitTorrent (2)
Pulling Chunks
at any given time, different peers have different subsets of file chunks
periodically, a peer (Alice) asks each neighbor for list of chunks that they
have.
Alice sends requests for her missing chunks
rarest first
BitTorrent: Tit-for-tat
P2P: searching for information
File sharing (eg e-mule)
Index dynamically tracks the locations of files that peers share.
Peers need to tell index what they have.
Peers search index to determine where files can be found
Instant messaging
Index maps user names to locations.
When user starts IM application, it needs to inform index of its location
Peers search index to determine IP address of user.
P2P: centralized index
original “Napster” design
1) when peer connects, it informs central server:
IP address
content
2) Alice queries for “Hey Jude”
3) Alice requests file from Bob
P2P: problems with centralized directory
single point of failure
performance bottleneck
copyright infringement: “target” of lawsuit is obvious
file transfer is decentralized, but
locating content is highly centralized
Query flooding
fully distributed
no central server
used by Gnutella
Each peer indexes the files it makes available for sharing (and no other files)
overlay network: graph
edge between peer X and Y if there’s a TCP connection
all active peers and edges form overlay net
edge: virtual (not physical) link
given peer typically connected with < 10 overlay neighbors
Query flooding
Gnutella: Peer joining
joining peer Alice must find another peer in Gnutella network: use list of
candidate peers
Alice sequentially attempts TCP connections with candidate peers until
connection setup with Bob
Flooding: Alice sends Ping message to Bob; Bob forwards Ping message to his
overlay neighbors (who then forward to their neighbors….)
peers receiving Ping message respond to Alice with Pong message
Alice receives many Pong messages, and can then setup additional TCP
connections
Hierarchical Overlay
between centralized index, query flooding approaches
each peer is either a super node or assigned to a super node
TCP connection between peer and its super node.
TCP connections between some pairs of super nodes.
Super node tracks content in its
children
P2P Case study: Skype
inherently P2P: pairs of users communicate.
proprietary application-layer protocol (inferred via reverse engineering)
hierarchical overlay with SNs
Index maps usernames to IP addresses; distributed over SNs
Peers as relays
Problem when both Alice and Bob are behind
“NATs”.
NAT prevents an outside peer from initiating a call to insider peer
Solution:
Using Alice’s and Bob’s SNs, Relay is chosen
Each peer initiates session with relay.
Peers can now communicate through NATs via relay
Distributed Hash Table (DHT)
DHT: a distributed P2P database
database has (key, value) pairs; examples:
key: ss number; value: human name
key: movie title; value: IP address
Distribute the (key, value) pairs over the (millions of peers)
a peer queries DHT with key
DHT returns values that match the key
peers can also insert (key, value) pairs
Q: how to assign keys to peers?
central issue:
assigning (key, value) pairs to peers.
basic idea:
convert each key to an integer
Assign integer to each peer
put (key,value) pair in the peer that is closest to the key
DHT identifiers
assign integer identifier to each peer in range [0,2n-1] for some n.
each identifier represented by n bits.
require each key to be an integer in same range
to get integer key, hash original key
e.g., key = hash(“Led Zeppelin IV”)
this is why its is referred to as a distributed “hash” table
Assign keys to peers
rule: assign key to the peer that has the closest ID.
convention in lecture: closest is the immediate successor of the key.
e.g., n=4; peers: 1,3,4,5,8,10,12,14;
key = 13, then successor peer = 14
key = 15, then successor peer = 1
Circular DHT (1)
each peer only aware of immediate successor and predecessor.
“overlay network”
Circular DHT (1)
Circular DHT with shortcuts
each peer keeps track of IP addresses of predecessor, successor, short cuts.
reduced from 6 to 2 messages.
possible to design shortcuts so O(log N) neighbors, O(log N) messages in query
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
Socket programming
Socket API
introduced in BSD4.1 UNIX, 1981
explicitly created, used, released by apps
client/server paradigm
two types of transport service via socket API:
unreliable datagram
reliable, byte stream-oriented
Socket-programming using TCP
Socket: a door between application process and end-end-transport protocol (UCP
or TCP)
TCP service: reliable transfer of bytes from one process to another
Socket programming with TCP
Client must contact server
server process must first be running
server must have created socket (door) that welcomes client’s contact
Client contacts server by:
creating client-local TCP socket
specifying IP address, port number of server process
When client creates socket: client TCP establishes connection to server TCP
When contacted by client, server TCP creates new socket for server process to
communicate with client
allows server to talk with multiple clients
source port numbers used to distinguish clients (more in Chap 3)
Client/server socket interaction: TCP
A stream is a sequence of characters that flow into or out of a process.
An input stream is attached to some input source for the process, e.g.,
keyboard or socket.
An output stream is attached to an output source, e.g., monitor or socket.
Socket programming with TCP
Example client-server app:
1) client reads line from standard input (inFromUser stream) , sends to server
via socket (outToServer stream)
2) server reads line from socket
3) server converts line to uppercase, sends back to client
4) client reads, prints modified line
from socket (inFromServer stream)
Example: Java client (TCP)
Example: Java client (TCP), cont.
Example: Java server (TCP)
Example: Java server (TCP), cont
Chapter 2: Application layer
2.1 Principles of network applications
2.2 Web and HTTP
2.3 FTP
2.4 Electronic Mail
SMTP, POP3, IMAP
2.5 DNS
2.6 P2P applications
2.7 Socket programming with TCP
2.8 Socket programming with UDP
Socket programming with UDP
UDP: no “connection” between client and server
no handshaking
sender explicitly attaches IP address and port of destination to each packet
server must extract IP address, port of sender from received packet
UDP: transmitted data may be received out of order, or lost
Client/server socket interaction: UDP
Example: Java client (UDP)
Example: Java client (UDP)
Example: Java client (UDP), cont.
Example: Java server (UDP)
Example: Java server (UDP), cont
Chapter 2: Summary
application architectures
client-server
P2P
hybrid
application service requirements:
reliability, bandwidth, delay
Internet transport service model
connection-oriented, reliable: TCP
unreliable, datagrams: UDP
our study of network apps now complete!
Chapter 2: Summary
typical request/reply message exchange:
client requests info or service
server responds with data, status code
message formats:
headers: fields giving info about data
data: info being communicated
Most importantly: learned about protocols
Chapter
3: Transport Layer
Our goals:
understand principles behind transport layer services:
multiplexing/demultiplexing
reliable data transfer
flow control
congestion control
learn about transport layer protocols in the Internet:
UDP: connectionless transport
TCP: connection-oriented transport
TCP congestion control
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
Transport services and protocols
provide logical communication between app processes running on different hosts
transport protocols run in end systems
send side: breaks app messages into segments, passes to network layer
rcv side: reassembles segments into messages, passes to app layer
more than one transport protocol available to apps
Internet: TCP and UDP
Transport vs. network layer
network layer: logical communication between hosts
transport layer: logical communication between processes
relies on, enhances, network layer services
Household analogy:
12 kids sending letters to 12 kids
processes = kids
app messages = letters in envelopes
hosts = houses
transport protocol = Ann and Bill
network-layer protocol = postal service
Internet transport-layer protocols
reliable, in-order delivery (TCP)
congestion control
flow control
connection setup
unreliable, unordered delivery: UDP
no-frills extension of “best-effort” IP
services not available:
delay guarantees
bandwidth guarantees
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
Multiplexing/demultiplexing
How demultiplexing works
host receives IP datagrams
each datagram has source IP address, destination IP address
each datagram carries 1 transport-layer segment
each segment has source, destination port number
host uses IP addresses & port numbers to direct segment to appropriate
socket
Connectionless demultiplexing
Create sockets with port numbers:
DatagramSocket mySocket1 = new DatagramSocket(12534);
DatagramSocket mySocket2 = new DatagramSocket(12535);
UDP socket identified by two-tuple:
(dest IP address, dest port number)
When host receives UDP segment:
checks destination port number in segment
directs UDP segment to socket with that port number
IP datagrams with different source IP addresses and/or source port numbers
directed to same socket
Connectionless demux (cont)
DatagramSocket serverSocket = new DatagramSocket(6428);
Connection-oriented demux
TCP socket identified by 4-tuple:
source IP address
source port number
dest IP address
dest port number
recv host uses all four values to direct segment to appropriate socket
Server host may support many simultaneous TCP sockets:
each socket identified by its own 4-tuple
Web servers have different sockets for each connecting client
non-persistent HTTP will have different socket for each request
Connection-oriented demux (cont)
Connection-oriented demux: Threaded Web Server
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
UDP: User Datagram Protocol [RFC 768]
“no frills,” “bare bones” Internet transport protocol
“best effort” service, UDP segments may be:
lost
delivered out of order to app
connectionless:
no handshaking between UDP sender, receiver
each UDP segment handled independently of others
Why is there a UDP?
no connection establishment (which can add delay)
simple: no connection state at sender, receiver
small segment header
no congestion control: UDP can blast away as fast as desired
UDP: more
often used for streaming multimedia apps
loss tolerant
rate sensitive
other UDP uses
DNS
SNMP
reliable transfer over UDP: add reliability at application layer
application-specific error recovery!
UDP checksum
Sender:
treat segment contents as sequence of 16-bit integers
checksum: addition (1’s complement sum) of segment contents
sender puts checksum value into UDP checksum field
Receiver:
compute checksum of received segment
check if computed checksum equals checksum field value:
NO – error detected
YES – no error detected. But maybe errors nonetheless? More later ….
Internet Checksum Example
Note
When adding numbers, a carryout from the most significant bit needs to be added
to the result
Example: add two 16-bit integers
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
Principles of Reliable data transfer
important in app., transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine complexity of reliable
data transfer protocol (rdt)
Principles of Reliable data transfer
important in app., transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine complexity of reliable
data transfer protocol (rdt)
Principles of Reliable data transfer
important in app., transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine complexity of reliable
data transfer protocol (rdt)
Reliable data transfer: getting started
Reliable data transfer: getting started
We’ll:
incrementally develop sender, receiver sides of reliable data transfer protocol
(rdt)
consider only unidirectional data transfer
but control info will flow on both directions!
use finite state machines (FSM) to specify
sender, receiver
Rdt1.0: reliable transfer over a reliable channel
underlying channel perfectly reliable
no bit errors
no loss of packets
separate FSMs for sender, receiver:
sender sends data into underlying channel
receiver read data from underlying channel
Rdt2.0: channel with bit errors
underlying channel may flip bits in packet
checksum to detect bit errors
the question: how to recover from errors:
acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had
errors
sender retransmits pkt on receipt of NAK
new mechanisms in rdt2.0 (beyond rdt1.0):
error detection
receiver feedback: control msgs (ACK,NAK) rcvr->sender
rdt2.0: FSM specification
rdt2.0: operation with no errors
rdt2.0: error scenario
rdt2.0 has a fatal flaw!
What happens if ACK/NAK corrupted?
sender doesn’t know what happened at receiver!
can’t just retransmit: possible duplicate
Handling duplicates:
sender retransmits current pkt if ACK/NAK garbled
sender adds sequence number to each pkt
receiver discards (doesn’t deliver up) duplicate pkt
rdt2.1: sender, handles garbled ACK/NAKs
rdt2.1: receiver, handles garbled ACK/NAKs
rdt2.1: discussion
Sender:
seq # added to pkt
two seq. #’s (0,1) will suffice. Why?
must check if received ACK/NAK corrupted
twice as many states
state must “remember” whether “current” pkt has 0 or 1 seq. #
Receiver:
must check if received packet is duplicate
state indicates whether 0 or 1 is expected pkt seq #
note: receiver can not know if its last ACK/NAK received OK at sender
rdt2.2: a NAK-free protocol
same functionality as rdt2.1, using ACKs only
instead of NAK, receiver sends ACK for last pkt received OK
receiver must explicitly include seq # of pkt being ACKed
duplicate ACK at sender results in same action as NAK: retransmit current pkt
rdt2.2: sender, receiver fragments
rdt3.0: channels with errors and loss
New assumption: underlying channel can also lose packets (data or ACKs)
checksum, seq. #, ACKs, retransmissions will be of help, but not enough
Approach: sender waits “reasonable” amount of time for ACK
retransmits if no ACK received in this time
if pkt (or ACK) just delayed (not lost):
retransmission will be duplicate, but
use of seq. #’s already handles this
receiver must specify seq # of pkt being ACKed
requires countdown timer
rdt3.0 sender
Stop-and-wait protocol in action
Stop-and-Wait Protocol in action
Performance of Stop-and-Wait
rdt3.0 works, but performance stinks
ex: 1 Gbps link, 15 ms prop. delay, 8000 bit packet:
rdt3.0: stop-and-wait operation
Pipelined protocols
Pipelining: sender allows multiple, “in-flight”, yet-to-be-acknowledged pkts
range of sequence numbers must be increased
buffering at sender and/or receiver
Two generic forms of pipelined protocols: go-Back-N, selective repeat
Pipelining: increased utilization
Pipelining Protocols
Go-back-N: big picture:
Sender can have up to N unacked packets in pipeline
Rcvr only sends cumulative acks
Doesn’t ack packet if there’s a gap
Sender has timer for oldest unacked packet
If timer expires, retransmit all unacked packets
Selective Repeat: big pic
Sender can have up to N unacked packets in pipeline
Rcvr acks individual packets
Sender maintains timer for each unacked packet
When timer expires, retransmit only unack packet
Selective repeat: big picture
Sender can have up to N unacked packets in pipeline
Rcvr acks individual packets
Sender maintains timer for each unacked packet
When timer expires, retransmit only unack packet
Go-Back-N
Sender:
k-bit seq # in pkt header
“window” of up to N, consecutive unack’ed pkts allowed
GBN: sender extended FSM
GBN: receiver extended FSM
ACK-only: always send ACK for correctly-received pkt with highest in-order seq
#
may generate duplicate ACKs
need only remember expectedseqnum
out-of-order pkt:
discard (don’t buffer) -> no receiver buffering!
Re-ACK pkt with highest in-order seq #
GBN in
action
Selective Repeat
receiver individually acknowledges all correctly received pkts
buffers pkts, as needed, for eventual in-order delivery to upper layer
sender only resends pkts for which ACK not received
sender timer for each unACKed pkt
sender window
N consecutive seq #’s
again limits seq #s of sent, unACKed pkts
Selective repeat: sender, receiver windows
Selective repeat
data from above :
if next available seq # in window, send pkt
timeout(n):
resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N]:
mark pkt n as received
if n smallest unACKed pkt, advance window base to next unACKed seq #
Selective repeat in action
Selective repeat:
dilemma
Example:
seq #’s: 0, 1, 2, 3
window size=3
receiver sees no difference in two scenarios!
incorrectly passes duplicate data as new in (a)
Q: what relationship between seq # size and window size?
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
TCP: Overview RFCs: 793, 1122, 1323,
2018, 2581
full duplex data:
bi-directional data flow in same connection
MSS: maximum segment size
connection-oriented:
handshaking (exchange of control msgs) init’s sender, receiver state before
data exchange
flow controlled:
sender will not overwhelm receiver
point-to-point:
one sender, one receiver
reliable, in-order byte steam:
no “message boundaries”
pipelined:
TCP congestion and flow control set window size
send & receive buffers
TCP segment structure
TCP seq. #’s and ACKs
Seq. #’s:
byte stream “number” of first byte in segment’s data
ACKs:
seq # of next byte expected from other side
cumulative ACK
Q: how receiver handles out-of-order segments
A: TCP spec doesn’t say, – up to implementor
TCP Round Trip Time and Timeout
Q: how to set TCP timeout value?
longer than RTT
but RTT varies
too short: premature timeout
unnecessary retransmissions
too long: slow reaction to segment loss
Q: how to estimate RTT?
SampleRTT: measured time from segment transmission until ACK receipt
ignore retransmissions
SampleRTT will vary, want estimated RTT “smoother”
average several recent measurements, not just current SampleRTT
TCP Round Trip Time and Timeout
Example RTT estimation:
TCP Round Trip Time and Timeout
Setting the timeout
EstimtedRTT plus “safety margin”
large variation in EstimatedRTT -> larger safety margin
first estimate of how much SampleRTT deviates from EstimatedRTT:
Karn’s Algorithm
Issue: What about ACKs for those segments which have been transmitted more than
once?
Solution: ignore retransmitted packets when updating the RTT estimate to avoid
the retransmission ambiguity problem
RTT estimate is only based on those segments transmitted once
Use the backoff-based RTO upon each timeout: double the RTO value upon each
timeout
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
TCP reliable data transfer
TCP creates rdt service on top of IP’s unreliable service
Pipelined segments
Cumulative acks
TCP uses single retransmission timer
Retransmissions are triggered by:
timeout events
duplicate acks
Initially consider simplified TCP sender:
ignore duplicate acks
ignore flow control, congestion control
TCP sender events:
data rcvd from app:
Create segment with seq #
seq # is byte-stream number of first data byte in segment
start timer if not already running (think of timer as for oldest unacked
segment)
expiration interval: TimeOutInterval
timeout:
retransmit segment that caused timeout
restart timer
Ack rcvd:
If acknowledges previously unacked segments
update what is known to be acked
start timer if there are outstanding
segments
TCP
sender
(simplified)
TCP: retransmission scenarios
TCP retransmission scenarios (more)
TCP ACK generation [RFC 1122, RFC 2581]
Fast Retransmit
Time-out period often relatively long:
long delay before resending lost packet
Detect lost segments via duplicate ACKs.
Sender often sends many segments back-to-back
If segment is lost, there will likely be many duplicate ACKs.
If sender receives 3 ACKs for the same data, it supposes that segment after
ACKed data was lost:
fast retransmit: resend segment before timer expires
Fast retransmit algorithm:
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
TCP Flow Control
receive side of TCP connection has a receive buffer:
speed-matching service: matching the send rate to the receiving app’s drain
rate
TCP Flow control: how it works
(Suppose TCP receiver discards out-of-order segments)
spare room in buffer
= RcvWindow
= RcvBuffer-[LastByteRcvd – LastByteRead]
Rcvr advertises spare room by including value of RcvWindow in segments
Sender limits unACKed data to RcvWindow
guarantees receive buffer doesn’t overflow
Chapter 3 outline
3.1 Transport-layer services
3.2 Multiplexing and demultiplexing
3.3 Connectionless transport: UDP
3.4 Principles of reliable data transfer
3.5 Connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 Principles of congestion control
3.7 TCP congestion control
TCP Connection Management
Recall: TCP sender, receiver establish “connection” before exchanging data
segments
initialize TCP variables:
seq. #s
buffers, flow control info (e.g. RcvWindow)
client: connection initiator
Socket clientSocket = new Socket(“hostname”,”port
number”);
server: contacted by client
Socket connectionSocket =
welcomeSocket.accept();
Three way handshake:
Step 1: client host sends TCP SYN segment to server
specifies initial seq #
no data
Step 2: server host receives SYN, replies with SYNACK segment
server allocates buffers
specifies server initial seq. #
Step 3: client receives SYNACK, replies with ACK segment, which may contain
data
TCP Connection Management (cont.)
Closing a connection:
client closes socket: clientSocket.close();
Step 1: client end system sends TCP FIN control segment to server
Step 2: server receives FIN, replies with ACK. Closes connection, sends FIN.
TCP Connection Management (cont.)
Step 3: client receives FIN, replies with ACK.
Enters “timed wait” – will respond with ACK to received FINs
Step 4: server, receives ACK. Connection
closed.
Note: with small modification, can handle simultaneous FINs.
TCP Connection Management (cont)
Principles of congestion control
congestion:
informally: “too many sources sending too much data too fast for network to
handle”
different from flow control!
manifestations:
lost packets (buffer overflow at routers)
long delays (queueing in router buffers)
a top-10 problem!
Causes/costs of congestion: scenario 1
two senders, two receivers
one router, infinite buffers
output link capacity: R
no retransmission
maximum per-connection throughput: R/2
Causes/costs of congestion: scenario 2
one router, finite buffers
sender retransmission of timed-out packet
application-layer input = application-layer output: λin = λout
transport-layer input includes retransmissions : λin λin
Causes/costs of congestion: scenario 2
idealization: perfect knowledge
sender sends only when router buffers available
Causes/costs of congestion: scenario 2
Idealization: known loss packets can be lost, dropped at router due to full buffers
sender only resends if packet known to be lost
Causes/costs of congestion: scenario 2
Idealization: known loss packets can be lost, dropped at router due to full buffers
sender only resends if packet known to be lost
Causes/costs of congestion: scenario 2
Causes/costs of congestion: scenario 2
Causes/costs of congestion: scenario 3
four senders
multihop paths
timeout/retransmit
Causes/costs of congestion: scenario 3
Approaches towards congestion control
end-end congestion control:
no explicit feedback from network
congestion inferred from end-system observed loss, delay
approach taken by TCP
network-assisted congestion control:
routers provide feedback to end systems
single bit indicating congestion (SNA, DECbit, TCP/IP ECN, ATM)
explicit rate for sender to send at
Case study: ATM ABR congestion control
ABR: available bit rate:
“elastic service”
if sender’s path “underloaded”:
sender should use available bandwidth
if sender’s path congested:
sender throttled to minimum guaranteed rate
RM (resource management) cells:
sent by sender, interspersed with data cells
bits in RM cell set by switches (“network-assisted”)
NI bit: no increase in rate (mild congestion)
CI bit: congestion indication
RM cells returned to sender by receiver, with bits intact
Case study: ATM ABR congestion control
two-byte ER (explicit rate) field in RM cell
congested switch may lower ER value in cell
senders’ send rate thus max supportable rate on path
EFCI bit in data cells: set to 1 in congested switch
if data cell preceding RM cell has EFCI set, receiver sets CI bit in returned
RM cell
Chapter 3 outline
3.1 transport-layer services
3.2 multiplexing and demultiplexing
3.3 connectionless transport: UDP
3.4 principles of reliable data transfer
3.5 connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
3.6 principles of congestion control
3.7 TCP congestion control
AIMD Rule: additive increase, multiplicative decrease
Why AIMD? TCP Fairness
fairness goal: if K TCP sessions share same bottleneck link of bandwidth R,
each should have average rate of R/K
Why is AIMD fair?
two competing sessions:
additive increase gives slope of 1, as throughout increases
multiplicative decrease decreases throughput proportionally
TCP Slow Start
When connection begins, cwnd 2 MSS, typically,
set cwnd = 1MSS
Example: MSS = 500 bytes & RTT = 200 msec
initial rate = 20 kbps
available bandwidth may be >> MSS/RTT
desirable to quickly ramp up to respectable rate
TCP Slow Start (more)
When connection begins, increase rate exponentially when cwnd<ssthresh
double cwnd every RTT by setting
cwnd += 1 MSS for every ACK received
Summary: initial rate is slow but ramps up exponentially fast
Congestion Avoidance
increase cwnd by 1 MSS per RTT until congestion (loss) is detected
Conditoins: when cwnd > ssthresh and no loss occurs
Actions: cwnd += (MSS/cwnd)*MSS (bytes)
upon every incoming non-duplicate ACK
When loss occurs
Detecting losses and reacting to them:
through duplicate ACKs
fast retransmit / fast recovery
multiplicative decrease cwnd upon loss
through retransmission timeout
reset everything
Fast Retransmit/Fast Recovery
fast retransmit: to detect and repair loss,
based on incoming duplicate ACKs
use 3 duplicate ACKs to infer packet loss
set ssthresh = cwnd/2
cwnd = ssthresh + 3MSS
retransmit the lost packet
fast recovery: governs the transmission of new data until a non-duplicate ACK
arrives
increase cwnd by 1 MSS upon every duplicate ACK
Fast Retransmit/Fast Recovery
upon 3rd duplicate ACK
ssthresh = max (cwnd/2, 2*MSS)
cwnd should be flight size to be more accurate
cwnd = ssthresh + 3*MSS
why add 3 packets here?
retransmit the lost TCP packet
upon each additional duplicate ACK
cwnd += 1 MSS
transmit a new packet if allowed by the updated cwnd and rwnd
upon a new (i.e., non-duplicate) ACK
cwnd = ssthresh
deflating the congestion window size
Retransmission Timeout
when retransmission timer expires
ssthresh = max ( cwnd/2, 2*MSS)
cwnd should be flight size to be more accurate
see RFC 2581
cwnd = 1 MSS
retransmit the lost TCP packet
why resetting?
heavy loss detected
Putting Things Together in TCP
use selective repeat to do reliable data transfer for a window of packets win
at any time
update win = min (cwnd, rwnd)
cwnd is updated by TCP congestion control
rwnd is updated by TCP flow control
TCP throughput
avg. TCP thruput as function of window size, RTT?
ignore slow start, assume always data to send
W: window size (measured in bytes) where loss occurs
avg. window size (# in-flight bytes) is ¾ W
avg. thruput is 3/4W per RTT
TCP Futures: TCP over “long, fat pipes”
example: 1500 byte segments, 100ms RTT, want 10 Gbps throughput
requires W = 83,333 in-flight segments
throughput in terms of segment loss probability, L [Mathis 1997]:
➜ to achieve 10 Gbps throughput, need a
loss rate of L = 2·10-10 – a very small
loss rate!
new versions of TCP for high-speed
Chapter 3: summary
principles behind transport layer services:
multiplexing, demultiplexing
reliable data transfer
flow control
congestion control
instantiation, implementation in the Internet
UDP
TCP
next:
leaving the network “edge” (application, transport layers)
into the network “core”
Chapter 4: network layer
chapter goals:
understand principles behind network layer services:
network layer service models
forwarding versus routing
how a router works
routing (path selection)
broadcast, multicast
instantiation, implementation in the Internet
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Network layer
transport segment from sending to receiving host
on sending side encapsulates segments into datagrams
on receiving side, delivers segments to transport layer
network layer protocols in every host, router
router examines header fields in all IP datagrams passing through it
Two key network-layer functions
forwarding: move packets from router’s input to appropriate router output
routing: determine route taken by packets from source to dest.
routing algorithms
Connection setup
3rd important function in some network architectures:
ATM, frame relay, X.25
before datagrams flow, two end hosts and intervening routers establish virtual
connection
routers get involved
network vs transport layer connection service:
network: between two hosts (may also involve intervening routers in case of
VCs)
transport: between two processes
Network service model
example services for individual datagrams:
guaranteed delivery
guaranteed delivery with less than 40 msec delay
example services for a flow of datagrams:
in-order datagram delivery
guaranteed minimum bandwidth to flow
restrictions on changes in inter-packet spacing
Network layer service models:
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Connection, connection-less service
datagram network provides network-layer connectionless service
virtual-circuit network provides network-layer connection service
analogous to TCP/UDP connecton-oriented / connectionless transport-layer
services, but:
service: host-to-host
no choice: network provides one or the other
implementation: in network core
Virtual circuits
call setup, teardown for each call before data can flow
each packet carries VC identifier (not destination host address)
every router on source-dest path maintains “state” for each passing connection
link, router resources (bandwidth, buffers) may be allocated to VC (dedicated
resources = predictable service)
“source-to-dest path behaves much like telephone circuit”
performance-wise
network actions along source-to-dest path
VC implementation
a VC consists of:
path from source to destination
VC numbers, one number for each link along path
entries in forwarding tables in routers along path
packet belonging to VC carries VC number (rather than dest address)
VC number can be changed on each link.
new VC number comes from forwarding table
VC forwarding table
Virtual circuits: signaling protocols
used to setup, maintain teardown VC
used in ATM, frame-relay, X.25
not used in today’s Internet
Datagram networks
no call setup at network layer
routers: no state about end-to-end connections
no network-level concept of “connection”
packets forwarded using destination host address
Datagram forwarding table
Datagram forwarding table
Longest prefix matching
Datagram or VC network: why?
Internet (datagram)
data exchange among computers
“elastic” service, no strict timing req.
many link types
different characteristics
uniform service difficult
“smart” end systems (computers)
can adapt, perform control, error recovery
simple inside network, complexity at “edge”
ATM (VC)
evolved from telephony
human conversation:
strict timing, reliability requirements
need for guaranteed service
“dumb” end systems
telephones
complexity inside network
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Router architecture overview
two key router functions:
run routing algorithms/protocol (RIP, OSPF, BGP)
forwarding datagrams from incoming to outgoing link
Input port functions
decentralized switching:
given datagram dest., lookup output port using forwarding table in input port
memory (“match plus action”)
goal: complete input port processing at ‘line speed’
queuing: if datagrams arrive faster than forwarding rate into switch fabric
Switching fabrics
transfer packet from input buffer to appropriate output buffer
switching rate: rate at which packets can be transfer from inputs to outputs
often measured as multiple of input/output line rate
N inputs: switching rate N times line rate desirable
three types of switching fabrics
Switching via memory
first generation routers:
traditional computers with switching under direct control of CPU
packet copied to system’s memory
speed limited by memory bandwidth (2 bus
crossings per datagram)
Switching via a bus
datagram from input port memory
to output port memory via a shared
bus
bus contention: switching speed limited
by bus bandwidth
32 Gbps bus, Cisco 5600: sufficient speed for access and enterprise routers
Switching via interconnection network
overcome bus bandwidth limitations
banyan networks, crossbar, other interconnection nets initially developed to
connect processors in multiprocessor
advanced design: fragmenting datagram into fixed length cells, switch cells
through the fabric.
Cisco 12000: switches 60 Gbps through the interconnection network
Output ports
buffering required when datagrams arrive from fabric faster than the
transmission rate
scheduling discipline chooses among queued datagrams for transmission
Output port queueing
buffering when arrival rate via switch exceeds output line speed
queueing (delay) and loss due to output port buffer overflow!
Input port queuing
fabric slower than input ports combined -> queueing may occur at input
queues
queueing delay and loss due to input buffer overflow!
Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents
others in queue from moving forward
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
The Internet network layer
host, router network layer functions:
IP datagram format
IP fragmentation, reassembly
network links have MTU (max.transfer size) – largest possible link-level frame
different link types, different MTUs
large IP datagram divided (“fragmented”) within net
one datagram becomes several datagrams
“reassembled” only at final destination
IP header bits used to identify, order related fragments
IP fragmentation, reassembly
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
IP addressing: introduction
IP address: 32-bit identifier for host, router interface
interface: connection between host/router and physical link
router’s typically have multiple interfaces
host typically has one or two interfaces (e.g., wired Ethernet, wireless
802.11)
IP addresses associated with each interface
IP addressing: introduction
Q: how are interfaces actually connected?
A: we’ll learn about that in chapter 5, 6.
Subnets
IP address:
subnet part – high order bits
host part – low order bits
what’s a subnet ?
device interfaces with same subnet part of IP address
can physically reach each other without intervening router
Subnets
recipe
to determine the subnets, detach each interface from its host or router,
creating islands of isolated networks
each isolated network is called a subnet
Subnets
how many?
IP addressing: CIDR
CIDR: Classless InterDomain Routing
subnet portion of address of arbitrary length
address format: a.b.c.d/x, where x is # bits in subnet portion of address
IP addresses: how to get one?
Q: How does a host get IP address?
hard-coded by system admin in a file
Windows: control-panel->network->configuration->tcp/ip->properties
UNIX: /etc/rc.config
DHCP: Dynamic Host Configuration Protocol: dynamically get address from as
server
“plug-and-play”
DHCP: Dynamic Host Configuration Protocol
goal: allow host to dynamically obtain its IP address from network server when
it joins network
can renew its lease on address in use
allows reuse of addresses (only hold address while connected/“on”)
support for mobile users who want to join network (more shortly)
DHCP overview:
host broadcasts “DHCP discover” msg [optional]
DHCP server responds with “DHCP offer” msg [optional]
host requests IP address: “DHCP request” msg
DHCP server sends address: “DHCP ack” msg
DHCP client-server scenario
DHCP client-server scenario
DHCP: more than IP addresses
DHCP can return more than just allocated IP address on subnet:
address of first-hop router for client
name and IP address of DNS sever
network mask (indicating network versus host portion of address)
DHCP: example
connecting laptop needs its IP address, addr of first-hop router, addr of DNS
server: use DHCP
DHCP: example
DCP server formulates DHCP ACK containing client’s IP address, IP address of
first-hop router for client, name & IP address of DNS server
IP addresses: how to get one?
Q: how does network get subnet part of IP addr?
A: gets allocated portion of its provider ISP’s address space
Hierarchical addressing: route aggregation
Hierarchical addressing: more specific routes
IP addressing: the last word…
Q: how does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers
http://www.icann.org/
allocates addresses
manages DNS
assigns domain names, resolves disputes
NAT: network address translation
NAT: network address translation
motivation: local network uses just one IP address as far as outside world is
concerned:
range of addresses not needed from ISP:
just one IP address for all devices
can change addresses of devices in local network without notifying outside
world
can change ISP without changing addresses of devices in local network
devices inside local net not explicitly addressable, visible by outside world
(a security plus)
Dedicated Space for Carrier-Grade NAT (RFC6598)
100.64.0.0/10, used for carrier-grade NAT only
About 4 million addresses
Used for internal operations of carrier networks
Should NOT be used in private networks or public Internet
Private IP Address Spaces
IPv4 (RFC1918):
24-bit block: 10.0.0.0 ~ 10.255.255.255 (10.0.0.0/8)
16,777,216 addresses
20-bit block: 172.16.0.0~172.31.255.255 (172.16.0.0/12)
1,048,576 addresses
16-bit block: 192.168.0.0~192.168.255.255 (192.168.0.0/16)
65,536 addresses
IPv6 (RFC4193): fc00::/7
NAT: network address translation
implementation: NAT router must:
outgoing datagrams: replace (source IP address, port #) of every outgoing
datagram to (NAT IP address, new port #)
. . . remote clients/servers will respond using (NAT IP address, new port #) as
destination addr
remember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation
pair
incoming datagrams: replace (NAT IP address, new port #) in dest fields of
every incoming datagram with corresponding (source IP address, port #) stored
in NAT table
NAT: network address translation
NAT: network address translation
16-bit port-number field:
60,000 simultaneous connections with a single LAN-side address!
NAT is controversial:
routers should only process up to layer 3
violates end-to-end argument
NAT possibility must be taken into account by app designers, e.g., P2P
applications
address shortage should instead be solved by IPv6
NAT traversal problem
client wants to connect to server with address 10.0.0.1
server address 10.0.0.1 local to LAN (client can’t use it as destination addr)
only one externally visible NATed address: 138.76.29.7
solution1: statically configure NAT to forward incoming connection requests at
given port to server
e.g., (123.76.29.7, port 2500) always forwarded to 10.0.0.1 port 25000
NAT traversal problem
solution 2: Universal Plug and Play (UPnP) Internet Gateway Device (IGD)
Protocol. Allows NATed host to:
learn public IP address (138.76.29.7)
add/remove port mappings (with lease times)
i.e., automate static NAT port map configuration
NAT traversal problem
solution 3: relaying (used in Skype)
NATed client establishes connection to relay
external client connects to relay
relay bridges packets between to connections
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
ICMP: internet control message protocol
used by hosts & routers to communicate network-level information
error reporting: unreachable host, network, port, protocol
echo request/reply (used by ping)
network-layer “above” IP:
ICMP msgs carried in IP datagrams
ICMP message: type, code plus the header and first 8 bytes of IP datagram causing
error
Traceroute and ICMP
source sends series of UDP segments to dest
first set has TTL =1
second set has TTL=2, etc.
unlikely port number
when nth set of datagrams arrives to nth
router:
router discards datagrams
and sends source ICMP messages (type 11, code 0)
ICMP messages includes name of router & IP address
when ICMP messages arrives, source records RTTs
IPv6: motivation
initial motivation: 32-bit address space soon to be completely allocated.
additional motivation:
header format helps speed processing/forwarding
header changes to facilitate QoS
IPv6 datagram format:
fixed-length 40 byte header
no fragmentation allowed
IPv6 datagram format
IPv4 & IPv6 Header Comparison
Other changes from IPv4
checksum: removed entirely to reduce processing time at each hop
options: allowed, but outside of header, indicated by “Next Header” field
ICMPv6: new version of ICMP
additional message types, e.g. “Packet Too Big”
multicast group management functions
Transition from IPv4 to IPv6
not all routers can be upgraded simultaneously
no “flag days”
how will network operate with mixed IPv4 and IPv6 routers?
tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers
Tunneling
Tunneling
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Interplay between routing, forwarding
Graph abstraction
Graph abstraction: costs
Routing algorithm classification
Q: global or decentralized information?
global:
all routers have complete topology, link cost info
“link state” algorithms
decentralized:
router knows physically-connected neighbors, link costs to neighbors
iterative process of computation, exchange of info with neighbors
“distance vector” algorithms
Q: static or dynamic?
static:
routes change slowly over time
dynamic:
routes change more quickly
periodic update
in response to link cost changes
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
A Link-State Routing Algorithm
Dijkstra’s algorithm
net topology, link costs known to all nodes
accomplished via “link state broadcast”
all nodes have same info
computes least cost paths from one node (‘source”) to all other nodes
gives forwarding table for that node
iterative: after k iterations, know least cost path to k dest.’s
notation:
c(x,y): link cost from node x to y; = ∞
if not direct neighbors
D(v): current value of cost of path from source to dest. v
p(v): predecessor node along path from source to v
N’: set of nodes whose least cost path definitively known
Dijsktra’s Algorithm
Dijkstra’s algorithm: another example
Dijkstra’s algorithm: example (2)
Dijkstra’s algorithm, discussion
algorithm complexity: n nodes
each iteration: need to check all nodes, w, not in N
n(n+1)/2 comparisons: O(n2)
more efficient implementations possible: O(nlogn)
oscillations possible:
e.g., support link cost equals amount of carried traffic:
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Distance vector algorithm
Bellman-Ford equation (dynamic programming)
let
dx(y) := cost of least-cost path from
x to y
then
dx(y) = min {c(x,v) + dv(y) }
Bellman-Ford example
Distance vector algorithm
Dx(y) = estimate of least cost from x to y
x maintains distance vector Dx = [Dx(y):
y є N ]
node x:
knows cost to each neighbor v: c(x,v)
maintains its neighbors’ distance vectors. For each neighbor v, x maintains
Dv = [Dv(y): y є N
]
Distance vector algorithm
key idea:
from time-to-time, each node sends its own distance vector estimate to
neighbors
when x receives new DV estimate from neighbor, it updates its own DV using B-F
equation:
Distance vector algorithm
iterative, asynchronous: each local iteration caused by:
local link cost change
DV update message from neighbor
distributed:
each node notifies neighbors only when its DV changes
neighbors then notify their neighbors if necessary
Distance vector: link cost changes
Distance vector: link cost changes
Comparison of LS and DV algorithms
message complexity
LS: with n nodes, E links, O(nE) msgs sent
DV: exchange between neighbors only
convergence time varies
speed of convergence
LS: O(n2) algorithm requires O(nE) msgs
may have oscillations
DV: convergence time varies
may be routing loops
count-to-infinity problem
robustness: what happens if router malfunctions?
LS:
node can advertise incorrect link cost
each node computes only its own table
DV:
DV node can advertise incorrect path cost
each node’s table used by others
error propagate thru network
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Hierarchical routing
scale: with 600 million destinations:
can’t store all dest’s in routing tables!
routing table exchange would swamp links!
administrative autonomy
internet = network of networks
each network admin may want to control routing in its own network
Hierarchical routing
aggregate routers into regions, “autonomous systems” (AS)
routers in same AS run same routing protocol
“intra-AS” routing protocol
routers in different AS can run different intra-AS routing protocol
gateway router:
at “edge” of its own AS
has link to router in another AS
Interconnected ASes
forwarding table configured by both
intra- and inter-AS routing algorithm
intra-AS sets entries for internal dests
inter-AS & intra-AS sets entries for external dests
Inter-AS tasks
suppose router in AS1 receives datagram destined outside of AS1:
router should forward packet to gateway router, but which one?
AS1 must:
learn which dests are reachable through AS2, which through AS3
propagate this reachability info to all routers in AS1
job of inter-AS routing!
Example: setting forwarding table in router 1d
suppose AS1 learns (via inter-AS protocol) that subnet x reachable via AS3
(gateway 1c), but not via AS2
inter-AS protocol propagates reachability info to all internal routers
router 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c
installs forwarding table entry (x,I)
Example: choosing among multiple ASes
now suppose AS1 learns from inter-AS protocol that subnet x is reachable from
AS3 and from AS2.
to configure forwarding table, router 1d must determine which gateway it should
forward packets towards for dest x
this is also job of inter-AS routing protocol!
Example: choosing among multiple ASes
now suppose AS1 learns from inter-AS protocol that subnet x is reachable from
AS3 and from AS2.
to configure forwarding table, router 1d must determine towards which gateway it
should forward packets for dest x
this is also job of inter-AS routing protocol!
hot potato routing: send packet towards closest of two routers.
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Intra-AS Routing
also known as interior gateway protocols (IGP)
most common intra-AS routing protocols:
RIP: Routing Information Protocol
OSPF: Open Shortest Path First
IGRP: Interior Gateway Routing Protocol (Cisco proprietary)
RIP ( Routing Information Protocol)
included in BSD-UNIX distribution in 1982
distance vector algorithm
distance metric: # hops (max = 15 hops), each link has cost 1
DVs exchanged with neighbors every 30 sec in response message (aka
advertisement)
each advertisement: list of up to 25 destination subnets (in IP addressing
sense)
RIP: example
RIP: example
RIP: link failure, recovery
if no advertisement heard after 180 sec –> neighbor/link declared dead
routes via neighbor invalidated
new advertisements sent to neighbors
neighbors in turn send out new advertisements (if tables changed)
link failure info quickly (?) propagates to entire net
poison reverse used to prevent ping-pong loops (infinite distance = 16 hops)
RIP table processing
RIP routing tables managed by application-level process called route-d (daemon)
advertisements sent in UDP packets, periodically repeated
OSPF (Open Shortest Path First)
“open”: publicly available
uses link state algorithm
LS packet dissemination
topology map at each node
route computation using Dijkstra’s algorithm
OSPF advertisement carries one entry per neighbor
advertisements flooded to entire AS
carried in OSPF messages directly over IP (rather than TCP or UDP
IS-IS routing protocol: nearly identical to OSPF
OSPF “advanced” features (not in RIP)
security: all OSPF messages authenticated (to prevent malicious intrusion)
multiple same-cost paths allowed (only one path in RIP)
for each link, multiple cost metrics for different TOS (e.g., satellite link
cost set “low” for best effort ToS; high for real time ToS)
integrated uni- and multicast support:
Multicast OSPF (MOSPF) uses same topology data base as OSPF
hierarchical OSPF in large domains.
Hierarchical OSPF
Hierarchical OSPF
two-level hierarchy: local area, backbone.
link-state advertisements only in area
each nodes has detailed area topology; only know direction (shortest path) to
nets in other areas.
area border routers: “summarize” distances
to nets in own area, advertise to other Area Border routers.
backbone routers: run OSPF routing limited to backbone.
boundary routers: connect to other AS’s.
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): the de facto inter-domain routing protocol
“glue that holds the Internet together”
BGP provides each AS a means to:
eBGP: obtain subnet reachability information from neighboring ASs.
iBGP: propagate reachability information to all AS-internal routers.
determine “good” routes to other networks based on reachability information and
policy.
allows subnet to advertise its existence to rest of Internet: “I am here”
BGP basics
when AS3 advertises a prefix to AS1:
AS3 promises it will forward datagrams towards that prefix
AS3 can aggregate prefixes in its advertisement
BGP basics: distributing path information
using eBGP session between 3a and 1c, AS3 sends prefix reachability info to
AS1.
1c can then use iBGP to distribute new prefix info to all routers in AS1
1b can then re-advertise new reachability info to AS2 over 1b-to-2a eBGP
session
when router learns of new prefix, it creates entry for prefix in its forwarding
table.
Path attributes and BGP routes
advertised prefix includes BGP attributes
prefix + attributes = “route”
two important attributes:
AS-PATH: contains ASs through which prefix advertisement has passed: e.g., AS
67, AS 17
NEXT-HOP: indicates specific internal-AS router to next-hop AS. (may be
multiple links from current AS to next-hop-AS)
gateway router receiving route advertisement uses import policy to
accept/decline
e.g., never route through AS x
policy-based routing
BGP route selection
router may learn about more than 1 route to destination AS, selects route based
on:
local preference value attribute: policy decision
shortest AS-PATH
closest NEXT-HOP router: hot potato routing
additional criteria
BGP messages
BGP messages exchanged between peers over TCP connection
BGP messages:
OPEN: opens TCP connection to peer and authenticates sender
UPDATE: advertises new path (or withdraws old)
KEEPALIVE: keeps connection alive in absence of UPDATES; also ACKs OPEN request
NOTIFICATION: reports errors in previous msg; also used to close connection
BGP routing policy
BGP routing policy (2)
Why different Intra-, Inter-AS routing ?
policy:
inter-AS: admin wants control over how its traffic routed, who routes through
its net.
intra-AS: single admin, so no policy decisions needed
scale:
hierarchical routing saves table size, reduced update traffic
performance:
intra-AS: can focus on performance
inter-AS: policy may dominate over performance
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format
IPv4 addressing
ICMP
IPv6
4.5 routing algorithms
link state
distance vector
hierarchical routing
4.6 routing in the Internet
RIP
OSPF
BGP
4.7 broadcast and multicast routing
Broadcast routing
deliver packets from source to all other nodes
source duplication is inefficient:
In-network duplication
flooding: when node receives broadcast packet, sends copy to all neighbors
problems: cycles & broadcast storm
controlled flooding: node only broadcasts pkt if it hasn’t broadcast same
packet before
node keeps track of packet ids already broadacsted
or reverse path forwarding (RPF): only forward packet if it arrived on shortest
path between node and source
spanning tree:
no redundant packets received by any node
Spanning tree
first construct a spanning tree
nodes then forward/make copies only along spanning tree
Spanning tree: creation
center node
each node sends unicast join message to center node
message forwarded until it arrives at a node already belonging to spanning tree
Multicast routing: problem statement
goal: find a tree (or trees) connecting routers having local mcast group
members
tree: not all paths between routers used
shared-tree: same tree used by all group members
Approaches for building mcast trees
approaches:
source-based tree: one tree per source
shortest path trees
reverse path forwarding
group-shared tree: group uses one tree
minimal spanning (Steiner)
center-based trees
Shortest path tree
mcast forwarding tree: tree of shortest path routes from source to all receivers
Dijkstra’s algorithm
Reverse path forwarding
if (mcast datagram received on incoming link on shortest path back to center)
then flood datagram onto all outgoing
links
else ignore datagram
Reverse path forwarding: example
Reverse path forwarding: pruning
forwarding tree contains subtrees with no mcast group members
no need to forward datagrams down subtree
“prune” msgs sent upstream by router with no downstream group members
Center-based trees
single delivery tree shared by all
one router identified as “center” of tree
to join:
edge router sends unicast join-msg addressed to center router
join-msg “processed” by intermediate routers and forwarded towards center
join-msg either hits existing tree branch for this center, or arrives at center
path taken by join-msg becomes new branch of tree for this router
Center-based trees: example
Internet Multicasting Routing: DVMRP
DVMRP: distance vector multicast routing protocol, RFC1075
flood and prune: reverse path
forwarding, source-based tree
RPF tree based on DVMRP’s own routing tables constructed by communicating DVMRP
routers
no assumptions about underlying unicast
initial datagram to mcast group flooded
everywhere via RPF
routers not wanting group: send upstream prune msgs
DVMRP: continued…
soft state: DVMRP router periodically (1 min.) “forgets” branches are pruned:
mcast data again flows down unpruned branch
downstream router: reprune or else continue to receive data
routers can quickly regraft to tree
following IGMP join at leaf
odds and ends
commonly implemented in commercial router
Tunneling
Q: how to connect “islands” of multicast
routers in a “sea” of unicast routers?
PIM: Protocol Independent Multicast
not dependent on any specific underlying unicast routing algorithm (works with
all)
two different multicast distribution scenarios :
Consequences of sparse-dense dichotomy:
dense
group membership by routers assumed until routers explicitly prune
data-driven construction on mcast tree (e.g., RPF)
bandwidth and non-group-router processing profligate
sparse:
no membership until routers explicitly join
receiver- driven construction of mcast tree (e.g., center-based)
bandwidth and non-group-router processing conservative
PIM- dense mode
PIM – sparse mode
center-based approach
router sends join msg to rendezvous point (RP)
intermediate routers update state and forward join
after joining via RP, router can switch to source-specific tree
increased performance: less concentration, shorter paths
PIM – sparse mode
sender(s):
unicast data to RP, which distributes down RP-rooted tree
RP can extend mcast tree upstream to source
RP can send stop msg if no attached receivers
“no one is listening!”
4.1 introduction
4.2 virtual circuit and datagram networks
4.3 what’s inside a router
4.4 IP: Internet Protocol
datagram format, IPv4 addressing, ICMP, IPv6
4.5 routing algorithms
link state, distance vector, hierarchical routing
4.6 routing in the Internet
RIP, OSPF, BGP
4.7 broadcast and multicast routing
Chapter 5: Link layer
goals:
understand principles behind link layer services:
error detection, correction
sharing a broadcast channel: multiple access
link layer addressing
local area networks: Ethernet, VLANs
instantiation, implementation of various link layer technologies
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
Link layer: introduction
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
Link layer services
framing, link access:
encapsulate datagram into frame, adding header, trailer
channel access if shared medium
“MAC” addresses used in frame headers to identify source, dest
different from IP address!
reliable delivery between adjacent nodes
we learned how to do this already (chapter 3)!
seldom used on low bit-error link (fiber, some twisted pair)
wireless links: high error rates
Q: why both link-level and end-end reliability?
Link layer services (more)
flow control:
pacing between adjacent sending and receiving nodes
error detection:
errors caused by signal attenuation, noise.
receiver detects presence of errors:
signals sender for retransmission or drops frame
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
Adaptors communicating
sending side:
encapsulates datagram in frame
adds error checking bits, rdt, flow control, etc.
receiving side
looks for errors, rdt, flow control, etc
extracts datagram, passes to upper layer at receiving side
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
Error detection
Cyclic redundancy check
more powerful error-detection coding
view data bits, D, as a binary number
choose r+1 bit pattern (generator), G
goal: choose r CRC bits, R, such that
<D,R> exactly divisible by G (modulo 2)
receiver knows G, divides <D,R> by G. If non-zero remainder: error detected!
can detect all burst errors less than r+1 bits
widely used in practice (Ethernet, 802.11 WiFi, ATM)
CRC example
want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by G, want remainder R to satisfy:
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
Multiple access links, protocols
two types of “links”:
point-to-point
PPP for dial-up access
point-to-point link between Ethernet switch, host
broadcast (shared wire or medium)
old-fashioned Ethernet
upstream HFC
802.11 wireless LAN
Multiple access protocols
single shared broadcast channel
two or more simultaneous transmissions by nodes: interference
collision if node receives two or more signals at the same time
multiple access protocol (MAC)
distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit
communication about channel sharing must use channel itself!
no out-of-band channel for coordination
MAC protocols: taxonomy
three broad classes:
channel partitioning
divide channel into smaller “pieces” (time slots, frequency, code)
allocate piece to node for exclusive use
random access
channel not divided, allow collisions
“recover” from collisions
“taking turns”
nodes take turns, but nodes with more to send can take longer turns
Channel partitioning MAC protocols: TDMA
TDMA: time division multiple access
access to channel in “rounds”
each station gets fixed length slot (length = pkt trans time) in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6 idle
Channel partitioning MAC protocols: FDMA
FDMA: frequency division multiple access
channel spectrum divided into frequency bands
each station assigned fixed frequency band
unused transmission time in frequency bands go idle
example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle
Random access protocols
when node has packet to send
transmit at full channel data rate R.
no a priori coordination among nodes
two or more transmitting nodes ➜ “collision”,
random access MAC protocol specifies:
how to detect collisions
how to recover from collisions (e.g., via delayed retransmissions)
examples of random access MAC protocols:
slotted ALOHA
ALOHA
CSMA, CSMA/CD, CSMA/CA
Slotted ALOHA
assumptions:
all frames same size
time divided into equal size slots (time to transmit 1 frame)
nodes start to transmit only slot beginning
nodes are synchronized
if 2 or more nodes transmit in slot, all nodes detect collision
operation:
when node obtains fresh frame, transmits in next slot
if no collision: node can send new frame in next slot
if collision: node retransmits frame in each subsequent slot with prob. p until success
Slotted ALOHA
Pros:
single active node can continuously transmit at full rate of channel
highly decentralized: only slots in nodes need to be in sync
simple
Cons:
collisions, wasting slots
idle slots
nodes may be able to detect collision in less than time to transmit packet
clock synchronization
Slotted ALOHA: efficiency
suppose: N nodes with many frames to send, each transmits in slot with probability p
prob that given node has success in a slot = p(1-p)N-1
prob that any node has a success = Np(1-p)N-1
max efficiency: find p* that maximizes
Np(1-p)N-1
for many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives:
max efficiency = 1/e = .37
Pure (unslotted) ALOHA
unslotted Aloha: simpler, no synchronization
when frame first arrives
transmit immediately
collision probability increases:
frame sent at t0 collides with other frames sent in [t0-1,t0+1]
Pure ALOHA efficiency
P(success by given node) = P(node transmits) .
P(no other node transmits in [t0-1,t0] .
P(no other node transmits in [t0-1,t0]
= p . (1-p)N-1 . (1-p)N-1
=p . (1-p)2(N-1)
… choosing optimum p and then letting n
= 1/(2e) = .18
CSMA (carrier sense multiple access)
CSMA: listen before transmit:
if channel sensed idle: transmit entire frame
if channel sensed busy, defer transmission
human analogy: don’t interrupt others!
CSMA collisions
collisions can still occur: propagation delay means two nodes may not hear each other’s transmission
collision: entire packet transmission time wasted
distance & propagation delay play role in in determining collision probability
CSMA/CD (collision detection)
CSMA/CD: carrier sensing, deferral as in CSMA
collisions detected within short time
colliding transmissions aborted, reducing channel wastage
collision detection:
easy in wired LANs: measure signal strengths, compare transmitted, received signals
difficult in wireless LANs: received signal strength overwhelmed by local transmission strength
human analogy: the polite conversationalist
CSMA/CD (collision detection)
Ethernet CSMA/CD algorithm
1. NIC receives datagram from network layer, creates frame
2. If NIC senses channel idle, starts frame transmission. If NIC senses channel busy, waits until channel idle, then transmits.
3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
4. If NIC detects another transmission while transmitting, aborts and sends jam signal
5. After aborting, NIC enters binary (exponential) backoff:
after mth collision, NIC chooses K at random from {0,1,2, …, 2m-1}. NIC waits K·512 bit times, returns to Step 2
longer backoff interval with more collisions
CSMA/CD efficiency
Tprop = max prop delay between 2 nodes in LAN
ttrans = time to transmit max-size frame
efficiency goes to 1
as tprop goes to 0
as ttrans goes to infinity
better performance than ALOHA: and simple, cheap, decentralized!
“Taking turns” MAC protocols
channel partitioning MAC protocols:
share channel efficiently and fairly at high load
inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node!
random access MAC protocols
efficient at low load: single node can fully utilize channel
high load: collision overhead
“taking turns” protocols
look for best of both worlds!
“Taking turns” MAC protocols
polling:
master node “invites” slave nodes to transmit in turn
typically used with “dumb” slave devices
concerns:
polling overhead
latency
single point of failure (master)
“Taking turns” MAC protocols
Summary of MAC protocols
channel partitioning, by time, frequency or code
Time Division, Frequency Division
random access (dynamic),
ALOHA, S-ALOHA, CSMA, CSMA/CD
carrier sensing: easy in some technologies (wire), hard in others (wireless)
CSMA/CD used in Ethernet
CSMA/CA used in 802.11
taking turns
polling from central site, token passing
bluetooth, FDDI, token ring
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
MAC addresses and ARP
32-bit IP address:
network-layer address for interface
used for layer 3 (network layer) forwarding
MAC (or LAN or physical or Ethernet) address:
function: used ‘locally” to get frame from one interface to another physically-connected interface (same network, in IP-addressing sense)
48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
e.g.: 1A-2F-BB-76-09-AD
LAN addresses and ARP
LAN addresses (more)
MAC address allocation administered by IEEE
manufacturer buys portion of MAC address space (to assure uniqueness)
analogy:
MAC address: like Social Security Number
IP address: like postal address
MAC flat address ➜ portability
can move LAN card from one LAN to another
IP hierarchical address not portable
address depends on IP subnet to which node is attached
ARP: address resolution protocol
ARP table: each IP node (host, router) on LAN has table
IP/MAC address mappings for some LAN nodes:
< IP address; MAC address; TTL>
TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)
ARP protocol: same LAN
A wants to send datagram to B
B’s MAC address not in A’s ARP table.
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
B receives ARP packet, replies to A with its (B’s) MAC address
frame sent to A’s MAC address (unicast)
A caches (saves) IP-to-MAC address pair in its ARP table until information becomes old (times out)
soft state: information that times out (goes away) unless refreshed
ARP is “plug-and-play”:
nodes create their ARP tables without intervention from net administrator
Addressing: routing to another LAN
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 (how?)
assume A knows R’s MAC address (how?)
Addressing: routing to another LAN
Addressing: routing to another LAN
Addressing: routing to another LAN
Addressing: routing to another LAN
Addressing: routing to another LAN
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
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
Ethernet: physical topology
bus: popular through mid 90s
all nodes in same collision domain (can collide with each other)
star: prevails today
active switch in center
each “spoke” runs a (separate) Ethernet protocol (nodes do not collide with each other)
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
Ethernet: unreliable, connectionless
connectionless: no handshaking between sending and receiving NICs
unreliable: receiving NIC doesnt send acks or nacks to sending NIC
data in dropped frames recovered only if initial sender uses higher layer rdt (e.g., TCP), otherwise dropped data lost
Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff
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, cable
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
Ethernet switch
link-layer device: takes an active role
store, forward Ethernet frames
examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segment
transparent
hosts are unaware of presence of switches
plug-and-play, self-learning
switches do not need to be configured
Switch: multiple simultaneous transmissions
hosts have dedicated, direct connection to switch
switches buffer packets
Ethernet protocol used on each incoming link, but no collisions; full duplex
each link is its own collision domain
switching: A-to-A’ and B-to-B’ can transmit simultaneously, without collisions
Switch forwarding table
Q: how does switch know A’ reachable via interface 4, B’ reachable via interface 5?
Switch: self-learning
switch learns which hosts can be reached through which interfaces
when frame received, switch “learns” location of sender: incoming LAN segment
records sender/location pair in switch table
Switch: frame filtering/forwarding
when frame received at switch:
1. record incoming link, MAC address of sending host
2. index switch table using MAC destination address
3. ifentry found for destination
then {
ifdestination on segment from which frame arrived
then drop frame
else forward frame on interface indicated by entry
}
else flood /* forward on all interfaces except arriving
interface */
Self-learning, forwarding: example
frame destination, A’, location unknown:
Interconnecting switches
switches can be connected together
Institutional network
Switches vs. routers
both are store-and-forward:
routers: network-layer devices (examine network-layer headers)
switches: link-layer devices (examine link-layer headers)
both have forwarding tables:
routers: compute tables using routing algorithms, IP addresses
switches: learn forwarding table using flooding, learning, MAC addresses
VLANs: motivation
consider:
CS user moves office to EE, but wants connect to CS switch?
single broadcast domain:
all layer-2 broadcast traffic (ARP, DHCP, unknown location of destination MAC address) must cross entire LAN
security/privacy, efficiency issues
VLANs
port-based VLAN: switch ports grouped (by switch management software) so that single physical switch ……
Port-based VLAN
traffic isolation: frames to/from ports 1-8 can only reach ports 1-8
can also define VLAN based on MAC addresses of endpoints, rather than switch port
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
Multiprotocol label switching (MPLS)
initial goal: high-speed IP forwarding using fixed length label (instead of IP address)
fast lookup using fixed length identifier (rather than shortest prefix matching)
borrowing ideas from Virtual Circuit (VC) approach
but IP datagram still keeps IP address!
MPLS capable routers
a.k.a. label-switched router
forward packets to outgoing interface based only on label value (don’t inspect IP address)
MPLS forwarding table distinct from IP forwarding tables
flexibility: MPLS forwarding decisions can differ from those of IP
use destination and source addresses to route flows to same destination differently (traffic engineering)
re-route flows quickly if link fails: pre-computed backup paths (useful for VoIP)
MPLS versus IP paths
MPLS versus IP paths
MPLS forwarding tables
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a web request
Data center networks
10’s to 100’s of thousands of hosts, often closely coupled, in close proximity:
e-business (e.g. Amazon)
content-servers (e.g., YouTube, Akamai, Apple, Microsoft)
search engines, data mining (e.g., Google)
Link layer, LANs: outline
5.1 introduction, services
5.2 error detection, correction
5.3 multiple access protocols
5.4 LANs
addressing, ARP
Ethernet
switches
VLANS
5.5 link virtualization: MPLS
5.6 data center networking
5.7 a day in the life of a Web request
Synthesis: a day in the life of a web request
journey down protocol stack complete!
application, transport, network, link
putting-it-all-together: synthesis!
goal: identify, review, understand protocols (at all layers) involved in seemingly simple scenario: requesting www page
scenario: student attaches laptop to campus network, requests/receives www.google.com
A day in the life: scenario
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
A day in the life… connecting to the Internet
DHCP server formulates DHCP ACK containing client’s IP address, IP address of first-hop router for client, name & IP address of DNS server
A day in the life… ARP (before DNS, before HTTP)
before sending HTTPrequest, need IP address of www.google.com: DNS
A day in the life… using DNS
A day in the life…TCP connection carrying HTTP
A day in the life… HTTP request/reply
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links, characteristics
CDMA
6.3 IEEE 802.11 wireless LANs (“Wi-Fi”)
6.4 Cellular Internet Access
Mobility
6.5 Principles: addressing and routing to mobile users
6.6 Mobile IP
6.8 Mobility and higher-layer protocols
Elements of a wireless network
Elements of a wireless network
Elements of a wireless network
Elements of a wireless network
Elements of a wireless network
Elements of a wireless network
Wireless network taxonomy
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links, characteristics
CDMA
6.3 IEEE 802.11 wireless LANs (“Wi-Fi”)
6.4 Cellular Internet Access
Mobility
6.5 Principles: addressing and routing to mobile users
6.6 Mobile IP
6.8 Mobility and higher-layer protocols
Wireless Link Characteristics
important differences from wired link ….
decreased signal strength: radio signal attenuates as it propagates through matter (path loss)
interference from other sources: standardized wireless network frequencies (e.g., 2.4 GHz) shared by other devices (e.g., phone); devices (motors) interfere as well
multipath propagation: radio signal reflects off objects ground, arriving ad destination at slightly different times
…. make communication across (even a point to point) wireless link much more “difficult”
Wireless network characteristics
Multiple wireless senders and receivers create additional problems (beyond multiple access):
Code Division Multiple Access (CDMA)
unique “code” assigned to each user; i.e., code set partitioning
all users share same frequency, but each user has own “chipping” sequence (i.e., code) to encode data
allows multiple users to “coexist” and transmit simultaneously with minimal interference (if codes are “orthogonal”)
encoded signal = (original data) X (chipping sequence)
decoding: inner-product of encoded signal and chipping sequence
CDMA encode/decode
CDMA: two-sender interference
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links, characteristics
CDMA
6.3 IEEE 802.11 wireless LANs (“Wi-Fi”)
6.4 Cellular Internet Access
Mobility
6.5 Principles: addressing and routing to mobile users
6.6 Mobile IP
6.8 Mobility and higher-layer protocols
IEEE 802.11 Wireless LAN
802.11b
2.4-5 GHz unlicensed spectrum
up to 11 Mbps
direct sequence spread spectrum (DSSS) in physical layer
all hosts use same chipping code
802.11a
5-6 GHz range
up to 54 Mbps
802.11g
2.4-5 GHz range
up to 54 Mbps
802.11n: multiple antennas
2.4-5 GHz range
up to 600 Mbps
802.11 LAN architecture
802.11: Channels, association
802.11b: 2.4GHz-2.485GHz spectrum divided into 11 channels at different frequencies
AP admin chooses frequency for AP
interference possible: channel can be same as that chosen by neighboring AP!
host: must associate with an AP
scans channels, listening for beacon frames containing AP’s name (SSID) and MAC address
selects AP to associate with
may perform authentication [Chapter 8]
will typically run DHCP to get IP address in AP’s subnet
IEEE 802.11: multiple access
avoid collisions: 2+ nodes transmitting at same time
802.11: CSMA – sense before transmitting
don’t collide with ongoing transmission by other node
802.11: no collision detection!
difficult to receive (sense collisions) when transmitting due to weak received signals (fading)
can’t sense all collisions in any case: hidden terminal, fading
goal: avoid collisions: CSMA/C(ollision)A(voidance)
IEEE 802.11 MAC Protocol: CSMA/CA
802.11 sender
1 if sense channel idle for DIFS then
transmit entire frame (no CD)
2 if sense channel busy then
start random backoff time
timer counts down while channel idle
transmit when timer expires
if no ACK, increase random backoff interval, repeat 2
802.11 receiver
– if frame received OK
return ACK after SIFS (ACK needed due to hidden terminal problem)
Avoiding collisions (more)
idea: allow sender to “reserve” channel rather than random access of data frames: avoid collisions of long data frames
sender first transmits small request-to-send (RTS) packets to BS using CSMA
RTSs may still collide with each other (but they’re short)
BS broadcasts clear-to-send CTS in response to RTS
CTS heard by all nodes
sender transmits data frame
other stations defer transmissions
Collision Avoidance: RTS-CTS exchange
H1 remains in same IP subnet: IP address can remain same
Client-initiated switching to another AP
When signal is weak
Scan for nearby APs
Select the “best” AP and switch by “associating to” it
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links, characteristics
CDMA
6.3 IEEE 802.11 wireless LANs (“Wi-Fi”)
6.4 Cellular Internet access
Mobility
6.5 Principles: addressing and routing to mobile users
6.6 Mobile IP
6.8 Mobility and higher-layer protocols
Cellular networks: the first hop
Two techniques for sharing mobile-to-BS radio spectrum
combined FDMA/TDMA: divide spectrum in frequency channels, divide each channel into time slots
CDMA: code division multiple access
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links, characteristics
CDMA
6.3 IEEE 802.11 wireless LANs (“Wi-Fi”)
6.4 Cellular Internet Access
Mobility
6.5 Principles: addressing and routing to mobile users
6.6 Mobile IP
6.8 Mobility and higher-layer protocols
Mobility: vocabulary
Mobility: more vocabulary
Mobility: approaches
let routing handle it: routers advertise permanent address of mobile-nodes-in-residence via usual routing table exchange.
routing tables indicate where each mobile located
no changes to end-systems
let end-systems handle it:
indirect routing: communication from correspondent to mobile goes through home agent, then forwarded to remote
direct routing: correspondent gets foreign address of mobile, sends directly to mobile
Mobility: approaches
let routing handle it: routers advertise permanent address of mobile-nodes-in-residence via usual routing table exchange.
routing tables indicate where each mobile located
no changes to end-systems
let end-systems handle it:
indirect routing: communication from correspondent to mobile goes through home agent, then forwarded to remote
direct routing: correspondent gets foreign address of mobile, sends directly to mobile
Mobility: registration
end result:
foreign agent knows about mobile
home agent knows location of mobile
Mobility via indirect routing
Indirect Routing: comments
mobile uses two addresses:
permanent address: used by correspondent (hence mobile location is transparent to correspondent)
care-of-address: used by home agent to forward datagrams to mobile
foreign agent functions may be done by mobile itself
triangle routing: correspondent-home-network-mobile
inefficient when
correspondent, mobile
are in same network
Mobility via direct routing
Mobility via direct routing: comments
overcome triangle routing problem
non-transparent to correspondent: correspondent must get care-of-address from home agent
what if mobile changes visited network?
Chapter 6 outline
6.1 Introduction
Wireless
6.2 Wireless links, characteristics
CDMA
6.3 IEEE 802.11 wireless LANs (“Wi-Fi”)
6.4 Cellular Internet Access
Architecture
Mobility
6.5 Principles: addressing and routing to mobile users
6.6 Mobile IP
6.8 Mobility and higher-layer protocols
Mobile IP
RFC 3344
has many features we’ve seen:
home agents, foreign agents, foreign-agent registration, care-of-addresses, encapsulation (packet-within-a-packet)
three components to standard:
indirect routing of datagrams
agent discovery
registration with home agent
Mobile IP: indirect routing
Mobile IP: registration example
Wireless, mobility: impact on higher layer protocols
logically, impact should be minimal …
best effort service model remains unchanged
TCP and UDP can (and do) run over wireless, mobile
… but performance-wise:
packet loss/delay due to bit-errors (discarded packets, delays for link-layer retransmissions), and handoff
TCP interprets loss as congestion, will decrease congestion window un-necessarily
delay impairments for real-time traffic
limited bandwidth of wireless links
Multimedia networking: outline
7.1 multimedia networking applications
7.2 streaming stored video
7.3 voice-over-IP
7.4 protocols for real-time conversationalapplications
7.5 network support for multimedia
Multimedia networking: outline
7.1 multimedia networking applications
7.2 streaming stored video
7.3 voice-over-IP
7.4 protocols for real-time conversational applications
7.5 network support for multimedia
Multimedia: audio
Multimedia: audio
Multimedia: video
video: sequence of images displayed at constant rate
e.g. 24 images/sec
digital image: array of pixels
each pixel represented by bits
coding: use redundancy within and between images to decrease # bits used to encode image
spatial (within image)
temporal (from one image to next)
Multimedia: video
Multimedia networking: 3 application types
streaming, stored audio, video
streaming: can begin playout before downloading entire file
stored (at server): can transmit faster than audio/video will be rendered (implies storing/buffering at client)
e.g., YouTube, Netflix, Hulu
conversational voice/video over IP
interactive nature of human-to-human conversation limits delay tolerance
e.g., Skype
streaming live audio, video
e.g., live sporting event (futbol)
Multimedia networking: outline
7.1 multimedia networking applications
7.2 streaming stored video
7.3 voice-over-IP
7.4 protocols for real-time conversational applications
7.5 network support for multimedia
Streaming stored video:
Streaming stored video: challenges
Streaming stored video: revisited
client-side buffering and playout delay: compensate for network-added delay, delay jitter
Client-side buffering, playout
Client-side buffering, playout
Client-side buffering, playout
playout buffering: average fill rate (x), playout rate (r):
x < r: buffer eventually empties (causing freezing of video playout until buffer again fills)
x > r: buffer will not empty, provided initial playout delay is large enough to absorb variability in x(t)
initial playout delay tradeoff: buffer starvation less likely with larger delay, but larger delay until user begins watching
Streaming multimedia: UDP
server sends at rate appropriate for client
often: send rate = encoding rate = constant rate
transmission rate can be oblivious to congestion levels
short playout delay (2-5 seconds) to remove network jitter
error recovery: application-level, timeipermitting
RTP [RFC 2326]: multimedia payload types
UDP may not go through firewalls
Streaming multimedia: HTTP
multimedia file retrieved via HTTP GET
send at maximum possible rate under TCP
fill rate fluctuates due to TCP congestion control, retransmissions (in-order delivery)
larger playout delay: smooth TCP delivery rate
HTTP/TCP passes more easily through firewalls
Streaming multimedia: DASH
DASH: Dynamic, Adaptive Streaming over HTTP
server:
divides video file into multiple chunks
each chunk stored, encoded at different rates
manifest file: provides URLs for different chunks
client:
periodically measures server-to-client bandwidth
consulting manifest, requests one chunk at a time
chooses maximum coding rate sustainable given current bandwidth
can choose different coding rates at different points in time (depending on available bandwidth at time)
Streaming multimedia: DASH
DASH: Dynamic, Adaptive Streaming over HTTP
“intelligence” at client: client determines
when to request chunk (so that buffer starvation, or overflow does not occur)
what encoding rate to request (higher quality when more bandwidth available)
where to request chunk (can request from URL server that is “close” to client or has high available bandwidth)
Content distribution networks
challenge: how to stream content (selected from millions of videos) to hundreds of thousands of simultaneous users?
option 1: single, large “mega-server”
single point of failure
point of network congestion
long path to distant clients
multiple copies of video sent over outgoing link
….quite simply: this solution doesn’t scale
Content distribution networks
challenge: how to stream content (selected from millions of videos) to hundreds of thousands of simultaneous users?
option 2: store/serve multiple copies of videos at multiple geographically distributed sites (CDN)
enter deep: push CDN servers deep into many access networks
close to users
used by Akamai, 1700 locations
bring home: smaller number (10’s) of larger clusters in POPs near (but not within) access networks
used by Limelight
CDN: “simple” content access scenario
CDN cluster selection strategy
challenge: how does CDN DNS select “good” CDN node to stream to client
pick CDN node geographically closest to client
pick CDN node with shortest delay (or min # hops) to client (CDN nodes periodically ping access ISPs, reporting results to CDN DNS)
IP anycast
alternative: let client decide – give client a list of several CDN servers
client pings servers, picks “best”
Netflix approach
Case study: Netflix
30% downstream US traffic in 2011
owns very little infrastructure, uses 3rd party services:
own registration, payment servers
Amazon (3rd party) cloud services:
Netflix uploads studio master to Amazon cloud
create multiple version of movie (different endodings) in cloud
upload versions from cloud to CDNs
Cloud hosts Netflix web pages for user browsing
three 3rd party CDNs host/stream Netflix content: Akamai, Limelight, Level-3
Case study: Netflix
Multimedia networking: outline
7.1 multimedia networking applications
7.2 streaming stored video
7.3 voice-over-IP
7.4 protocols for real-time conversational applications
7.5 network support for multimedia
Voice-over-IP (VoIP)
VoIP end-end-delay requirement: needed to maintain “conversational” aspect
higher delays noticeable, impair interactivity
< 150 msec: good
> 400 msec bad
includes application-level (packetization,playout), network delays
session initialization: how does callee advertise IP address, port number, encoding algorithms?
value-added services: call forwarding, screening, recording
emergency services: 911
VoIP characteristics
speaker’s audio: alternating talk spurts, silent periods.
64 kbps during talk spurt
pkts generated only during talk spurts
20 msec chunks at 8 Kbytes/sec: 160 bytes of data
application-layer header added to each chunk
chunk+header encapsulated into UDP or TCP segment
application sends segment into socket every 20 msec during talkspurt
VoIP: packet loss, delay
network loss: IP datagram lost due to network congestion (router buffer overflow)
delay loss: IP datagram arrives too late for playout at receiver
delays: processing, queueing in network; end-system (sender, receiver) delays
typical maximum tolerable delay: 400 ms
loss tolerance: depending on voice encoding, loss concealment, packet loss rates between 1% and 10% can be tolerated
Delay jitter
end-to-end delays of two consecutive packets: difference can be more or less than 20 msec (transmission time difference)
VoIP: fixed playout delay
receiver attempts to playout each chunk exactly q msecs after chunk was generated.
chunk has time stamp t: play out chunk at t+q
chunk arrives after t+q: data arrives too late for playout: data “lost”
tradeoff in choosing q:
large q: less packet loss
small q: better interactive experience
VoIP: fixed playout delay
Adaptive playout delay (1)
goal: low playout delay, low late loss rate
approach: adaptive playout delay adjustment:
estimate network delay, adjust playout delay at beginning of each talk spurt
silent periods compressed and elongated
chunks still played out every 20 msec during talk spurt
adaptively estimate packet delay: (EWMA – exponentially weighted moving average, recall TCP RTT estimate):
Adaptive playout delay (2)
estimates di, vicalculated for every received packet, but used only at start of talk spurt
for first packet in talk spurt, playout time is:
remaining packets in talkspurt are played out periodically
Adaptive playout delay (3)
Q: How does receiver determine whether packet is first in a talkspurt?
if no loss, receiver looks at successive timestamps
difference of successive stamps > 20 msec –>talk spurt begins.
with loss possible, receiver must look at both time stamps and sequence numbers
difference of successive stamps > 20 msec and sequence numbers without gaps –> talk spurt begins.
VoiP: recovery from packet loss (1)
Challenge: recover from packet loss given small tolerable delay between original transmission and playout
each ACK/NAK takes ~ one RTT
alternative: Forward Error Correction (FEC)
send enough bits to allow recovery without retransmission (recall two-dimensional parity in Ch. 5)
simple FEC
for every group of n chunks, create redundant chunk by exclusive OR-ing n original chunks
send n+1 chunks, increasing bandwidth by factor 1/n
can reconstruct original n chunks if at most one lost chunk from n+1 chunks, with playout delay
VoiP: recovery from packet loss (2)
VoiP: recovery from packet loss (3)
interleaving to conceal loss:
audio chunks divided into smaller units, e.g. four 5 msec units per 20 msec audio chunk
packet contains small units from different chunks
if packet lost, still have most of every original chunk
no redundancy overhead, but increases playout delay
Voice-over-IP: Skype
proprietary application-layer protocol (inferred via reverse engineering)
encrypted msgs
P2P components:
P2P voice-over-IP: Skype
skype client operation:
Skype: peers as relays
problem: both Alice, Bob are behind “NATs”
NAT prevents outside peer from initiating connection to insider peer
inside peer can initiate connection to outside
Multimedia networking: outline
7.1 multimedia networking applications
7.2 streaming stored video
7.3 voice-over-IP
7.4 protocols for real-time conversational applications: RTP, SIP
7.5 network support for multimedia
Real-Time Protocol (RTP)
RTP specifies packet structure for packets carrying audio, video data
RFC 3550
RTP packet provides
payload type identification
packet sequence numbering
time stamping
RTP runs in end systems
RTP packets encapsulated in UDP segments
interoperability: if two VoIP applications run RTP, they may be able to work together
RTP runs on top of UDP
RTP example
example: sending 64 kbps PCM-encoded voice over RTP
application collects encoded data in chunks, e.g., every 20 msec = 160 bytes in a chunk
audio chunk + RTP header form RTP packet, which is encapsulated in UDP segment
RTP header indicates type of audio encoding in each packet
sender can change encoding during conference
RTP header also contains sequence numbers, timestamps
RTP and QoS
RTP does not provide any mechanism to ensure timely data delivery or other QoS guarantees
RTP encapsulation only seen at end systems (not by intermediate routers)
routers provide best-effort service, making no special effort to ensure that RTP packets arrive at destination in timely matter
RTP header
RTP header
timestamp field (32 bits long): sampling instant of first byte in this RTP data packet
for audio, timestamp clock increments by one for each sampling period (e.g., each 125 usecs for 8 KHz sampling clock)
if application generates chunks of 160 encoded samples, timestamp increases by 160 for each RTP packet when source is active. Timestamp clock continues to increase at constant rate when source is inactive.
SSRC field (32 bits long): identifies source of RTP stream. Each stream in RTP session has distinct SSRC
Real-Time Control Protocol (RTCP)
works in conjunction with RTP
each participant in RTP session periodically sends RTCP control packets to all other participants
each RTCP packet contains sender and/or receiver reports
report statistics useful to application: # packets sent, # packets lost, interarrival jitter
feedback used to control performance
sender may modify its transmissions based on feedback
RTCP: multiple multicast senders
RTCP: packet types
receiver report packets:
fraction of packets lost, last sequence number, average interarrival jitter
sender report packets:
SSRC of RTP stream, current time, number of packets sent, number of bytes sent
source description packets:
e-mail address of sender, sender’s name, SSRC of associated RTP stream
provide mapping between the SSRC and the user/host name
RTCP: stream synchronization
RTCP can synchronize different media streams within a RTP session
e.g., videoconferencing app: each sender generates one RTP stream for video, one for audio.
timestamps in RTP packets tied to the video, audio sampling clocks
not tied to wall-clock time
each RTCP sender-report packet contains (for most recently generated packet in associated RTP stream):
timestamp of RTP packet
wall-clock time for when packet was created
receivers uses association to synchronize playout of audio, video
RTCP: bandwidth scaling
RTCP attempts to limit its traffic to 5% of session bandwidth
example : one sender, sending video at 2 Mbps
RTCP attempts to limit RTCP traffic to 100 Kbps
RTCP gives 75% of rate to receivers; remaining 25% to sender
75 kbps is equally shared among receivers:
with R receivers, each receiver gets to send RTCP traffic at 75/R kbps.
sender gets to send RTCP traffic at 25 kbps.
participant determines RTCP packet transmission period by calculating avg RTCP packet size (across entire session) and dividing by allocated rate
SIP: Session Initiation Protocol [RFC 3261]
long-term vision:
all telephone calls, video conference calls take place over Internet
people identified by names or e-mail addresses, rather than by phone numbers
can reach callee (if callee so desires), no matter where callee roams, no matter what IP device callee is currently using
SIP services
SIP provides mechanisms for call setup:
for caller to let callee know she wants to establish a call
so caller, callee can agree on media type, encoding
to end call
determine current IP address of callee:
maps mnemonic identifier to current IP address
call management:
add new media streams during call
change encoding during call
invite others
transfer, hold calls
Example: setting up call to known IP address
Setting up a call (more)
codec negotiation:
suppose Bob doesn’t have PCM μlaw encoder
Bob will instead reply with 606 Not Acceptable Reply, listing his encoders. Alice can then send new INVITE message, advertising different encoder
rejecting a call
Bob can reject with replies “busy,” “gone,” “payment required,” “forbidden”
media can be sent over RTP or some other protocol
Example of SIP message
INVITE sip:bob@domain.com SIP/2.0
Via: SIP/2.0/UDP 167.180.112.24
From: sip:alice@hereway.com
To: sip:bob@domain.com
Call-ID: a2e3a@pigeon.hereway.com
Content-Type: application/sdp
Content-Length: 885
c=IN IP4 167.180.112.24
m=audio 38060 RTP/AVP 0
Notes:
HTTP message syntax
sdp = session description protocol
Call-ID is unique for every call
Name translation, user location
caller wants to call callee, but only has callee’s name or e-mail address.
need to get IP address of callee’s current host:
user moves around
DHCP protocol
user has different IP devices (PC, smartphone, car device)
result can be based on:
time of day (work, home)
caller (don’t want boss to call you at home)
status of callee (calls sent to voicemail when callee is already talking to someone)
SIP registrar
REGISTER sip:domain.com SIP/2.0
Via: SIP/2.0/UDP 193.64.210.89
From: sip:bob@domain.com
To: sip:bob@domain.com
Expires: 3600
SIP proxy
another function of SIP server: proxy
Alice sends invite message to her proxy server
contains address sip:bob@domain.com
proxy responsible for routing SIP messages to callee, possibly through multiple proxies
Bob sends response back through same set of SIP proxies
proxy returns Bob’s SIP response message to Alice
contains Bob’s IP address
SIP proxy analogous to local DNS server plus TCP setup
SIP example: jim@umass.edu calls keith@poly.edu
Multimedia networking: outline
7.1 multimedia networking applications
7.2 streaming stored video
7.3 voice-over-IP
7.4 protocols for real-time conversational applications
7.5 network support for multimedia
Network support for multimedia
Dimensioning best effort networks
approach: deploy enough link capacity so that congestion doesn’t occur, multimedia traffic flows without delay or loss
low complexity of network mechanisms (use current “best effort” network)
high bandwidth costs
challenges:
network dimensioning: how much bandwidth is “enough?”
estimating network traffic demand: needed to determine how much bandwidth is “enough” (for that much traffic)
Providing multiple classes of service
thus far: making the best of best effort service
one-size fits all service model
alternative: multiple classes of service
partition traffic into classes
network treats different classes of traffic differently (analogy: VIP service versus regular service)
Multiple classes of service: scenario
Scenario 1: mixed HTTP and VoIP
example: 1Mbps VoIP, HTTP share 1.5 Mbps link.
HTTP bursts can congest router, cause audio loss
want to give priority to audio over HTTP
Principles for QoS guarantees (more)
what if applications misbehave (VoIP sends higher than declared rate)
policing: force source adherence to bandwidth allocations
marking, policing at network edge
Principles for QoS guarantees (more)
allocating fixed (non-sharable) bandwidth to flow: inefficient use of bandwidth if flows doesn’t use its allocation
Scheduling and policing mechanisms
scheduling: choose next packet to send on link
FIFO (first in first out) scheduling: send in order of arrival to queue
discard policy: if packet arrives to full queue: who to discard?
tail drop: drop arriving packet
priority: drop/remove on priority basis
random: drop/remove randomly
Scheduling policies: priority
priority scheduling: send highest priority queued packet
multiple classes, with different priorities
class may depend on marking or other header info, e.g. IP source/dest, port numbers, etc.
Scheduling policies: still more
Round Robin (RR) scheduling:
multiple classes
cyclically scan class queues, sending one complete packet from each class (if available)
Policing mechanisms
goal: limit traffic to not exceed declared parameters
Three common-used criteria:
(long term) average rate:how many pkts can be sent per unit time (in the long run)
crucial question: what is the interval length: 100 packets per sec or 6000 packets per min have same average!
peak rate: e.g., 6000 pkts per min (ppm) avg.; 1500 ppm peak rate
(max.) burst size: max number of pkts sent consecutively (with no intervening idle)
Policing mechanism: token bucket
token bucket: limit input to specified burst size and average rate
bucket can hold b tokens
tokens generated at rate r token/sec unless bucket full
over interval of length t: number of packets admitted less than or equal to (r t + b)
Differentiated Services
want “qualitative” service classes
relative service distinction: Platinum, Gold, Silver
scalability: simple functions in network core, relatively complex functions at edge routers (or hosts)
signaling, maintaining per-flow router state difficult with large number of flows
don’t define definite service classes, provide functional components to build service classes
DiffServ architecture
Per-connection QoS guarantee
basic fact of life: can not support traffic demands beyond link capacity
QoS guarantee scenario
resource reservation
call setup, signaling (RSVP)
traffic, QoS declaration
per-element admission control
Chapter 8: Network Security
Chapter goals:
understand principles of network security:
cryptography and its many uses beyond “confidentiality”
authentication
message integrity
security in practice:
firewalls and intrusion detection systems
security in application, transport, network, link layers
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity, authentication
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
What is network security?
confidentiality: only sender, intended receiver should “understand” message contents
sender encrypts message
receiver decrypts message
authentication: sender, receiver want to confirm identity of each other
message integrity: sender, receiver want to ensure message not altered (in transit, or afterwards) without detection
access and availability: services must be accessible and available to users
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity, authentication
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
The language of cryptography
m plaintext message
KA(m) ciphertext, encrypted with key KA
m = KB(KA(m))
Symmetric key cryptography
symmetric key crypto: Bob and Alice share same (symmetric) key: K
e.g., key is knowing substitution pattern in mono alphabetic substitution cipher
Q: how do Bob and Alice agree on key value?
AES: Advanced Encryption Standard
symmetric-key NIST standard
processes data in 128 bit blocks
128, 192, or 256 bit keys
brute force decryption (try each key) taking 149 trillion years for AES
Public key cryptography
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity, authentication
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
Authentication
Goal: Bob wants Alice to “prove” her identity to him
Authentication
Authentication: another try
Authentication: another try
Authentication: another try
Authentication: another try
Authentication: yet another try
Authentication: yet another try
Authentication: yet another try
Authentication: ap5.0
ap4.0 requires shared symmetric key
can we authenticate using public key techniques?
ap5.0: use nonce, public key cryptography
ap5.0: security hole
man (or woman) in the middle attack: Trudy poses as Alice (to Bob) and as Bob (to Alice)
ap5.0: security hole
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity, authentication
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
Digital signatures
cryptographic technique analogous to hand-written signatures:
sender (Bob) digitally signs document, establishing he is document owner/creator.
verifiable, nonforgeable: recipient (Alice) can prove to someone that Bob, and no one else (including Alice), must have signed document
Digital signatures
simple digital signature for message m:
Bob signs m by encrypting with his private key KB, creating “signed” message, KB(m)
Digital signatures
Alice thus verifies that:
Bob signed m
no one else signed m
Bob signed m and not m‘
non-repudiation:
Alice can take m, and signature KB(m) to court and prove that Bob signed m
Message digests
computationally expensive to public-key-encrypt long messages
goal: fixed-length, easy- to-compute digital “fingerprint”
apply hash function H to m, get fixed size message digest, H(m).
Hash function properties:
many-to-1
produces fixed-size msg digest (fingerprint)
given message digest x, computationally infeasible to find m such that x = H(m)
Alice verifies signature, integrity of digitally signed message:
Hash function algorithms
MD5 hash function widely used (RFC 1321)
computes 128-bit message digest in 4-step process.
arbitrary 128-bit string x, appears difficult to construct msg m whose MD5 hash is equal to x
SHA-1 is also used
US standard [NIST, FIPS PUB 180-1]
160-bit message digest
Recall: ap5.0 security hole
man (or woman) in the middle attack: Trudy poses as Alice (to Bob) and as Bob (to Alice)
Public-key certification
motivation: Trudy plays pizza prank on Bob
Trudy creates e-mail order:
Dear Pizza Store, Please deliver to me four pepperoni pizzas. Thank you, Bob
Trudy signs order with her private key
Trudy sends order to Pizza Store
Trudy sends to Pizza Store her public key, but says it’s Bob’s public key
Pizza Store verifies signature; then delivers four pepperoni pizzas to Bob
Bob doesn’t even like pepperoni
Certification authorities
certification authority (CA): binds public key to particular entity, E.
E (person, router) registers its public key with CA.
E provides “proof of identity” to CA.
CA creates certificate binding E to its public key.
certificate containing E’s public key digitally signed by CA – CA says “this is E’s public key”
Certification authorities
when Alice wants Bob’s public key:
gets Bob’s certificate (Bob or elsewhere).
apply CA’s public key to Bob’s certificate, get Bob’s public key
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity, authentication
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
Secure e-mail
Secure e-mail
Secure e-mail (continued)
Secure e-mail (continued)
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
SSL: Secure Sockets Layer
widely deployed security protocol
supported by almost all browsers, web servers
https
billions $/year over SSL
mechanisms: [Woo 1994], implementation: Netscape
variation -TLS: transport layer security, RFC 2246
provides
confidentiality
integrity
authentication
original goals:
Web e-commerce transactions
encryption (especially credit-card numbers)
Web-server authentication
optional client authentication
minimum hassle in doing business with new merchant
available to all TCP applications
secure socket interface
SSL and TCP/IP
Real SSL
connection
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
What is network-layer confidentiality ?
between two network entities:
sending entity encrypts datagram payload, payload could be:
TCP or UDP segment, ICMP message, OSPF message ….
all data sent from one entity to other would be hidden:
web pages, e-mail, P2P file transfers, TCP SYN packets …
“blanket coverage”
Virtual Private Networks (VPNs)
motivation:
institutions often want private networks for security.
costly: separate routers, links, DNS infrastructure.
VPN: institution’s inter-office traffic is sent over public Internet instead
encrypted before entering public Internet
logically separate from other traffic
IPsec services
data integrity
origin authentication
replay attack prevention
confidentiality
two protocols providing different service models:
AH
ESP
Two IPsec protocols
Authentication Header (AH) protocol
provides source authentication & data integrity but not confidentiality
Encapsulation Security Protocol (ESP)
provides source authentication, data integrity, and confidentiality
more widely used than AH
What happens?
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
802.11i: four phases of operation
Chapter 8 roadmap
8.1 What is network security?
8.2 Principles of cryptography
8.3 Message integrity
8.4 Securing e-mail
8.5 Securing TCP connections: SSL
8.6 Network layer security: IPsec
8.7 Securing wireless LANs
8.8 Operational security: firewalls and IDS
Firewalls
Firewalls: why
Stateless packet filtering
internal network connected to Internet via router firewall
router filters packet-by-packet, decision to forward/drop packet based on:
source IP address, destination IP address
TCP/UDP source and destination port numbers
ICMP message type
TCP SYN and ACK bits
Limitations of firewalls, gateways
IP spoofing: router can’t know if data “really” comes from claimed source
if multiple app’s. need special treatment, each has own app. gateway
client software must know how to contact gateway.
e.g., must set IP address of proxy in Web browser
filters often use all or nothing policy for UDP
tradeoff: degree of communication with outside world, level of security
many highly protected sites still suffer from attacks
Intrusion detection systems
packet filtering:
operates on TCP/IP headers only
no correlation check among sessions
IDS: intrusion detection system
deep packet inspection: look at packet contents (e.g., check character strings in packet against database of known virus, attack strings)
examine correlation among multiple packets
port scanning
network mapping
DoS attack
Network Security (summary)
basic techniques……
cryptography (symmetric and public)
message integrity
end-point authentication
…. used in many different security scenarios
secure email
secure transport (SSL)
IP sec
802.11
operational security: firewalls and IDS