COMPUTER NETWORKS Flashcards
Protocols
TCP/IP
General Network (WAN or LAN)
nodes, aka switches) inside the subnet, connected by
communication links;
(external devices, e.g., computers, servers, terminals, and so
on) outside the subnet, connected via the subnet
Messages
originated at these external devices,
pass into the subnet,
from node to node on the links,
to the external recipient.
: a string of bits
Topology
placement of links between
nodes
LAN
Local Area Networks
on the order of a square kilometer or less.
restricted topology – nodes distributed on a bus, a ring, or a
star
MAN
Metropolitan Area Networks)
WAN
more than a metropolitan,
comparatively arbitrary topology.
Packet
transmitting messages long in length can be harmful – delay,
congestion, complex buffer management…,
solution: messages broken into shorter strings, i.e., packets,
packets transmitted through the subnet as individual entities,
and reassembled into messages at the destination
Session
a sequence of messages. e.g.:
Interactive: short messages, small delay, high reliability,
File: long messages, moderate delays
Shared Media Broadcast Network
defn: terminals share a common channels (for example,
Ethernet, Token Ring);
all will receive the sender’s message, but only the receiver is
interested;
cheap, limited in scalability
Switched Point-to-point Network
defn: information travels over several points from one terminal
to the other;
circuit switched - separate channel for session, e.g., telephone.
packet switched/store-and-forward - several sessions share
channel
Circuit Switching
Packet Switching
virtual circuit routing (generally used in practise, connection
oriented)
a fixed path,
but it is virtual - link capacity shared by sessions, and link use
based on demand.
dynamic routing (connectionless)
packets may be missing,
packets might arrive destination in different order.
, 8
Circuit Switching
assign a rate rs to the session s,
create a path
allocate/reserve rs on each link of the path
condition: sum of all rates cannot exceed the total
transmission capacity of the link
if no such path can be found, the session is rejected,
once a session is setup, it has guaranteed transmission rate rs
through the network
example: telephone network
Packet Switching concepts
circuit Switching: Inefficient Use of Links
Typical data sessions tend to have short bursts of high activity
followed by lengthy inactive periods;
but circuit switching wastes the allocated rate during these
inactive periods.
A quantitative view:
let λ be the message arrival rate for a given session. (e.g.,
λ = 3 messages/min)
1/λ, the expected interarrival time between messages (1/3
minutes, 20 sec.)
̄X , expected transmission time of a message (4 sec).
Delays
Queueing Delay: the time the packet is assigned to a queue
for transmission and the time it starts being transmitted.
During this time, the packet waits while other packets in the
transmission queue are transmitted.
Propagation Delay: the time between the last bit is
transmitted at the head node of the link and the time the last
bit is received at the tail node. This is proportional to the
physical distance between transmitter and receiver
Packet Switching: Control of Queueing Delay
packets queued are from many different sites, when delay
excessive (or buffer full) need to slow down.
hard to control,
largely nonexistent in circuit switching
Circuit Switching vs. Packet Switching
Complexity of Networks
Many issues to address
synchronization, encoding, addressing, error control, ordering
messages, flow control, message segmentation, framing,
routing, scheduling, multiplexing, security, billing, compression,
code conversion.
useful method of dealing with complexity is through the use of
functional modularity.
break complex problem into simple sub-problems,
use “black box” abstraction of sub-problems.
example:
computer: processor, memory, bus, …
processor: control unit, arithmetic unit, I/O Unit …
arithmetic unit: adders, accumulators
, 16
Layered Network Architectures
Hierarchical Layering, a type of functional modularity useful in
communication networks
Peers of Peer Processe
members of the same layer at
different locations
Protocol
set of rules for how peers interac
Service
function performed by layer N for layer N+1 across
an interface
Network Architecture
the set of layers (services and
protocols) that defines a network
Explain a blackbox communication system
Explain the 7 architecture system
Describe the order of growth of data units between:
Transport layer
Network Layer
Data Link layer
Application Layer
Service: Supports applications
Tasks: Connection setup, flow control, error contorl.
Examples: HTTP to support the web, SMTP to support
electronic email, FTP to support file transfer.
, 22
Transport Layer
Service: prepares messages for being transported over the
network
Tasks: splitting/multiplexing of sessions, message
fragmentation and reassembly, flow control, error control,
connection setup
breaks messages into packets at the transmitting end and
reassembles packets into messages at the receiving end,
end-to-end flow control.
Examples: TCP(Transmission Control Protocol), UDP (User
Datagram Protocol
Network Layer
Service: Send data units over the network. All peer processes
work together.
Tasks: Routing, addressing, congestion control
Packet: (Packet Header, Packet Body)
the header is used to accomplish routing and flow control
functions.
virtual circuit vs. dynamic routing - for successive packets of a
session, with/out initiation, same/different routes, arrives
in/out order, with/out dropped packets.
congestion, users demand more than the capacity can offer.
solution? flow-control.
along with new packets arrive from the higher layer, transited
packets arrive from the lower layer.
Examples: IP (Internet Protocol)
, 24
Data Link Layer
Service: Sends data units over a link, asynchronously, but
error free.
Tasks: framing, error control, retransmissions
Frame: Header, Packet, Tailer
overheads control bits determine, whether errors occur, if so
request retransmission, delineate the beginning and ending of
frames.
typically packets leave the receiving DL in the same order in
which they enter the transmitting DL
Physical Layer
Service: Sends a sequence of bits over a link between a pair of
nodes.
Modem (Modulator/Demodulator)
map the incoming bits from Data Link Layer into signals,
map the signals back into bits at the receiving end.
, 26
Why use the layers
users care only about what the underlying system does, not
about how it does it,
standardizing what the system does allows the implementation
to change while the users get the same service,
with this standardization, users can change their systems
without worrying about the underlying system,
this allows overall systems to evolve very rapidly, while
interface standards change slowly,
also allows multiple vendors to offer compatible products.
Layer Functions
error control: makes the logical channel between the layers in
two peer processes more reliable,
flow control: avoids overwhelming a slower peer process,
segmentation and reassembly of data units,
multiplexing: allows several higher-level sessions to share a
single lower-level connection,
connection setup: provides handshaking with peer process
Server
always-on host
permanent IP address
data centers for scaling
clients:
communicate with server
may be intermittently connected
may have dynamic IP addresses
do not communicate directly with each other
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 to deliver message to socket at receiving process
Addressing processes
does IP address of host on which process runs suffice for identifying the process?
no, many processes can be running on same host
identifier
Reliable data transfer
some apps (e.g., file transfer, web transactions) require 100% reliable data transfer
other apps (e.g., audio) can tolerate some loss
throughput
some apps (e.g., multimedia) require minimum amount of throughput to be “effective”
other apps (“elastic apps”) make use of whatever throughput they get (e.g., email, file transfer.
timing
some apps (e.g., Internet telephony, interactive games) require low delay to be “effective”
Transport service requirements: common apps
security
encryption, data integrity,
TCP service:
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 guarantee, security
connection-oriented: setup required between client and server processes
Internet apps: application, transport protocols
UDP service:
unreliable data transfer between sending and receiving process
does not provide: reliability, flow control, congestion control, timing, throughput guarantee, security, or connection setup,
connection-less: no hand shaking between client and server processes
HTTP
hypertext transfer protocol
client
browser that requests, receives, (using HTTP protocol) and “displays” Web objects
server
Web server sends (using HTTP protocol) objects in response to requests
HTTP overview
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
HTTP is “stateless”
server maintains no information about past client requests
persistent HTTP
multiple objects can be sent over single TCP connection between client, server
non-persistent HTTP
at most one object sent over TCP connection
connection then closed
downloading multiple objects required multiple connections
Non-persistent HTTP Overview
- HTTP server closes TCP connection.
- HTTP client receives response message containing html file, displays html. Parsing html file, finds 10 referenced jpeg objects
- Steps 1-5 repeated for each of 10 jpeg objects
Non-persistent HTTP: response time
RTT Round Trip Time (definition): time for a small packet to travel from client to server and back
HTTP 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
non-persistent HTTP response time =
2RTT+ file transmission time
non-persistent HTTP issues:
requires 2 RTTs per object
OS overhead for each TCP connection
browsers often open parallel TCP connections to fetch referenced object
persistent HTTP:
server leaves connection open after sending response
subsequent HTTP messages between same client/server sent over open connection
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
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
often used by application developer for debugging
Method types: 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
User-server state: cookies
what cookies can be used for:
authorization
shopping carts
recommendations
user session state (Web e-mail)
how to keep “state”:
protocol endpoints: maintain state at sender/receiver over multiple transactions
cookies: http messages carry state
FTP: the file transfer protocol
FTP: separate control, data connections
FTP client contacts FTP server at port 21, using TCP
client authorized over control connection
client browses remote directory, sends commands over control connection
when server receives file transfer command, server opens 2nd TCP data connection (for file) to client
after transferring one file, server closes data connection
server opens another TCP data connection to transfer another file
control connection: “out of band”
FTP server maintains “state”: current directory, earlier authentication
FTP commands, repesponses
Electronic mail
Electronic mail: mail servers
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 (like HTTP, FTP)
commands: ASCII text
response: status code and phrase
messages must be in 7-bit ASCII
Mail access protocols
SMTP: delivery/storage to receiver’s server – assuming Bob reads his email by logging onto the server and executing a mail reader on the server.
But how can emails be read from user’s end systems? (no push protocol such as SMTP).
Mail Access Protocols: retrieval from server
POP: Post Office Protocol [RFC 1939]: authorization, download
IMAP: Internet Mail Access Protocol [RFC 1730]: more features, including manipulation of stored msgs on server
HTTP: gmail, Hotmail, Yahoo! Mail, etc.
DNS: services, structure
DNS services
hostname to IP address translation
host aliasing
canonical, alias names
mail server aliasing
toronto.ca, utoronto.edu.
load distribution
to associate several IP addresses with a single host name.
when the DNS responds to a request, a whole list of addresses are returned to the client.
these addresses are then used in a round-robin or load-sharing fashion, providing some form of load balancing.
DNS: domain name system
people: many identifiers:
SSN, name, passport #
Internet hosts, routers:
IP address (32 bit) - used for addressing datagrams
“name”, e.g., www.yahoo.com - used by humans
Q: how to map between IP address and name, and vice versa ?
Domain Name System:
distributed database implemented in hierarchy of many name servers
application-layer protocol: hosts, name servers communicate to resolve names (address/name translation)
note: core Internet function, implemented as application-layer protocol
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
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
multiplexing at sender:
handle data from multiple
sockets, add transport header (later used for demultiplexing)
demultiplexing at receiver:
use header info to deliver
received segments to correct
socket
Connection-oriented demux
Connectionless demultiplexing
How demultiplexing works
host receives IP datagrams
each datagram has source IP address, destination IP address
each datagram carries one transport-layer segment
each segment has source, destination port number
host uses IP addresses & port numbers to direct segment to appropriate socket
UDP: User Datagram Protocol [RFC 768]
UDP: segment header
UDP checksum
rdt2.0: channel with bit errors
rdt2.0 has a fatal flaw!
rdt2.1: discussion
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
rdt3.0: channels with errors and loss
Pipelined protocols
Pipelined protocols: overview
Selective repeat
TCP reliable data transfer
TCP creates rdt service on top of IP’s unreliable service
pipelined segments
cumulative acks
single retransmission timer
retransmissions triggered by:
timeout events
duplicate acks
TCP sender events:
TCP 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.
TCP flow control
receiver “advertises” free buffer space by including rwnd value in TCP header of receiver-to-sender segments
RcvBuffer size set via socket options (typical default is 4096 bytes)
many operating systems autoadjust RcvBuffer
sender limits amount of unacked (“in-flight”) data to receiver’s rwnd value
guarantees receive buffer will not overflow
Connection Management
before exchanging data, sender/receiver “handshake”:
agree to establish connection (each knowing the other willing to establish connection)
agree on connection parameters
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!
TCP: closing a connection
client, server each close their side of connection
send TCP segment with FIN bit = 1
respond to received FIN with ACK
on receiving FIN, ACK can be combined with own FIN
simultaneous FIN exchanges can be handled
Approaches towards congestion control
Case study: ATM ABR congestion control
TCP Slow Start
TCP: detecting, reacting to loss
loss indicated by timeout:
cwnd set to 1 MSS;
window then grows exponentially (as in slow start) to threshold, then grows linearly
loss indicated by 3 duplicate ACKs: TCP RENO
dup ACKs indicate network capable of delivering some segments
cwnd is cut in half window then grows linearly
TCP Tahoe always sets cwnd to 1 (timeout or 3 duplicate acks)
TCP Fairness
fairness goal: if K TCP sessions share same bottleneck link of bandwidth R, each should have average rate of R/K
