Implementing Remote Procedure Calls

Andrew D. Birrell & Bruce Jay Nelson

ACM Trans. on Computer Systems, 1984, pp 39-54

1. Introduction

1.1 Background

RPC idea: Use the same mechanism to pass control and data across network as function calls within a single process
Simple and clean semantics
Efficient: ?
Lots of paper works on RPC but no extensive effort to implement it
semantics of a call in the presence of machine and communication failure
semantics of address-containing arguments in the absence of a shared address space
integration into the existing (or future) programming systems
network protocol
data integrity and security

1.2 Environment

Relatively powerful personal computers (Dorado) are connected together by interconnection of Ethernets
Most communications are within Ethernet. Slow internetworking causes little problem
Only high-level language (mainly Mesa) is available to program
PUP network protocol family has UDP-like, TCP-like, and raw Ethernet protocol

1.3 Aims

Make distributed computing easy: let the programmer focus on fundamental difficulty of distributed computing: timing, independent failure of components, ...
Make RPC communication highly efficient: don't distort program by making programmer avoid communication due to its slowness
Make the semantics of RPC as powerful as possible without loss of simplicity or efficiency
Provide secure communication

1.4 Fundamental Decisions

Why the procedure call as the paradigm for expressing control and data transfer? For example why not message passing?
Function call is the major control and data transfer mechanism in Mesa, and still true for modern languages
Why not shared virtual address?
They argues that shared virtual address is not cost-effective and adding this semantics could hurt efficiency
One big principle: make RPC semantics as close as possible to those of local procedure call, even some important features of distributed computing, such as timeout, are eliminated

1.5 Structure

Component of remote procedure call: user, user-stud, communication package, server-stub, server
user places normal local call
user-stub does binding and makes packets with procedure call and arguments
communication package transfers the packets reliably
server-stub unpacks the packets and call server as a local call
server-stub packs the result of local call
communication package transfers the result packet
user-stub unpacks the packet and pass the result to user
All communication is done in blocking mode
Absolutely the same semantics of local call: if user and server are brought to a single machine and bound together, they will work!
Distributed programming in RPC
write interfaces, like *.h file
write the server which implements those interfaces
write the client which calls those interfaces
pass the interfaces to Lupine, which then generates user-stub and server-stub
=> No network programming at all!
However the programmer needs to pass information needed for binding and be prepared to handle machine or communication error

2. Binding

Issues about which function of which machine should be called when the caller places a function call
How to name an exporter and how to locate the exporter, given a name

2.1 Naming

Binding operation: bind an importer of an interface to an exporter of the interface
How to name the function X on machine Y
Name with type and instance
Type: which service the caller expects the callee to implement
Instance: which particular callee should be called

2.2 Locating an Appropriate Exporter

This system uses Grapevine distributed database
Both of type and instance are represented by RNames of the same registry, i.e. entries in the single logical database
Type: group entry whose members are RNames of instance of the type
Instance: individual entry which represents a host which exports the interface
Export & Import
server calls Export(type, name) -> server-stub calls ExportInterface(type, instance, ...)
-> update the database: add the instance as a member of type RName
-> stash information about export, including a unique id, into a table inside server-stub
client calls Import(type, name) -> user-stub calls ImportInterface(type, instance, ...)
-> do database query to get ip-address of the exporter
Contact any registry server and get a registry server for RPC registry
Get the member (= the exporter) of the type RName from the RPC registry
-> contact the exporter -> exporter replies with the unique id and table index
-> ip-addr, id, table index are stashed in user-stub
-> After binding, all RPC packets from caller to callee have these information
-> Server-stub uses the table index to check the id and call the appropriate function
Binding to any server
client calls Import(type) -> user-stub gets all member of the type from the database -> tries in turn in the order of ...
Binding without using Grapevine
client calls Import(type, ip-addr) -> user-stub contacts server-stub directly using the ip-addr

2.3 Discussion

Stateless server and stateful client
Import affects exporter nothing => server is stateless about client => server is scalable & don't need to worry about client crash
Client is kind of stateful about server: export id -> server crash in between calls can be detected by server
Who can export an interface? ACL of Grapevine: only authorized users (or hosts) can update the group entry
Flexible binding time
binding with only type - dynamic binding
binding with instance RName: actual machine can be determined at the time of export not compile time
binding to ip-addr: actual machine is determined at compile time

3. Packet-Level Transport Protocol

3.1 Requirements

Why not general byte-stream protocol like TCP?
Latency is more important than bandwidth: connection establishment & tear-down should be light-weight
To service many clients at the same time, server should not maintain much state information of connection
The semantics of RPC procedure should be provided at this level
For example, retry can result in multiple execution of server function
-> As long as the communication package at server responds, user-stub should not return fail

3.2 Simple Calls: Every argument and result fits in a packet

call packet: call id + procedure (export id, table index) + argument
return packet: call id + return values
The capacity of network pipe is basically one packet (stop-and-wait) = only one RPC call outstanding per process
call id = machine id + process id + monotonically increasing sequence number:
to map the result packet to the correct call: delayed result should be dropped on the floor
to avoid calling server function multiple times in case of retransmission
Session: call packet -> result packet
No connection setup & tear down
Result packet is used as the ack of call packet
The start of the next session (identified by the call id) is used as the ack of result packet

3.3 Complicated Calls

Packet loss -> retransmission of modified packet with request for explicit ack
Call with long arguments or result
Packets except last one are sent with explicit req. for ack
Ack for the last arg packet = result packet
Ack for the last result packet = the next call packet
Flow control: stop-and-wait
=> Not a good way to send bulk data <- tuned to work best with simple calls
Long duration packet
Seems like the loss of the last arg packet to caller -> retransmission with explicit req. for ack
After getting ack for the last packet, caller keeps sending probe packet to assure that the callee is still working
Timer to send probe increase gradually
Long gap between calls
Seems like the loss of the last result packet to callee -> retransmission with explicit req. for ack
One possible enhancement: RPC protocol for simple calls & TCP for complicated calls

3.4 Exception Handling

MESA exception handling: Java-like exception handling
RPC supports MESA exception handling
Exception arises -> callee returns an exception packet instead of result packet
-> RPCRuntime on caller raises the exception to the client process
-> User handling procedure executed or terminate process
-> Return value of catch procedure is returned to callee or notifies callee about abort
-> Callee process resumes its execution or unwind its call stack
RPCRuntime may also raise exception to notify a communication difficulty

3.5 Use of Processes

Context switch is usually 10 times slower than procedure call. But remote procedure call incurs creation and context switch at server side -> Pool of pre-forked processes to reduce the overhead of process creation & Hacking to reduce context switch

3.6 Other Optimizations

Cheat by modifying network drive to handle RPC packets special: skip all layers between RPC & layer 2

3.7 Security

Authentication: use Grapevine as a key distribution center
Encryption: use federal encryption standard


Specialized network protocol to reduce latency. Reliable protocol with no connection setup & tear down.
Flexible binding methods
Exception handling
Why not use TCP for bulk data transmission
Lots of hacking to boost speed up
No congestion control aggravates congestion