Transcript class slides

Introduction to Networking and
Distributed Systems
Operating Systems
Fall 2002
OS Fall’02
Overview
 Intro to Networking
Review of Basic principles:
 layers, protocols, etc…
TCP/IP and the Internet
Implementation issues
 Intro to Distributed systems
client/server
OS Fall’02
Communication in everyday life
I like
rabbits
J’aime
les
lapins
L: Dutch
L: Dutch
Ik hou
van
konijnen
Ik hou
van
konijnen
Fax#
Fax#
L: Dutch
L: Dutch
Ik hou
van
konijnen
Ik hou
van
konijnen
OS Fall’02
Computer based communication
mail
mail
message
mail
mail
encode
encode
message rep
OS Fall’02
Computer based communication
mail
mail
encode
encode
message rep
mail
mail
encode
encode
packets
packets
mess rep pkt
age rep pkt
OS Fall’02
Computer based communication
mail
mail
encode
encode
packets
packets
route
route
route
message rep pkt addr
OS Fall’02
Computer based communication
mail
mail
encode
encode
packets
packets
route
route
route
error
error
error
message rep pkt addr ECC
OS Fall’02
Layered organization
 Computer networks are structured as
layer (protocol) stacks
 Each layer provides services to the layer
above
 Layers communicate by protocols
service
API
service
protocol
OS Fall’02
API
Protocols
 Protocol is a collection of message formats and
their interpretation needed to implement the
layer service
format: header+data
headers convey the protocol specific information
OS Fall’02
Standards and openness
 Protocols must be standardized for
interoperability
 Layer APIs must be standardized for
portability
 Existing standards:
ISO OSI Layered model (“eight-layer model”)
TCP/IP is a de-facto model of the Internet
OS Fall’02
ISO OSI Layered model
Application
Application
Presentation
Presentation
Session
Session
Transport
Transport
Network
Network
Data Link
Data Link
Physical
Physical
OS Fall’02
Lower OSI Layers
 Physical layer:
Voltages to represent 0/1, how many bits per
second can be sent, simplex/duplex,
hardware
 Data Link layer:
Grouping bits into frames,
point-to-point reliability, error
detection/correction
OS Fall’02
Network and Transport
 Network layer:
Getting data from one host to another
 Routing, addressing, fragmentation/reassembly
 Transport layer:
End-to-end application connectivity
Reliable transport connection:
 Messages are not lost and delivered in the order
they were sent
 Transmission Control Protocol (TCP)
OS Fall’02
Session and Presentation
 Session layer:
Enhanced transport layer: session control
 Presentation layer:
Message structure: e.g., records
Data representation
compression and encryption
OS Fall’02
Application Layer
 General-purpose high level services and
abstractions
File transfer (FTP)
Hyper-text transfer (HTTP)
Remote Procedure Call (RPC)
Network File System (NFS)
Object Request Brokers
 CORBA, Java RMI
Etc...
OS Fall’02
TCP/IP Protocol Suite
OSI model
TCP/IP protocol suite
Application
Application
Presentation
Session
Transport
TCP/UDP
Network
IP
Datalink
Network access
Physical
Physical
OS Fall’02
OS
Hardware
Physical Networks
 Each computer is directly attached to
some physical network
Network Interface Cards (NIC)+cables
Usually limited geographical scale (Local Area
Network=LAN)
 MAN, WAN
supports routing, addressing, network access
within its boundaries
 LAN: Ethernet (10Mbit/sec, 100Mbit/sec),
Token ring, Fibre channel, etc...
OS Fall’02
Physical networks characteristics
 Bandwidth: Number of bits per second
 Latency: The time it takes to send a
single bit
 Ethernet:
Shared bus bandwidth: 10Mbit/sec
Switched Ethernet bw: 100Mbit/sec
OS Fall’02
Ethernet LAN
 Shared bus
 Each NIC has a
unique address
 Messages are
broadcast
If collision occurs,
wait for a randomly
chosen time period
and retry
Maximum Transfer Unit
(MTU) = 1536 Bytes
OS Fall’02
Internet protocol (IP)
 Creates an illusion of a single physical
network over a collection of
heterogeneous LANs
Global addressing, routing
Fragmentation, reassembly to overcome
differences in the MTU sizes
 Architecture: LANs interconnected by
routers (gateways)
OS Fall’02
Internet Protocol (IP)
 Connectionless
Each packet is routed independently based
on the IP address in the header
 Connections are supported by the
transport layer (TCP)
OS Fall’02
The Internet
OS Fall’02
The Internet
OS Fall’02
TCP/IP transport protocols
 Connectivity between application endpoints
Application end-point is uniquely identified by
(IP address,port number)
 Transmission Control Protocol (TCP)
Reliable end-to-end byte stream,
connection oriented
 User Datagram Protocol (UDP)
Unreliable, connectionless
OS Fall’02
Implementation issues
 Reliability
 Flow control
 Routing
OS Fall’02
Reliability
 Physical networks are inherently
unreliable
Messages can be both: corrupted and lost
 Dealing with corruption
Error detection, error correction
 Dealing with message loss
retransmission
OS Fall’02
Error detection/correction
 Parity bit is the simplest error detection
technique
Parity bit is the binary sum of the message
bits
Detects corruption of a single bit
 More parity bits are needed for error
correction
OS Fall’02
Error correction
 Forward Error Correction (FEC)
A bit at position 2i ,i 0 holds parity of bits
whose positions includes 2i in its binary
representation
 The positions of wrong parity bits yield
the position of the erroneous bit
Corrects a single bit error
 In practice more sophisticated techniques
are used (e.g., CRC)
OS Fall’02
Dealing with message loss
 Timeouts
Send a message, wait for an
acknowledgment (ACK)
If an acknowledgment does not arrive during
a predefined timeout period: retransmit the
message
 If ack is lost a message can be sent more than
once!
 Negative acknowledgments
OS Fall’02
Flow control
 Sender and received have limited buffer
space to hold outgoing and incoming
messages
 Flow control is needed to avoid buffer
overflow
 The simplest technique:
The receiver buffer size in known in advance
Sender never sends a new message until it
knows that the receiver has enough space to
accommodate it
OS Fall’02
Routing
 Each router holds a table indicating the
next router (hop) on the way to each
destination
The next hop router must reside on the same
physical network (LAN)
 Routers exchange messages to update
their routing tables
 Protocols: Distance Vector (BellmanFord), Open Shortest Path First (OSPF)
OS Fall’02
Distributed Systems
 A distributed system (middleware) is an
implementation of an application level
service
 Distributed systems support high level
abstractions
 Remote Procedure Call (RPC): everything looks
like a local function call
 Network File System (NFS): everything looks like
a local file
 Object Based systems: Everything looks like a
local object
OS Fall’02
Client/Server Paradigm
 Distributed systems are usually structured
according to the client/server model
 A server implements a service
 Clients request service from the server
using a pre-defined protocol
 WWW, FTP, Telnet, NFS are all
client/server based
OS Fall’02
Internet Well-known services
 Well-known services must be supported
by all the computers connected to the
Internet
Ftp, telnet, rlogin, nfs
 Domain Name Service (DNS)
Symbolic name <-> IP address
 Uniquely identified by the port number of
the server
HTTP: 80, FTP: 20
OS Fall’02
RPC
 A server registers a procedure
implementation
 A client calls a function which looks local
to the client
E.g., add(a,b)
 The RPC implementation packs
(marshals) the function name and
parameter values into a message and
sends it to the server
OS Fall’02
RPC
 Server accepts the message, unpacks
(unmarshals) parameters and calls the
local function
 Return values is then marshaled into a
message and sent back to the client
 Marshaling/unmarshaling must take into
account differences in data
representation
OS Fall’02
RPC
 Transport: both TCP and UDP
 Data types: atomic types and non-
recursive structures
 Pointers are not supported
 Complex memory objects (e.g., linked
lists) are not supported
 NFS is built on top of RPC
OS Fall’02
Next:
 Storage Area Networks and
 Modern storage architectures
OS Fall’02