Distributed Algorithms
Distributed Computing
• What is a distributed computing system ?
A distributed system is a model in which components located on
networked computers communicate and coordinate their actions by
passing messages. The components interact with each other in order to
achieve a common goal.
The topology of a distributed system is represented by a graph
where the nodes represent processes, and the links represent
communication channels.
Distributed Algorithm
Distributed algorithms for various graph theoretic problems
have numerous applications in distributed computing system.
• Topology of a DS is represented by a graph
• A network of processes. The nodes are processes, and the
edges are communication channels.
Parallel vs Distributed
• In both parallel and distributed systems, the events are
partially ordered.
• The distinction between parallel and distributed is not always
very clear.
• In parallel systems, the primarily issues are
- speed-up and increased data handling capability.
• In distributed systems the primary issues are
- fault-tolerance, synchronization, scalability, etc.
Parallel Vs Distributed
• Tightly coupled systems
• Parallel processing systems.
• Loosely coupled systems
• Distributed computing
systems.
Examples
• Large networks are very commonplace these days. Think of
the world wide web.
Other examples are:
- Social Networks
- Sensor networks
- BitTorrent for downloading video / audio
- Skype for making free audio and video communication
- Computational grids
- Network of mobile robots
Why distributed systems???
• Geographic distribution of processes
• Resource sharing (example: P2P networks, grids)
• Computation speed up (as in a grid)
• Fault tolerance
• etc.
Important Services
• Internet banking
•Web search
• Net meeting
• Distance education
• Internet auction
• Google earth
• Skype
• Video distribution
• Publish subscribe
Important issues
• Knowledge is local
• Clocks are not synchronized
• No shared address space
• Topology and routing : everything is dynamic
• Scalability: all solutions do not scale well
• Processes and links fail: Fault tolerance
Common measures
• Space complexity
How much space is needed per process to run an
algorithm? (measured in terms of N, the size of the network)
• Time complexity
What is the max. time (number of steps) needed to
complete the execution of the algorithm?
• Message complexity
How many message are needed to complete the execution
of the algorithm?
Socket Programming
Nidhi Joraviya
Agenda
• Introduction
• Elements of Client Server Computing
• Networking Basics
• Understanding Ports and Sockets
• Java Sockets
• Implementing a Server
• Implementing a Client
• Sample Examples
• Conclusions
13
Introduction
• Internet and WWW have emerged as global ubiquitous
media for communication and changing the way we
conduct science, engineering, and commerce.
• They also changing the way we learn, live, enjoy,
communicate, interact, engage, etc. It appears like the
modern life activities are getting completely centered
around the Internet.
14
Internet Applications Serving Local and Remote Users
PC client
Internet
Server
Local Area Network
PDA
15
Increased demand for Internet applications
• To take advantage of opportunities presented by the Internet,
businesses are continuously seeking new and innovative ways and
means for offering their services via the Internet.
• This created a huge demand for software designers with skills to
create new Internet-enabled applications or migrate existing/legacy
applications on the Internet platform.
• Object-oriented Java technologies—Sockets, threads, RMI,
clustering, Web services-- have emerged as leading solutions for
creating portable, efficient, and maintainable large and complex
Internet applications.
16
Elements of C-S Computing
a client, a server, and network
t
es
qu
Re
Client
Server
Network
Re
su
lt
Client machine
Server machine
17
Networking Basics
• Applications Layer • TCP/IP Stack
• Standard apps
• HTTP
• FTP Application
• Telnet
• User apps (http,ftp,telnet,…)
• Transport Layer Transport
• TCP (TCP, UDP,..)
• UDP
• Programming Interface: Network
• Sockets (IP,..)
• Network Layer
• IP Link
• Link Layer (device driver,..)
• Device drivers
18
Networking Basics
• TCP (Transport Control Protocol) is • TCP/IP Stack
a connection-oriented protocol
that provides a reliable flow of Application
data between two computers. (http,ftp,telnet,…)
• Example applications: Transport
• HTTP (TCP, UDP,..)
• FTP
Network
• Telnet
(IP,..)
Link
(device driver,..)
19
Networking Basics
• UDP (User Datagram Protocol) is a protocol that sends independent packets
of data, called datagrams, from one computer to another with no
guarantees about arrival.
• Example applications:
• Clock server
• Ping
20
Understanding Ports
P
• The TCP and UDP protocols o
TCP
server
use ports to map incoming r
Client
data to a particular process t
running on a computer.
app app app app
port port port port
TCP or UDP
Packet
Data port# 21
data
Understanding Ports
• Port is represented by a positive (16-bit) integer value
• Some ports have been reserved to support common/well known
services:
• ftp 21/tcp
• telnet 23/tcp
• smtp 25/tcp
• login 513/tcp
• User level process/services generally use port number value >=
1024
22
Sockets
• Sockets provide an interface for programming networks at the transport
layer.
• Network communication using Sockets is very much similar to performing
file I/O
• In fact, socket handle is treated like file handle.
• The streams used in file I/O operation are also applicable to socket-based I/O
• Socket-based communication is programming language independent.
• That means, a socket program written in Java language can also communicate to a
program written in Java or non-Java socket program.
23
Communication Diagram
24
Socket Communication
• A server (program) runs on a specific computer and has a
socket that is bound to a specific port. The server waits and
listens to the socket for a client to make a connection request.
Connection request
port
server
Client
25
Socket Communication
• If everything goes well, the server accepts the connection. Upon
acceptance, the server gets a new socket bounds to a different port. It
needs a new socket (consequently a different port number) so that it can
continue to listen to the original socket for connection requests while
serving the connected client.
port
server
port
Client
port Connection
26
Sockets and Java Socket Classes
• A socket is an endpoint of a two-way communication link
between two programs running on the network.
• A socket is bound to a port number so that the TCP layer can
identify the application that data destined to be sent.
• Java’s .net package provides two classes:
• Socket – for implementing a client
• ServerSocket – for implementing a server
27
Java Sockets
Server ServerSocket(1234)
Output/write stream Client
Input/read stream
Socket(“128.250.25.158”, 1234)
It can be host_name like “mandroo.cs.mu.oz.au” 28
Implementing a Server
1. Open the Server Socket:
ServerSocket server;
DataOutputStream os;
DataInputStream is;
server = new ServerSocket( PORT );
2. Wait for the Client Request:
Socket client = server.accept();
3. Create I/O streams for communicating to the client
is = new DataInputStream( client.getInputStream() );
os = new DataOutputStream( client.getOutputStream() );
4. Perform communication with client
Receive from client: String line = is.readLine();
Send to client: os.writeBytes("Hello\n");
5. Close sockets: client.close();
For multithreaded server:
while(true) {
i. wait for client requests (step 2 above)
ii. create a thread with “client” socket as parameter (the thread creates streams (as in step (3) and does
communication as stated in (4). Remove thread once service is provided.
} 29
Implementing a Client
1. Create a Socket Object:
client = new Socket( server, port_id );
2. Create I/O streams for communicating with the server.
is = new DataInputStream(client.getInputStream() );
os = new DataOutputStream( client.getOutputStream() );
3. Perform I/O or communication with the server:
• Receive data from the server:
String line = is.readLine();
• Send data to the server:
os.writeBytes("Hello\n");
4. Close the socket when done:
client.close();
30
A simple server (simplified code)
// SimpleServer.java: a simple server program
import java.net.*;
import java.io.*;
public class SimpleServer {
public static void main(String args[]) throws IOException {
// Register service on port 1234
ServerSocket s = new ServerSocket(1234);
Socket s1=s.accept(); // Wait and accept a connection
// Get a communication stream associated with the socket
OutputStream s1out = s1.getOutputStream();
DataOutputStream dos = new DataOutputStream (s1out);
// Send a string!
dos.writeUTF("Hi there");
// Close the connection, but not the server socket
dos.close();
s1out.close();
s1.close();
31
A simple client (simplified code)
// SimpleClient.java: a simple client program
import java.net.*;
import java.io.*;
public class SimpleClient {
public static void main(String args[]) throws IOException {
// Open your connection to a server, at port 1234
Socket s1 = new Socket("mundroo.cs.mu.oz.au",1234);
// Get an input file handle from the socket and read the input
InputStream s1In = s1.getInputStream();
DataInputStream dis = new DataInputStream(s1In);
String st = new String (dis.readUTF());
System.out.println(st);
// When done, just close the connection and exit
dis.close();
s1In.close();
s1.close();
}
}
32
Run
• Run Server on mundroo.cs.mu.oz.au
• [raj@mundroo] java SimpleServer
• Run Client on any machine (including mundroo):
• [raj@mundroo] java SimpleClient
Hi there
• If you run client when server is not up:
• [raj@mundroo] sockets [1:147] java SimpleClient
Exception in thread "main" java.net.ConnectException: Connection refused
at java.net.PlainSocketImpl.socketConnect(Native Method)
at java.net.PlainSocketImpl.doConnect(PlainSocketImpl.java:320)
at java.net.PlainSocketImpl.connectToAddress(PlainSocketImpl.java:133)
at java.net.PlainSocketImpl.connect(PlainSocketImpl.java:120)
at java.net.Socket.<init>(Socket.java:273)
at java.net.Socket.<init>(Socket.java:100)
at SimpleClient.main(SimpleClient.java:6)
33
Socket Exceptions
try {
Socket client = new Socket(host, port); handleConnection(client);
}
catch(UnknownHostException uhe) { System.out.println("Unknown host: " +
host); uhe.printStackTrace();
}
catch(IOException ioe) {
System.out.println("IOException: " + ioe); ioe.printStackTrace();
}
34
Server in Loop: Always up
// SimpleServerLoop.java: a simple server program that runs forever in a single thead
import java.net.*;
import java.io.*;
public class SimpleServerLoop {
public static void main(String args[]) throws IOException {
// Register service on port 1234
ServerSocket s = new ServerSocket(1234);
while(true)
Socket s1=s.accept(); // Wait and accept a connection
// Get a communication stream associated with the socket
OutputStream s1out = s1.getOutputStream();
DataOutputStream dos = new DataOutputStream (s1out);
// Send a string!
dos.writeUTF("Hi there");
// Close the connection, but not the server socket
dos.close();
s1out.close();
s1.close();
35
Multithreaded Server: For Serving Multiple
Clients Concurrently
Client 1 Process Server Process
Server
Threads
■ Internet
Client 2 Process
36
Conclusion
• Programming client/server applications in Java is fun and
challenging.
• Programming socket programming in Java is much easier than
doing it in other languages such as C.
• Keywords:
• Clients, servers, TCP/IP, port number, sockets, Java sockets
37
Socket Programming in C
