Friday, January 16, 2009

Asynchronous Internet Programming

Programming an Internet application requires several asynchronous events such as network events, file I/O, timers and user interactions. In this article I walk through some existing design patterns for asynchronous programming.

Most programmers think synchronously, i.e., in a single control flow. For example, in a web server implementation, a socket is opened for listening, and when an incoming connection is received it accepts the connection, receives the request, and responds to the client. There are several steps in this flow that can block, e.g., waiting for incoming connection or incoming request. If a resource such as thread or process is blocking, it causes inefficiency in the overall system design. For example, if one thread is blocked serving a request from one client, another thread needs to be created to serve request from another client. Creating a thread-per-request causes too many thread creation and deletion in the system when the request-per-minute load increases.

Event handlers:
The first approach is to break your program into smaller chunks such that each chuck is non-blocking. Then use a event queue to schedule these chunks. The earlier windows programming (WinProc) falls under this category. The main loop just listens for the events on an event queue. When a user input is received such as mouse movement, click or keyboard input, a event is dispatched to the event queue. The event handlers installed in the program handle the events, and may post additional events in the queue. External events such as socket input can also be linked to this event queue. One problem with this design is that several event handlers need to share state (hence global variables) which results in complex software.

while not queue.empty():
msg = queue.remove(0)
dispatch(msg) # calls the event handler for msg

Some event-driven programming languages such as Flash ActionScript enforces this event handler design practice coupled with object-oriented design. Typically, in ActionScript, individual object has event queue and can dispatch events, instead of exposing a global event queue to the programmer. An object can listen for events from another object, e.g., a controller program can listen for click event on the button, and handle it appropriately. Thus, there can be some data hiding, information separation, and better software design using event handlers. In other languages (C++) libraries such as Poco that facilitate event driven object oriented programming. Nevertheless, one problem with this design is that logically similar source code needs to be split across different functions and methods, and sometimes different classes. For example, a timer event handler defined as a separate function from the timer initialization code.

button.addEventListener('click', clickHandler);
...
function clickHandler(event:Event):void {
...
}


Inline Closures:
Java as well as ActionScript solve this problem using inline closures. In particular, you can define event handlers inline within a method definition, thus keeping the logically similar code together in your program file. However, this is not always possible, e.g., if the same timer needs to be started from several places in the code. In this case, it does make sense to keep the timer handler as a separate method.

timer.addEventListener('timer', function(event:TimerEvent):void {
... // process timer event
}


Deferred Object:
Twisted Framework solves this problem using the Deferred Object pattern. The idea is as follows: instead of breaking the control flow source code every time a blocking operation occurs, the source code is broken when the result of the blocking operation is needed. This makes a lot of difference in programming, and makes the software cleaner. For example, earlier when a socket connection was initiated we needed to install an event handler for the success and failure result and perform the rest of the processing in those event handlers. Now, using the Deferred Object pattern, the socket.connect returns a deferred object, which is used in the same control flow as if it were a result of the connect method. The result object can be passed around elsewhere like a regular object. Only when we need to do something on completion of the connection, we wait on the result object'. This can be done either synchronously using result.wait() or asynchronously by installing a success and error callbacks. Provisions are there to allow one deferred object to wait on result of another deferred object before proceeding. An example follows:

result = socket.connect(...)
result.wait()
if result:
... # connection successful


Co-operative multitasking:
Python's multitask module allows cleaner source code by taking advantage of co-operative multitasking. The idea is to build application level threads of control which co-operate during blocking using the built-in yield method. A global scheduler runs in the main application. I find this to be the most clean design in my programming. An example follows.

data, addr = yield multitask.recvfrom(socket, ...)
yield multitask.sendto('response', addr)


One major problem with these approaches is that because of the inherent underlying single event queue software architecture, we cannot take advantage of multi-processor CPU architecture easily. Thus, we must use multi-threaded design in our software. Most of the earlier designs can be extended to multi-threaded application with some care. For example, one can run multiple global event loops listening on a single shared and locked event queue or one event-queue per thread where the dispatcher schedules it to the appropriate thread's queue. Clearly, the first one is more efficient from a queuing theory perspective. Care must be taken to lock the critical section in event handlers, or control flow that may get accessed from different threads at the same time.

Consequently, we get several multi-threaded designs: thread-per-request, thread-pool, two-stage thread-pool, etc. The performance comparison of these designs in the context of a SIP server is shown in my paper titled Failover, Load Sharing and Server Architecture in SIP Telephony, Sec 6.

Thursday, January 15, 2009

Programming languages for implementing SIP

The programming language used for the implementation can affect the software architecture. For example, Flash ActionScript is a pure event-based language with no way of implementing a blocking operation. Hence, when a connection is made on a socket object, the socket object will dispatch the success or failure event. The caller installs the appropriate event handlers to continue the processing after the connection is completed.

C
There are two main reasons for implementing SIP in C: ability to compile on several platforms and very high performance. The primary advantage of implementing a SIP stack in C is that it can be easily ported and compiled on variety of platforms especially embedded platforms. Usually a C compiler is available for a platform, whereas others such as Java interpreter or C++ compiler may not be. Secondly, because there is no overhead (e.g., in terms of run-time environment and code size), the performance is usually the best. The main problem with implementing a SIP stack in C is the development time and cost of maintenance of the software. Finding bugs and adding a feature in a C program is usually more challenging than other languages. However if the software is well designed then the problem can be alleviated to a large extent. In any case, the number of lines of code that needs to be written in C is usually much more than the other high level languages such as Java or Python.

The pjsip project presents an implementation of SIP and other related protocols. It has been used in a variety of real-world projects and has proven itself to be a good SIP implementation especially where performance matters or the resources are limited.

C++
The object oriented design allows better reusability and maintainability compared to programming in C. However, the number of lines of code is still large. If advanced C++ features such as standard template library (STL) are used then portability may become a concern for certain embedded platforms.

One of my earlier SIP implementation was in C++ (and C) at Columbia University. Another example implementation is reSIProcate, an open source SIP stack.

Java
The Java programming language is very popular among corporate world and enterprise application developers. The standards community has developed APIs that cover several aspects of SIP implementation and some of its extensions. This allows the application to be built against those APIs whereas the actual implementation of the SIP stack can be provided by several vendors. The main problem with an implementation written in Java is that it tends to be too verbose. Java on one hand gives the illusion of a very high level language, but on the other hand requires the programmer to write a lot of code even to do a small thing. Part of this is because of the way the language is defined -- in particular the exception handling and strict compiler enforced type checking. This requires the programmer to do a lot of typecasting and hence there is potential for run-time errors. Another problem with Java is that the run-time could become a memory hog.

NIST SIP Stack provides the reference implementation of the JAIN SIP API.

Tcl
The Tcl programming language is not as popular as the other high level languages such as perl, PHP or Java. However, because of the simplicity in the language construct it is very easy to learn. Unless the software is designed right, it becomes very difficult to maintain a large piece of software.

Columbia’s SIP user agent, sipc, is written in Tcl.

ActionScript
ActionScript (or ECMAScript 4), improves on the Java programming language by allowing much smaller source code size of the implementation and much shorter syntax for common operations. However, there are two major limitations: the platform is limited to Flash Player or AIR (Adobe integrated run-time) and the language is purely event-based. The limitation of Flash Player may not seem important at the beginning, but prevents certain features. For example, the current version of Flash Player doesn’t have UDP or TLS sockets that could be used for SIP. Even the functions of a TCP socket is limited in that you can only initiate connections but cannot receive incoming connections. This prevents us from implementing a complete SIP stack in ActionScript without support from Flash Player or an additional plugin. The Flash Player version for embedded devices is usually older than the current version which makes portability an issue. Because of the run-time overhead the performance is limited. The media codecs supplied by the Flash Player 9 or earlier are proprietary codecs that are usually not supported by any other implementation. This causes interoperability issues as well.

Python
The object oriented nature, the compact coding style and very small source code size of the implementation makes Python a very good choice for implementing application protocols such as SIP. There is some overhead because it is an interpreted language; however the overhead is comparable to that of Java run-time. The interpreter is now usually available for embedded platforms as well, making it more portable than other languages such as ActionScript or C++.
The biggest advantage of an implementation in Python is that the code size is drastically smaller than other languages. I have implemented the basic SIP stack in less than 2000 lines of Python source code. Compare this with the Java implementation of SIP which has more than 1000 files. The lower size means that not only the development time is smaller, but also the testing, code review and maintenance cost is much lower.

P2P API

In this article I describe several sets of APIs for P2P. For a software engineer, designing a good API is very important. A good abstraction of the underlying concept leads to a good API. For example, the data model of storing key-value pair in a P2P network is usually abstracted as a hash table. Programmers like seeing existing semantics in an API because they are already familiar with those semantics. This article uses API ideas from OpenDHT, JXTA, Adobe Flash Player, and IETF P2P-SIP draft.

A good API
  1. should take the form of use-cases
  2. is very general and concise: does one thing and does it well
  3. is self-explanatory and is similar to existing concepts, models, practices
  4. is independent of implementation details
At the high level, there are three abstractions for P2P APIs: data storage, peer connectivity and group membership. There are several special cases among these abstractions.

Data Storage
A distributed hash table (DHT) is a form of structured P2P network with data stored using hash table abstraction. In particular, it provides put, get and remove API methods. Programmers are familiar with container semantics of hash-tables. In Python, this looks like:

a = DHT()
a['key1'] = 'value1'
print a['key1']
del a['key1']

Let us apply this to a use-case of P2P-SIP user location storage. In particular, the key is the user identifier of the form 'kundan@example.net' and value is the user location of the form 'kns10@192.1.2.3:5062'. With this we see several problems in the existing container semantics of the API listed above. Firstly, a user can have several locations, in which case a call request is sent to all those locations as in SIP forking proxy behavior. The following modification to the API causes more confusion because set takes a single value whereas get returns multiple.
a['kundan@example.net'] = 'kns10@192.1.2.3:5062'
print a['henning@example.net'] # prints all contacts of henning

To solve this we can assume a 'set' semantics for a[k]
a['key1'] += 'value1'
a['key2'] += 'value2'
print a['key1'] # print a list of values
a['key1'] -= 'value1' # remove specific key1-value1
del a['key1'] # remove all values for key1

Another problem is that this API is not secure or authenticated. A secure DHT API based on public-key infrastructure can sign the stored value on set and del.
a = DHT(privatekey=...)   # supply the private key of the owner
print a['key1'] # print all values for given key
print a(owner=...)['key1'] # print values only by given owner
A third problem is that the API is not extensible to pure event-based languages such as Flash ActionScript. In ActionScript, there are no blocking operations, hence set and get much be defined asynchronously. ActionScript already has SharedObject abstraction to deal with remote shared storage of objects. This can be reused for the API as follows:
so = DistributedSharedObject.getRemote(privatekey=...)
so.setProperty('key1', 'value1') # sets the key1-value1 pair
so.retrieve('key2') # initiates get
so.addEventListener('sync', syncHandler)
so.addEventListener('propertyChange', changeHandler)
function syncHandler(event:SyncEvent):void {
... # put is completed
}
function changeHandler(event:PropertyChangeEvent):void {
if (event.property == 'key2') # get is completed
trace(so.data['key2'])
}

Another problem is that the API doesn't take into account the time-to-live of key-value pair. This can be solved by supplying a default timeout in the constructor.
d = DHT(privatekey=..., timeout=3600)   # default TTL of one hour

Note that a data storage API can be built on top of a routing and connectivity API. Since we would like to separate the abstractions (data storage and peer connectivity/routing), we will define separate sets of APIs for these.
d = DHT(net=..., .privatekey=..., timeout=...) # use the given connectivity (net) object

Peer connectivity and routing
The connectivity and routing layer deals with maintenance of P2P network. Programmers are familiar with socket abstraction and there has been effort to map P2P to socket abstraction [2].
s0 = ServerSocket(...)  # a P2P node is created
s0.bind(identity=..., credentials=....) # node joins the P2P network
The bind method is similar to the JXTA semantics, and similar to the attach method as proposed in IETF P2P-SIP work. Actual communication with a specific peer can happen over a connected socket. A connected socket is returned in the connect or accept API methods on the server-socket.
s1 = s0.connect(remote=...) # connect to the given remote identity
s2, remote = s0.accept() # receive an incoming connection from remote
The connection procedure takes care of negotiating connectivity checks using ICE (or similar algorithm) to allow NAT and firewall traversal.

Once connected, the socket can be used to send or receive any message to the peer.
s1.send(data=..., timeout=...)
data = s1.recv()
The original server-socket can be used to send or receive messages to specific peers without explicit connection.
s0.sendto(data=..., remote=...)  # send to specific peer
data, remote = s0.recvfrom(timeout=...)
Sometimes, a node needs to send a message to any available node close to a given identifier. This can be implemented using overloaded sendto method that takes either a remote address or a key identifier. The latter performs P2P routing to the given destination key identifier.
s0.sendto(data=..., key=...)
data, remote, local = s0.recvfrom(...)
if local == s0.sockname: # received for this node identifier
...
else: # received to the given key presumably close this node
key = local
A connected socket can be disconnected or a node removed from the P2P network using the close method.
s1.close()  # close the connection
s0.close() # remove the node
These abstractions allow building a distributed object location and routing APIs [1] using locality aware decentralized directory service.

Group membership
Group membership APIs are similar to the multicast and anycast socket APIs. A node can join or leave a group, and a message can be sent via multicast or anycast to one or more nodes in a group. Let us define a group identifier similar to that in JXTA. We extend the previous socket abstraction to create a new group.
s3 = s0.join(group=...)  # join a given group
The join method returns a semi-connected socket object which can be used to send or receive packets on the given group.
s3.send(data=...)        # send to every node in the group
s3.sendany(data=...) # send to at most one node in the group
data, remote, key = s3.recv() # receive a multicast or anycast data
The socket API gives an intuitive abstraction to understand the P2P concepts. The actual implementation of the group membership may be more complex than simple routing and connectivity. Closing a group socket leaves the group membership.

We have seen how a P2P API can evolve to accommodate various concepts into existing well known abstractions such as hash table and socket.

References:
1. Towards a common API for structured peer-to-peer overlays (2003) http://oceanstore.cs.berkeley.edu/publications/papers/pdf/iptps03-api.pdf
2. The Socket API in JXTA 2.0 http://java.sun.com/developer/technicalArticles/Networking/jxta2.0/