**Implementing Remote Procedure Call**
======================================

# Take away:
- How to make RPC fast:
1) implicit acknowledgement 
2) minimize cost of setting up, maintaining, and terminating connection
3) use process ID on packet, hence reduce number of process switch
4) modify network driver, to by pass normal software layer

- RPC semantics:
+ client will receive an exception if server crashes or communication breakdown
+ procedure at server is executed only once 
==> sequence number to eliminate duplicates

i.e at most once semantics:
if the call returns to the user then the procedure in the server has been 
invoked precisely once. Otherwise, an exception is reported to the user and the 
procedure will have been invoked either once or not at all--the user is not told 
which. If an exception is reported, the user does not know whether the server 
has crashed or whether there is a problem in the communication network

NOTE: See Remzi's notes for more detail on simple call.
Basically, a simple client call contains:
- Table index: identify which interface to call (for fast lookup)
- UID (to identify server crashes with a long wait)
- entry point # (why not passing the address to client? Security reason,
  server don't want to jump to that address)
- Stub gen (args)
- CallerID: [MachineID, PID], sequence #
	+ MachineID, PID, and sequence # is used to look up old result 
	(if this client happens to make a call twice and so forth)
	+ Implication: one outstanding activity from process

Why need to write its own Transfer protocol? Why not directly use TPC?
- still need to deal with failure anyway
- TPC is not optimized for RPC, extra ack and stuff, therefore slower.	

# Why RPC?
- clean and simple, like normal local procedure call
- efficient (probably, but it seems simple enough to implement it efficiently)
- generality

# Challenges:
- semantics of call in presents of machine and communication failures
- address-containing argument
 	+ caller and callee does not share same address space
- integration of RPC into existing programming systems
- data integrity and security
- data transfer and control protocol

# Goals
- Easiness: i.e call to an RPC like call to a local procedure
- Efficiency: fast RPC
- Powerful semantics without loosing easiness and efficiency
- secure communication

# Design Decision
- RPC over message passing:
	+ leverage support from Mesa language (control and data transfer mechanism)
- No shared address space between caller and callee of RPC
	+ could be, but will be complicated (problem integration and efficiency)
	(how? )
- No timeout
 	+ because want the semantics of RPC as close as local procedure call
	+ KISS

# Structure


	user		<------------->		server
	 |								 |
	 |								 |
	user stub	<------------->		server stub
 	 |								 |
	 |								 |
	RPC RT    	<-------------> 	RPC RT

1) user program makes normal local call to user stub
2) user stub put arguments and the target call into packets, ask RPC RT to 
transmit
3) RPC RT:
	+ retransmission
	+ ack
	+ packet routing
	+ encryption
4) server stub unpacks the packet, make normal call to server
(note: during this: user is suspended waiting)

# How does a client specify what he want to bind to: Naming?
- Naming: type & instance

# Location: how to keep caller find out machine address of callee?
- Alternative 1: hardcode the callee machine address into apps programs
	==> inflexible, bind too early
- Alternative 2: use broadcast protocol
	==> interference of other nodes not involved in the call
- Alternative 3: database lookup (Grapevine)
 This paper uses alternative 3


Exporting Step: when server wants to export his interface
	1) Server calls server-stub, which calls ExportInterface in RPC RT
	2) ExportInterface is given:
		+ interface name
		+ procedure (dispatcher) implemented in server-stub handling 
		incoming packet
	3) RPC RT updates Grapevine
	4) For each exported interface, RPC RT at exporting machine keeps:
		+ interface name
		+ dispatcher name
		+ unique ID (implemented as a counter) (why need this)

Binding:
	1) User code calls user-stub, which calls ImportInterface in RPCRT,
	giving it type and instance
	2) RPC RT ask grapevine for network address of the exporter
	3) RCP RT (at user) make an RPC to RPCRT (at server)
	4) The ID and table index are returned to binding machine
	(exporter network address, ID, index are remembered by user-stub)

On Calling:
	Calling packet contains:
		+ Index (for fast look up at server side)
		+ ID (in case server fails, binding will be broken)
			==> user is notified if a sever crashes and restarts

Importance of ID:
	+ user will realize if a server crashes and restarts,
	don't think it is a long delay
	+ allow only exported procedure to be called
	(What if no ID? any procedure can be called at server side)

# 3. Packet level transport protocol: design for PERFORMANCE
# 3.1 Requirement
- can use existing transport protocol, but there will be performance overhead
Thus, How to design a protocol that is fast for RPC? 
- Goals:
	+ minimizing elapsed real-time between initiating call and getting results
	i.e How to make connection setup and taking down fast?
	+ minimizing load on server when there are lot of users
VS. bulk transfer:
	+ most of the time transferring data, hence setup and take down connection
	may be slow
- Semantics:
	+ if a call returns, the procedure at server has been invoked precisely once
	+ otherwise, an exception: procedure at server may be invoked once or not
		> user does not know where the server has crashed or communication break
		down
	+ as long as the server is alive, the client will wait for results
	==> i.e a call is aborted if server crash or communication break down,
	but not if server spin loop or dead lock

(how to implement this: caller probe callee after a while, and callee 
is expected to ack this, and the probe interval increase gradually)

# 3.2: how to make simple call fast?
- simple call: all arguments fit in single packet buffer
- each call packet contain:
	+ call ID
	+ binding info
	+ argument
- result packet contains:
	+ same call ID
	+ result
- acknowledgement:
	+ is implicit (hence fast)
		> result packet is ack for call packet (same call ID)
		> call packet is ack for result packet of previous call
	+ if time out, retransmission, now require explicit ack
(based on assumption: at most 1 outstanding rpc call at a time)
(well V Kernel on also assume this, the request-response/stop-wait model)
- call ID
	+ help caller to match result packet with call packet (same Call ID)
	+ help callee to eliminate duplicates (due to retransmission)
		==> hence, procedure at server is executed exactly once
	+ contains: 
		> global ID (i.e stored at RPC RT when binding)
			==> to find which procedure to call at server side
		> process info (implication: one process at caller site can call
		at a time?)
		> *monotonic* sequence number
			==> for duplicate elimination

Note: 
	- connection establishment is light weight, rely only on small amount of
	share state between caller and callee 
		(i.e Unique ID at binding time)
	- when connection is idle:
		on caller site: maintain the counter
		on callee site: entry with last caller sequence number
		now message needs to maintain idle connection
	- termination: implicit

Question: what if a caller restarted, and make a call again (of course, after
binding)? It is possible that a sequence number is repeat, hence will call
packet will be eliminate?
Solution:
- make sure that sequence number does not repeat
- use *secure calls*: i.e each call packet now contains a conversation ID,
which is uniquely assigned when machine restarts.

# 3.3 How to make complicated calls fast?
- complicated call = call with large arguments which need to broken up into
multiple packet
- require ack for each package except the last one? Why?
	+ the last one is ack by result packet
	+ simplify implementation: one packet buffer at each end
But: compare with bulk transfer, this requires as twice as many packets
(because require ack for each packet)

# 3.5 Use of Processes
- use a pool of process instead of forking on demand
	==> reduce cost of process creation
- each packet now contains process ID for source and destination
	> on packet from caller: destination is server process
	(it learn this from previous packet)
- How does this help?
	+ make ack easy:
		since call packet is forwarded to server that previously served
		that caller, it is very likely that process is waiting for a ack from
		caller, hence that new call packet server at acknowledgement
	+ in complicated call: all packet belong to that call is received by
	a single server process
	==> hence reduce the number of process switch

# 3.6 Other optimization
- bypassing software layers that correspond to a normal layer of a protocol
hierarchy
- How: modified network driver, treat RPC packet as special cases