The DQSA Research Group (DRG) reports are available in pdf form. A pdf viewer is required so click here if you don't have a pdf viewer and we'll tell you how to obtain one. The highlights of each paper are presented below -- the first time visitor will find these highlights useful in deciding which papers to view. There are animation type simulation programs that accompany some of the papers. The programs are all DOS executables and can be downloaded by clicking in the appropriate space. Some of the reports were subsequently presented in revised form at conferences, etc., and these are so identified. Click here to go directly to a list of the available papers. Click here to go directly to a list of the demonstration programs.
The seminal paper in the series is DRG Report 90-1 "DQRAP - A Distributed Queueing Random Access Protocol" by Xu and Campbell. DRG 90-1 presents the basic rules of DQRAP, the explanation of how DQRAP works, and proof that 100% utilization of the channel is achievable. A simulation program, rundq.exe, demonstrates the operation of the queues -- you will not see the "dancing Itos" but you will see the dancing queues. A subsequent revised version of this paper was presented at SIGCOMM '93 and is available in Computer Communication Review, Vol. 23, No. 4, Oct. 1993, pp. 270-278.
DQRAP technically is a blocked access protocol, i.e., a station must continually monitor the channel in order to transmit. DRG Report 90-2 describes a free access version of DQRAP in "A Free Access DQRAP for a Broadcast Channel" by Xu and Campbell. FADQRAP offers free access by operating the ubiquitous queues of DQRAP as LIFO instead of the usual FIFO. The utilization is still 100% and the average delay is still excellent but the FIFO operation does mean that at times a recently arrived packet will be transmitted after a later arriving packet. (DQRAP provides as close to FIFO performance as is practically desirable.) FADQRAP would normally be a cause for celebration in the multiple access community but as is shown obtaining the history of activity on the channel in DQRAP is trivially simple thus currently FADQRAP is on the back-burner. There is also a demo, runfree.exe, again a DOS executable, that illustrates the LIFO action of the queues. As fascinating as a Nintendo game when watching to see if some poor soul at the head of the queue ever escapes from the LIFO queue.
A protocol that utilizes control minislots in addition to the dataslot is an example of an Extended Channel Model protocol. Prior to DQRAP the best such protocol were the Announced Arrival Random Access Protocols (AARA) as described by Towsley and Vales in 1987. The description of AARA concludes with the usual statement for such protocols that "with an infinite number of minislots AARA achieves a throughput of one". Thus the reason that Extended Channel model protocols are not in general use. DQRAP is an Extended Channel model MAC but requires only three minislots. DRG Report 90-3, "DQRAP with Announced Arrival for a Broadcast Channel" by Xu and Campbell demonstrates that including an announced arrival feature still produces the great performance of DQRAP.
DQRAP divides the arrival axis into ETIs (Enabled Transmission Intervals) and all stations arriving in a given ETI contend in a corresponding CRI (Contention Resolution Interval). DQRAP is very fair in that all packets arriving in a given ETI transmit before any packet in a subsequent ETI. However packets in a given ETI might not transmit ;in a FIFO fashion, the contention resolution process could permit a later arriving packet to transmit before two packets that were busy resolving their differences. Two students in an early seminar on DQRAP asked an interesting question. "What would happen if instead of a station randomly selecting one of the three minislots the station selected a minislot relative to its position in the ETI (Enabled Transmission Interval)?" They were curious as to whether this would result in true FIFO. They answered their own question in DRG Report 90-4, "Investigation into Fairness for the Distributed Queueing Random Access Protocol" by Jim Tomaszewski and David P. Bush. They developed two variations of DQRAP: "POO" and "ZOO". You can find out about "POO" and "ZOO" by reading the paper.
DRG Report 93-1 presents analytical proof of the throughput of DQRAP. "A Performance Analysis of Distributed Queueing Random Access Protocol" by Zhang and Campbell presents the analytical proof of both the throughput and delay characteristics of DQRAP. It also provides an intuitive argument to explain the great performance of DQRAP.
The performance of DQRAP is both excellent and fair but there will always be a requirement for a priority mechanism. The next paper, DRG Report 93-2, "PDQRAP - Prioritized Distributed Queueing Random Access Protocol" by H. J. Lin and G. Campbell presents two methods of implementing priorities in DQRAP - the extra-slot (Dixon) method and the extra-bit (Lin) method. Each has its strengths (there are no weaknesses in DQRAP) and supports classical priority queueing, i.e., nothing leaves a normal priority queue while the high priority queue is occupied. A revised version of this paper was presented at the 19th Conference on Local Computer Networks and is available in the Proceedings of 19th Conference on Local Computer Networks, Minneapolis, Oct. 1994, PP 82 - 91.
The superb performance of DQRAP led us to wonder about its potential in supporting voice circuits where packets were transmitted only when was sound present. It has been well known for decades that standard voice circuits are less than 40% utilized but other than some TASI implementation in oceanic cables this phenomenon has never been fully utilized - the obvious reason is that existing MACs don't do the job. However DRG Report 93-3, "Using DQRAP (Distributed Queueing Random Access Protocol) for Local Wireless Communications" by H.J Lin and G. Campbell demonstrates just how good DQRAP is in this venue. A revised version was presented at Wireless '93 and is available in the Proceedings of Wireless '93, July 14, 1993, Calgary, Canada, pp. 625-635.
Inspiration was the starting point of DQRAP but after that simulation became the dominant player. DRG Report 93-4 "Modelling MAC Protocols in a Slotted Channel with Minislots", by M. Miramica, M. McPheters and G. Campbell, presents the details of simulating various versions of DQRAP on OPNET ™, the excellent network simulation tool offered by MIL-3 Inc. A revised version of this paper is available in the Proceedings of the Second International Conference on Telecommunications Systems, pp. 51-68, Nashville TN, March 1994.
The next report, DRG Report 93-5, "DQRAP: A Proposed Standard for the 'Last Mile' of an IEEE 802.6 MAN" by R. Khasawneh and G. Campbell was submitted to IEEE 802.6 (P802.6-93/13). Many say that this paper was a major catalyst that led to the establishment of Working Group IEEE 802.14 to define a standard MAC for HFC (hybrid fiber coax) and cable TV systems.
A crucial question about any new protocol is "How robust?" The operation of DQRAP depends totally upon the stations obtaining ternary feedback from the control minislots. Thus the questions: "What happens when the contents of the control minislots are misinterpreted?" "Are there pathological situations that make a mess of the great performance of DQRAP?" These questions are answered in DQRAP Research Group Report 93-6, "Robustness Analysis of the DQRAP Protocol." by M. Miramica and G. Campbell A hint -- performance under error conditions is nothing short than phenomenal; at error rates of up to 10% there is some increase in delay at light offered loads but as the offered load increases at the same error rate the deterioration in performance almost disappears. Read and find out why.
A companion paper to DRG Report 93-5 is DRG Report 94-1 "Criteria for a MAC Protocol Standard for the Cable Television Medium" by G. Campbell. This was also a submission to IEEE 802.6 (IEEE P802.6-94/4). Compared with the extensive criteria since produced by IEEE 802.14 this is a modest effort but does present the author's opinion of what is important.
One of the more exciting developments to emerge from DQRAP is Extended DQRAP (XDQRAP). DQRAP utilizes control minislots that permit stations to reserve a single slot and to resolve contention. The goal was and is to keep the minislots as small as possible since despite their goodness they are overhead. Thus it is counter-intuitive to do anything that increases the size of the minislot. But that is what we did in DRG Report 94-2, "Extended DQRAP: (XDQRAP) A Cable TV Protocol Functioning as a Distributed Switch" by C. T. Wu and G. Campbell. In XDQRAP stations can reserve up to 256 slots in one trip to a minislot. There are two major benefits: (a) the SAR (segmentation and reassembly) process, always necessary in a system using fixed size data slots, does not require the individual segments to be encapsulated ala ATM. The second benefit (b) provided by XDQRAP is that using just two minislots provides the performance we love so well. A demo program, xdqrap.exe, accompanies this paper. The program simulates an offered load of greater than 80% and yet the viewer requires patience when waiting to observe a collision in a minislot. A revised version of this report was presented at the 1st International Workshop on Community Networking held in San Francisco in July 1994, and is available in the proceedings of that workshop.
The previous paper describes how XDQRAP works and presents simulation results. DRG Report 94-3 "The Extended DQRAP (XDQRAP) Algorithm" by C. T. Wu and G. Campbell provides the algorithm written in pseudo "C" that shows the details of XDQRAP.
In networks where "a" >0.5, i.e., feedback is not available immediately at the end of the slot, interleaving is used to compensate for the increased propagation delay. Interleaving establishes multiple protocol engines operating in parallel. The problem is that one engine could have a queue of waiting transmissions while other engines would not be utilized. DRG Report 94-4 "Interleaved DQRAP With Global TQ" by C. T. Wu and G. Campbell describes how a single global TQ can suffice providing much improved performance.
DQRAP is a generic MAC suitable for all topologies and networks of any value of "a", i.e., from LANs to WANs. We coined the name DQLAN to describe DQRAP in a LAN environment where "a" < 0.5, i.e., feedback is available at the end of the current data transmission. DRG Report 95-1, "DQLAN - A DQRAP Based LAN Protocol", by C. T. Wu and G. Campbell tells all. This report compares the performance of DQLAN with Ethernet and needless to say Ethernet comes out a poor second. Again a demo, dqlan.exe, accompanies this paper to illustrate the operation of DQLAN. This program permits the user to enter a request for a transmission from a particular station by hitting the corresponding numeric key. A revised version of this paper is available in the Proceedings of HiNet '95, a symposium held in conjunction with the 9th International Parallel Processing Symposium, Santa Barbara, CA, April 1995.
A previous paper describes XDQRAP as a distributed switch. DRG Report 95-2 "CBR Channels on a DQRAP-based HFC Network" by C. T. Wu and G. Campbell treats DQRAP as a distributed ATM switch. CBR (constant bit rate) channels generally support synchronous links such as phone circuits thus are "taken off the top". We are thus more interested in the performance of random traffic that utilizes the remaining capacity and this is described in this paper. The important contribution is the demonstration that ATM can be deployed so as to collect cells directly from users at the edge of the WEB. This overcomes the one glaring weakness of ATM that requires all data to be collected in another form and then brought to centrally located switches for the actual routing.