Real-Time Ethernet

In the early 90's, as multimedia traffic was just starting to be deployed on IP networks, the real time characteristics of networks was an important problem.  The TENET research group at Berkeley, headed by my dissertation advisor, Domenico Ferrari, pioneered a good deal of the research in this area.  As part of this group, I took a look at the problems of real-time traffic on CSMA/CD shared Ethernet LAN segments.  I found that CSMA/CD networks are particularly bad for real-time traffic, because of the packet starvation effect, which causes some packets to receive latency 100 or more times the average latency, and creates packet loss starting at an offered load of only 60%.   We both quantified this, and proposed a solution called FDDQ that solved the problem.  FDDQ maintains two virtual queues, a high priority and a low priority one, and provides first come first served access to the network.  It provides utilizations and average latencies very similar to CSMA/CD, while eliminating the packet starvation effect, and providing real-time guarantees to packets on the network.  The protocol is stable for a constant number of senders, is only slightly more complicated than the CSMA/CD algorithm, and could be implemented in firmware.  Unfortunately, given the near ubiquitous nature of Ethernet networks by that point, it would have been very difficult to get the standards bodies to accept it, and so I accepted that it wasn't commercially viable, and moved on to other topics.

The Packet Starvation Effect in CSMA/CD LANs and a Solution (.pdf)

Fast Track Packet Processing

In the spring of 1995, I worked on a project to optimize the latency of RMP and TCP.  With the help of Malik Kalfane, Todd Montgomery, and some other students, we designed a fast track packet processing architecture, instrumented and optimized a HP-UX kernel, and showed that we could reduce the latency of a UDP packet (not including time spent in the physical transmission) from 2 msec to 20 microseconds, as long as packet losses and out of order packets were avoided by the physical network.  We also calculated that RMP could be reduced to 200 microseconds latency.  This paper was never published, as other researchers beat us to publication, but was a fascinating experience in learning how a few small changes in software could drastically optimize the performance of a software system.  

Abstract:  This paper proposes a fast track architecture for handling the common case of the UDP/IP protocol stack with very high performance.  When combined with one of the new fast, fault-tolerant, reliable multicast protocols (such as RMP or Horus) which are implemented in user space, this architecture will support totally ordered reliable multicast messages with a user-user latency of approximately 200 microseconds, irregardless of the number of destinations of the message.  Simpler reliable transport protocols such as TCP/IP will be able to achieve latencies of 10-50 microseconds with this architecture.  This architecture will increase the current 13 Mbps RMP has achieved on FDDI rings to a speed limited only by the speed of memory copies on the bus.  This latency is one to two orders of magnitude better than that of current totally ordered multicast protocols, yet it is fully compatible with all other IP implementations. 

The main points of the architecture are an early demultiplexer called by the hardware device driver and a fast track for the common case packets which almost completely bypasses the operating system.  This performance is achieved without sacrificing protection between user processes.

RMP Security and Transaction Support

As part of the efforts to commercialize RMP, we specified one of the first multicast authentication protocols, but did not publish this.  We also showed how RMP could provide high speed distributed transaction support, that would be roughly constant in performance for groups of up to 100 copies of a database simultaneously committing this transaction.  However, it became clear that this did not have commercial value, and we didn't publish this.  Both were fascinating experiences, however.

Application Layer Multicast

At GlobalCast, we designed and implemented the first scaleable application layer multicast system that I know of, called the Multicast Distribution System (MDS).  Analysis and testing showed that the system scaled to tens of thousands of groups, each sending to thousands, if not tens of thousands, of simultaneous receivers.  MDS supported a combination of RMP, TCP, and RMTP-II protocols, in an adaptive fashion.  It organized servers in to a tree-based hierarchy, which provided scalability, but also provided a single potential bottleneck and point of failure.  This was released commercially in 1996, but we never published any academic papers on it, because it was proprietary. 

Talarian acquired GlobalCast in 1999, and we found that they had also built and deployed, a highly successful application layer multicast product, called SmartSockets.  As of early 2002, SmartSockets is the most globally scaleable deployed ALM system.  I led the design of the next generation architecture for SmartSockets, with Girish Kumar, Jim Stabile, Brad Cain, Radia Perlman, and others.  This new architecture is unfortunately proprietary as well.

Copyright © 2005 Brian Whetten
Last modified: 04/21/05