DS-Chapter DDEFR2-Communication_105220.ppt

DS BY MENOR DESTA

1. Chapter 2 -Communication

2. 2
Introduction
Interprocess communication is at the heart of all distributed
systems
communication in distributed systems is based on message
passing as offered by the underlying network as opposed to
using shared memory
modern distributed systems consist of thousands of
processes scattered across an unreliable network such as
the Internet
unless the primitive communication facilities of the network
are replaced by more advanced ones, development of large
scale Distributed Systems becomes extremely difficult

3. 3
Objectives of the Chapter
review of how processes communicate in a network (the
rules or the protocols) and their structures
introduce the four widely used communication models for
distributed systems:
Remote Procedure Call (RPC)
Remote Method Invocation (RMI)
Message-Oriented Middleware (MOM)
Streams/ Stream Oriented Communication (SOC)

4. 4
2.1 Layered Protocols
two computers, possibly from different manufacturers, must
be able to talk to each other
for such a communication, there has to be a standard
The ISO OSI (Open Systems Interconnection) Reference
Model is one of such standards -7 layers
TCP/IP protocol suite is the other; has 4 or 5 layers
OSI
Open–to connect open systems or systems that are open
for communication with other open systems using standard
rules that govern the format, contents, and meaningof the
messages sent and received
these rules are called protocols
two types of protocols: connection-oriented and
connectionless

5. 5
layers, interfaces, and protocols in the OSI model

6. 6
Physical: Physical characteristics of the media
Host (upper) Layers
Media (lower) Layers
Data Link: Reliable data delivery across the link
Network: Managing connections across the network
or routing
Transport:End-to-end connection and reliability (handles
lost packets); TCP (connection-oriented),
UDP (connectionless), etc.
Session: Managing sessions between applications
(dialog control and synchronization); rarely
supported
Presentation:Data presentation to applications; concerned
with the syntax and semantics of the
information transmitted
Application:Network services to applications; contains
protocols that are commonly needed by
users; FTP, HTTP, SMTP, ...

7. 7
a typical message as it appears on the network

8. 8discussion between a receiver and a sender in the data link layer
a conversation occurs between a sender and a receiver at
each layer
e.g., at the data link layer

9. 9
normal operation of TCP
assuming no messages are lost,
the client initiates a setup
connection using a three-way
handshake (1-3)
the client sends its request (4)
it then sends a message to
close the connection (5)
the server acknowledges
receipt and informs the client
that the connection will be
closed down (6)
then sends the answer (7)
followed by a request to close
the connection (8)
the client responds with an ack
to finish conversation (9)
Transport Protocols: Client-Server TCP

10. 10
transactional TCP
much of the overhead in TCP is for managing the connection
the client sends a single
message consisting of a setup
request, service request, and
information to the server that
the connection will be closed
down immediately after
receiving the answer (1)
the server sends acceptance of
connection request, the
answer, and a connection
release (2)
the client acknowledges tear
down of the connection (3)
combine connection setup with
request and closing connection
with answer
such protocol is called TCP for
Transactions(T/TCP)

11. 11
2.2 Remote Procedure Call
the first distributed systems were based on explicit message
exchange between processes through the use of
explicit/clear sendand receiveprocedures; but do not allow
access transparency
in 1984, Birrel and Nelson introduced a different way of
handling communication: i.e called Remote Procedure Call
it allows a program to call a procedure located on another
machine
simple and sophisticated, but there are implementation
problems
the calling and called procedures run in different address
spaces
parameters and results have to be exchanged;
what if the machines are not identical?
what happens if both machines crash?

12. 12
parameter passing in a local procedure
call: the stack before the call to read
Conventional Procedure Call, i.e., on a single machine
e.g. count = read (fd, buf, bytes); a C like statement, where
fdis an integer indicating a file
bufis an array of characters into which data are read
bytesis the number of bytes to be read
the stack while the called
procedure is active
Stack pointer
parameters can be call-by-value(fd and bytes) or call-by
reference(buf) or in some languages call-by-copy/restore
Stack pointer

13. 13
principle of RPC between a client and server program
Client and Server Stubs
RPCwouldliketomakearemoteprocedurecalllookthe
sameasalocalone;itshouldbetransparent,i.e.,thecalling
procedureshouldnotknowthatthecalledprocedureis
executingonadifferentmachineorviceversa
when a program is compiled, it uses different versions of library
functions called client stubs. A serverstubis the server-side equivalent
of a clientstub. A server stub is a piece of code that transforms
requests coming in over the network in local procedure calls

14. 14
Steps of a Remote Procedure Call
1.Client procedure calls client stub in the normal way
2.Client stub builds a message and calls the local OS
(packing parameters into a message is called parameter
marshaling)
3.Client's OS sends the message to the remote OS
4.Remote OS gives the message to the server stub
5.Server stub unpacks the parameters and calls the server
6.Server does the work and returns the result to the stub
7.Server stub packs it in a message and calls the local OS
8.Server's OS sends the message to the client's OS
9.Client's OS gives the message to the client stub
10.Stub unpacks the result and returns to client
hence, for the client remote services are accessed by making
ordinary (local) procedure calls; not by calling sendand
receive
server machine vs server process; client machine vs client process

15. 15
steps involved in doing remote computation through RPC
2.2.2 Parameter Passing
1. Passing Value Parameters
e.g., consider a remote procedure add(i, j),where iand jare
integer parameters

16. 16
the above discussion applies if the server and the client
machines are identical
but that is not the case in large distributed systems
the machines may differ in data representation (e.g., IBM
mainframes use EBCDIC whereas IBM PCs use ASCII)
byte numbering may be different (from right to left in Pentium
called little endian and left to right in SPARC, big endian)

17. 17
original message on the Pentium
(the numbers in boxes indicate the address of each byte)
the message after receipt on the SPARC; wrong integer, but correct string

18. 18
the message after being inverted (correct integer but wrong string)
one approach is to invert the bytes of each word after
receipt
additional information is required to tell which is an
integer and which is a string

19. 19
2. Passing Reference Parameters
assumetheparameterisapointertoanarray
copythearrayintothemessageandsendittotheserver
theserverstubcanthencalltheserverwithapointertothis
array
theserverthenmakesanychangestothearrayandsendsit
backtotheclientstubwhichcopiesittotheclient
thisisineffectcall-by-copy/restore
optimizationofthemethod
oneofthecopyoperationscanbeeliminatedifthestub
knowswhethertheparameterisinputoroutputtothe
server
ifitisaninputtotheserver(e.g.,inacalltowrite),itneed
notbecopiedback
ifitisanoutput,itneednotbesentoverinthefirstplace;
onlysendthesize

20. 20
a dooris a generic name for a procedurein the address
space of a server process that can be called by a process
colocated with the server
support from the local OS is required
2.2.3 Extended RPC Models
to solve some of the shortcomings of the original model
no need of network communication if server and client are
on the same machine
no need of blocking for the client in some cases
a. Doors
the original RPC model assumes that the caller and the
callee can communicate only by means of passing
messages over a network; what if they are colocated on
the same machine?

21. 211
2
3
the principle of using doors as IPC mechanism
1.the server process registers a door before it can be called
(door_create) and a name is attached to it
1.a client calls a door by a system call (door_call) including
all parameters
2.results are returned by the system call door_return

22. 22
benefit: it allows the use of a single mechanism (procedure
calls) for communication
disadv: application developers have to be aware of where a
procedure is located; is it
local within the current process
local to a different process on the same machine
a remote process

23. 23
b. Asynchronous RPC
if there is no need to block the client until it gets a reply
two cases
1. if there is no result to be returned
e.g., adding entries in a database, ...
the server immediately sends an ack promising that it
will carryout the request
the client can now proceed without blocking
a)the interconnection between client and server in a traditional RPC
b)the interaction using asynchronous RPC

24. 24
2. if the result can be collected later
e.g., prefetching network addresses of a set of hosts, ...
the server immediately sends an ack promising that it
will carryout the request
the client can now proceed without blocking
the server later sends the result
a client and server interacting through two asynchronous RPCs

25. 25
the above method combines two asynchronous RPCs
and is sometimes called deferred synchronous RPC
variants of asynchronous RPC
let the client continue without waiting even for an ack,
called one-way RPC
problem: if reliability of communication is not
guaranteed

26. 26
2.2.4 DCE (Distributed Computing Environment) RPC
a middleware and an example RPC system developed by OSF
(Open Software Foundation), now The Open Group
it is designed to executeas a layer of abstraction between existing
OSs and distributed applications
the Open Group sells the source codeand vendors integrate it into
their systems
it uses the client-server programming model and communication
is by means of RPCs
services
distributed file service: a worldwide file system that provides a
transparent way of accessing files
directoryservice: to keep track of the location of all resources
in the system (machines, printers, data, servers, ...); a process
can ask for a resource without knowing its location
securityservice: for protecting resources; access is only
through authorization
distributedtimeservice: to maintain clocks on different
machines synchronized (clock synchronization is covered in
Chapter 5)

27. 27
Binding a Client to a Server in DCE RPC
for a client to call a server, the server must be registered (1 &
2)
the registration allows the client to locate the server and
bind to it
the DCE daemon maintainsa table (server, endpoint) and the
protocols the server uses
the directory server maintains the locations of all resources
in the system (machines, servers, data,, ...)
two steps for server location
locate the server’s machine (3)
locate the server process on that machine (which has
what is called an endpointor port) (4)

28. 28

29. 29w
1
resulted from object-based technologythat has proven its
value in developing non-distributed applications
it is an expansion of the RPC mechanisms
it enhances distribution transparency as a consequence of
an object that hides its internal from the outside world by
means of a well-defined interface i.e called data abstraction
Distributed Objects
an object encapsulates data, called the state, and the
operations on those data, called methods
methods are made available through interfaces
the state of an object can be manipulated only by invoking
methods
this allows an interface to be placed on one machinewhile
the object itself resides on anothermachine; such an
organization is referred to as a distributed object
the state of an object is not distributed, only the interfaces
are; such objects are also referred to as remoteobjects
2.3 Remote Object (Method) Invocation (RMI)

30. 30
the implementation of an object’s interface is called a proxy
(analogous to a client stub in RPC systems)
it is loaded into the client’s address space when a client
bindsto a distributed object
Tasks:
a proxy marshals/binds together method invocation into
messages and unmarshals/unpacking reply messages to
return the result of the method invocation to the client
a server stub, called a skeleton, unmarshals messages and
marshals replies
Skeleton in RMI is an equivalent to server stub in RPC.

31. 31
common organization of a remote object with client-side proxy

32. 32
Binding a Client to an Object
aprocessmustfirstbindtoanobjectbefore
invoking/raisingitsmethods,whichresultsinaproxy
beingplacedintheprocess’saddressspace
bindingcanbeimplicit(directlyinvokemethodsusing
onlyareferencetoanobject)orexplicit(bycallinga
specialfunction)
anobjectreferencecouldcontain
networkaddressofthemachinewheretheobject
resides
endpointoftheserver
anidentificationofwhichobject
theprotocolused
...

33. 33
RPCs and RMIs are not adequate for all distributed system
applications
the provision of access transparency may be good but
they have semantics that is not adequate for all
applications
example problems
they assume that the receiving side is running at the
time of communication
a client is blocked until its request has been processed
2.4 Message Oriented Communication

34. 34
2.4.1 Persistence and Synchronicity in Communication
general organization of a communication system in which hosts are connected
through a network
assume the communication system is organized as a
computer network shown below

35. 35
communication can be
persistent or transient
asynchronous or synchronous
persistent: a message that has been submitted for
transmission is stored by the communication system as long
as it takes to deliver it to the receiver
e.g., email delivery, snail mail delivery
persistent communication of letters back in the days of the Pony Express

36. 36
transient: a message that has been submitted for
transmission is stored by the communication system only as
long as the sending and receiving applications are executing
Persistent Transient
Asynchronous
 
Synchronous

message-oriented; three forms
asynchronous: a sender continues immediately after it has
submitted its message for transmission
synchronous: the sender is blocked until its message is
stored in a local buffer at the receiving host or delivered to the
receiver
the different types of communication can be combined
persistent asynchronous: e.g., email
transient asynchronous: e.g., UDP, asynchronous RPC
in general there are six possibilities

37. 37
persistent asynchronous communicationpersistent synchronous communication

38. 38
receipt-based transient synchronous
communication
transient asynchronous communication
weakest form; the sender is
blocked until the message is
stored in a local buffer at the
receiving host

39. 39
response-based transient synchronous
communication
delivery-based transient synchronous
communication at message delivery
the sender is blocked until the
message is delivered to the
receiver for further processing;
e.g., asynchronous RPC
strongest form; the sender is
blocked until it receives a reply
message from the receiver

40. 40B
2.4.2 Message-Oriented Transient Communication
many applications are built on top of the simple message-
oriented model offered by the transport layer
standardizing the interface of the transport layer by
providing a set of primitives allows programmers to use
messaging protocols
they also allow porting applications
1.Berkley Sockets
an example is the socket interfaceas used in Berkley
UNIX
a socketis a communication endpoint to which an
application can write data that are to be sent over the
network, and from which incoming data can be read

41. 41
socket primitives for TCP/IP
PrimitiveMeaning Executedby
Socket
Create a new communication endpoint; also
reserve resources to send and receive messages
both
Bind
Attach a local address to a socket; e.g., IP
address with a known port number
servers
Listen
Announce willingness to accept connections; for
connection-oriented communication
Accept Block caller until a connection request arrives
Connect
Actively attempt to establish a connection; the
client is blocked until connection is set up
Send Send some data over the connection
ReceiveReceive some data over the connection
Close Release the connection

42. 42
connection-oriented communication pattern using sockets

43. 43
2. The Message-Passing Interface (MPI)
sockets were designed to communicate across networks
using general-purpose protocol stacks such as TCP/IP
they were not designed for proprietary protocols
developed for high-speed interconnection networks; of
course portability will suffer
MPI is designed for parallel applications and
tailored/customized for transient communication
MPI assumes communication takes place within a known
group of processes, where each group is assigned an
identifier (groupID)
each process within a group is also assigned an identifier
(processID)
a (groupID, processID) identifies the source or destination
of a message, and is used instead of a transport-level
address

44. 44
some of the most intuitive message-passing primitives of MPI
Primitive Meaning
MPI_bsend
Append outgoing message to a local send buffer; to support
transient asynchronous communication
MPI_send
Send a message and wait until copied to local or remote
buffer (to support receipt-based transient synchronous
communication)
MPI_ssend
Send a message and wait until receipt starts (to support
delivery-based transient synchronous communication)
MPI_sendrecv
Send a message and wait for reply (to support response-
based transient synchronous communication)
MPI_isend
Pass reference to outgoing message, and continue (a
variant of MPI_send)
MPI_issend
Pass reference to outgoing message, and wait until receipt
starts (a variant of MPI_ssend)
MPI_recv Receive a message; block if there are none
MPI_irecv Check if there is an incoming message, but do not block

45. 45
2.4.3 Message-Oriented Persistent Communication
there are message-oriented middleware services, called
message-queuingsystemsor Message-OrientedMiddleware
(MOM)
they support persistent asynchronous communication
they have intermediate-term storage capacity for messages,
without requiring the sender or the receiver to be active
during message transmission
unlike Berkley sockets and MPI, message transfer may take
minutes instead of seconds or milliseconds
Message-QueuingModel
applications communicate by inserting messages in
specific queues
it permits loosely-coupled communication
the sender may or may not be running; similarly the
receiver may or may not be running, giving four possible
combinations

46. 46
four combinations for loosely-coupled communications using queues

47. 47
basic interface to a queue in a message-queuing system
PrimitiveMeaning
Put
Append a message to a specified queue; by the sender
and is nonblocking
Get
Block until the specified queue is nonempty, and remove
the first message
Poll
Check a specified queue for messages, and remove the
first. Never block
Notify
Install a handler to be called when a message is put into
the specified queue; usually a daemon

48. 48the relationship between queue-level addressing and network-level addressing
General Architecture of a Message-Queuing System
messages can be put only into queues that are local to the
sender (same machine or on a nearby machine on a LAN)
such a queue is called the sourcequeue
messages can also be read only from local queues
a message put into a local queue must contain the specification
of the destination queue; hence a message-queuing system
must maintain a mapping of queues to network locations; like
in DNS

49. 49
messages are managed by queuemanagers
they generally interact with the application that sends and
receives messages
some also serve as routersor relays, i.e., they forward
incoming messages to other queue managers
however, each queue manager needs a copy of the queue-
to-location mapping, leading to network management
problems for large-scale queuing systems
the solution is to use a few routers that know about the
network topology

50. 50
the general organization of a message-queuing system with routers

51. 51the general organization of a message broker in a message-queuing system
MessageBrokers
how can applications understand the messages they receive
each receiver can not be made to understand message formats
of new applications
hence, in a message-queuing system conversations are
handled by message brokers
a message broker converts incoming messages to a format that
can be understood by the destination application based on a
set of rules

52. 52
until now, we focused on exchanging independent and
complete units of information
time has no effect on correctness; a system can be slow or fast
however, there are communications where time has a critical
role
Multimedia
media
storage, transmission, interchange, presentation,
representation and perception of different data types:
text, graphics, images, voice, audio, video, animation, ...
movie: video + audio + …
multimedia: handling of a variety of representation media
end user pull
information overload and starvation
technology push
emerging technology to integrate media
2.4 Stream Oriented Communication

53. 53
The Challenge
new applications
multimedia will be pervasive/widespread in few years (as
graphics)
storage and transmission
e.g., 2 hours uncompressed HDTV (1920×1080) movie:
1.02 TB (1920×1080x3x25x60x60x2)
videos are extremely large, even compressed
continuous delivery
e.g., 30 frames/s (NTSC), 25 frames/s (PAL) for video
guaranteed Quality of Service
admission control
search
can we look at 100… videos to find the proper one?

54. 54
Types of Media
two types
discrete media: text, executable code, graphics, images;
temporal relationships between data items are not
fundamental to correctly interpret the data
continuous media: video, audio, animation; temporal
relationships between data items are fundamental to
correctly interpret the data
a datastreamis a sequence of data units and can be applied
to discrete as well as continuous media
stream-oriented communication provides facilities for the
exchange of time-dependent information(continuous media)
such as audio and video streams

55. 55
timing in transmission modes
asynchronous transmission mode: data items are
transmitted one after the other, but no timing constraints;
e.g. text transfer
synchronous transmission mode: a maximum end-to-end
delay defined for each data unit; it is possible that data can
be transmitted faster than the maximum delay, but not slower
isochronous transmission mode: maximum and minimum
end-to-end delay are defined; also called boundeddelay
jitter; applicable for distributed multimedia systems
a continuous data stream can be simple or complex
simple stream: consists of a single sequence of data; e.g.,
mono audio, video only
complex stream: consists of several related simple streams
that must be synchronized; e.g., stereo audio, video
consisting of audio and video (may also contain subtitles,
translation to other languages, ...)

56. 56
movie as a set of simple streams

57. 57m
1
setting up a stream between two processes across a network
a stream can be considered as a virtual connection between a
source and a sink
the source or the sink could be a process or a device
setting up a stream directly between two devices

58. 58
an example of multicasting a stream to several receivers
the data stream can also be multicasted to several receivers
if devices and the underlying networks have different
capabilities, the stream may be filtered, generally called
adaptation (filtering?,transcoding?)

59. 59
Quality of Service (QoS)
QoS requirements describe what is needed from the
underlying distributed system and network to ensure
acceptable delivery; e.g. viewing experience of a user
for continuous data, the concerns are
timeliness: data must be delivered in time
volume: the required throughput must be met
reliability: a given level of loss of data must not be
exceeded
qualityofperception; highly subjective

60. 60
can be static or dynamic
StaticQoS Management Functions
specification
e.g., deterministic range for timeliness, volume and
reliability categories
negotiation
the application may accept lower level of QoS for
lower cost
admissioncontrol
if this test is passed, the system has to guarantee the
promised QoS
resourcereservation
may be necessary to provide guaranteed QoS
QoS Management

61. 61
monitoring
notices deviation from QoS level
at a certain level of granularity (e.g., every 100 ms)
policing
detect participants not keeping themselves to the contract
e.g., source sends faster than negotiated (e.g., 25 fps)
renegotiation
client tries to adapt –may be can accept lower QoS
DynamicQoS Management Functions

62. 62
QoS requirements can be specified using flow specification
containing bandwidth requirements, transmission rates,
delays, ...
e.g. by Partridge (1992)
it uses the token bucket algorithm which specifies how the
stream will shape its network traffic (in fact the leaky
bucket, as used in networking)
the idea is to shape bursty traffic into fixed-rate traffic by
averaging the data rate
packets may be dropped if the bucket is full
the input rate may vary, but the output rate remains
constant

63. 63
the principle of a token bucket algorithm
Setting up a Stream
resources such as bandwidth, buffers, processing power
must be reserved once a flow specification is made
on such protocol is RSVP -Resource reSerVation Protocol
it is a transport-level protocol for enabling resource
reservation in network routers

64. 64
Streaming stored audio/video
streaming means a user can listen (or watch) the file after
the downloading has started
the files are compressed and stored on a server
examples are songs, famous lectures, movies, TV shows,
music video clips, ...
such a service is usually called on-demand audio/video
(VoD) -similar to a rental store
communication is often unicast and on-demand
there are different approaches

65. 65
Using a Web Server
download a compressed audio/video file as text file
the client can use the services of HTTP and then use a media
player to play the file
1. Establish TCP connection,
Send HTTP GET request
2. Server gets file from disk,
File sent back
3. Browser writes file to disk,
Media player fetches file
block by block and plays it

66. 66
the basic organization of RSVP for resource reservation in a distributed system