DQSA and Universal Networking

A White Paper
by
Graham Campell

Introduction

DQSA (Distributed Queue Switch Architecture), a patented technology [1], represents a fundamental development in network switching in that it efficiently switches synchronous and asynchronous traffic without central control – all control resides in the network nodes, eliminating the need for routers. DQSA can utilize virtually any type of physical signaling on any type of physical medium while supporting data presented in any of the popular framing protocols such as Ethernet, IP, MPLS, Frame Relay, or ATM. DQSA provides a level of service superior to that currently available in wireless, satellite (LEO and GEO), wired (LANs, MANs, and WANs), and fiber-based networks. DQSA provides the basis for the universal switching of all information over all media using a common format such as Ethernet or IP datagrams.

DQSA’s simultaneous switching of asynchronous and synchronous traffic is of importance today as virtually all traffic is now packet-based but must travel over an infrastructure that is totally synchronous. In WANs the problem is that despite extensive development since the advent of the predecessor of the Internet, asynchronous switching has failed to satisfy either economic or performance requirements. This has resulted in the establishment of asynchronous networks that typically interface with the users but that then in turn utilize synchronous facilities that include SONET, SDH and optical switches. DQSA can utilize the existing synchronous network almost as is to efficiently carry asynchronous traffic between source and destination(s) [2].

In the wireless area where shared usage of a common channel is a requirement, the lack of an effective access method has meant that systems must use either asynchronous solutions of low utilization such as variants of slotted Aloha or accept the requirement of “nailing up” a synchronous circuit to support what is almost universally intermittent asynchronous traffic. The best example of this later use is a typical cell phone system where when a call is established a circuit is physically set-up between the remote node and the hub, a circuit that is maintained even when a party is not talking. DQSA-based wireless systems enable packets to be transmitted individually by a multitude of stations over a common channel such that 100% of the available data slots are utilized. Under overload conditions full utilization is maintained along with fair queueing for waiting callers.

Features of DQSA Switching

The ideal switch supports three functions: (1) asynchronous switching (data is carried in individual packets where time to travel (latency) once the circuit is established can vary from packet to packet, (2) synchronous switching, where latency does not change and (3) priorities. Synchronous switching has been with us since the time of Alexander Graham Bell; asynchronous switching evolved to satisfy the requirement of computers to transmit in short bursts, and priorities are still evolving. Asynchronous switching and priorities present the greatest problem for current switching technologies, the main reason that no current switch supports the three required functions. This section describes how DQSA supports each of these desirable features. Subsequent sections discuss implementation considerations and potential applications.

1. Asynchronous Operation:   DQSA solved the fundamental problem that bedeviled researchers since the development of the first MAC (medium access control) method, i.e., Aloha. That problem was how to sort out requests for service when there was no apriori information. DQSA accomplishes this by (1) allocating a portion of the bandwidth that enables stations to request service and (2) utilizing an elegant algorithm and two distributed queues that support respectively successful requests and to quickly resolve collided requests [3]. Variable length packets are divided into fixed-length segments, typically 64 bytes; the segments do not require encapsulation. When offered traffic follows a Poisson distribution for both length of packet and interarrival time, DQSA performance is close to the ideal. The algorithm is applicable over any distance and at any speed.
2. Synchronous Operation:   As stated in the previous section, DQSA is implemented over a channel that is divided into fixed-size slots. The fixed-size slots make it possible to dynamically allocate to a specific station the exclusive use of a slot on a repeating basis establishing what is in effect a TDM channel. All stations are aware of this allocation and when a station reaches the head of the queue it will defer transmitting if the next slot has been allocated [5]. The asynchronous and synchronous traffic can thus be intermixed. When 100% of the slots are allocated to synchronous operation, DQSA functions as a conventional synchronous switch.
3. Priorities and QoS:  One of the most difficult facilities to implement in networks is the ability to assign priorities to data. In DQSA priorities are implemented using the same mechanism as is most commonly used in operating systems, i.e., using separate queues and dispatching a packet from a lower priority queue only when higher priority queues are empty. This is possible because of the distributed nature of the control in DQSA. A single bit need only be added to a request to ensure that the requesting station operates from a queue separate from the regular queue. N bits allow 2^N levels of priority. Furthermore as with priorities in operating systems preemption is supported. For instance a station could be in the midst of transmitting an IP packet of several thousands bytes length. DQSA segments the packet into fixed-size chunks (no overhead on the segments) so that when a station with higher priority requests service the sending station can immediately suspend transmission [6].

DQSA can be implemented directly using variable length packets [9] but the preferred method of implementing DQSA is to utilize fixed-size data slots as described above. There are two versions: one that in addition to the data slot utilizes bandwidth for three request slots per time slot [3] and one that utilizes bandwidth for two request slots [4]. The two-slot version, XDQRAP, is the more versatile since a packet, e.g. an IP packet, can be segmented without requiring overhead on each segment. The three-slot version, DQRAP, requires that each segment be identified and so is ideal for switching ATM cells.

Using a combination of synchronous channels and priorities virtually any level of QoS can be supported by DQSA. A plus is that multicasting and broadcasting are possible with no extra complexity or cost.

Implementation Considerations

Simplicity: DQSA provides possibly the ultimate in a switching environment but an even greater plus is the simplicity of implementation. DQSA can be implemented with simple four-state logic plus two binary counters at each connected station. No central controller or even central node is required. However many networks utilize the equivalent of a star topology, e.g. wireless, or tree-and-branch topology and so if a central node is available it can be utilized by DQSA. At the simplest level the central node in a DQSA environment need only copy incoming requests and transmit same to the attached stations. Logic can optionally be included at minimal incremental cost at the central node that strengthens even further the already robust DQSA [11].

DQSA utilizes conventional transmission of packets over already existing physical layer transmission/receiving infrastructure. The simple logic described in the previous paragraph acts a gate that passes packets/segments to the transmission hardware when one of the above mentioned binary counters reaches zero. The requests for service involve the transmission of small amounts of data, something less than 24 bits. The overall utilization in a given environment will be dependent upon the type of modulation/signaling and will range from 85% in some wireless environments to greater than 98% in a synchronous environment.

Hand-off: Mobile wireless environments such as cell phone systems are subject to the normal atmospheric disturbances but in addition users can be in motion so they must transfer from one base station to another; the procedure is called hand-off. LEO satellite systems have the same problem excepting that it is the “base station” that moves out of range and the users remain stationary. DQSA’s utilization of packets provides natural intervals that simplify the hand-off.

Synchronization: All stations synchronize at both the MAC layer and the PHY layer.

A beacon is broadcast each slot-time by either a station or a central node to provide synchronization at the MAC layer. Feedback from requests made in a previous slot-time is provided with each beacon; each station utilizes this feedback to calculate the state of the network, i.e., the length of the global queues. This state of the network can also be provided along with the feedback so that stations can compare their self-determined state of the network with a centrally calculated value, further improving the robustness.

The PHY layer synchronization is straightforward. When a central node is utilized, the usual case, the outbound channel has continuous transmission thus the carrier is available for synchronization.

DQSA is an access method that operates over any distance. A virtual network is established wherein all stations are moved virtually so that they appear to be the same distance from a central node. Conventional ranging methods are used to establish the physical location of each station so that the virtual distance that each must be moved can be calculated.

Control: A central controller is not required, all decision making is carried out at the user nodes. The sole responsibility of a central node is to receive requests for service from user nodes and to then transmit the feedback to those user nodes

DQSA Applications

The term universal has been used in describing the potential of DQSA. The list of applications presented below, presented in four groups, justifies the use of that adjective.

• Wireless:

1. Cell Phone:   Current technology necessitates the establishment of the equivalent of a dedicated full-duplex circuit for the duration of the call even though conversation is half-duplex. DQSA can more than double the number of voice circuits supported by utilizing space between words in addition to efficiently supporting half-duplex conversation [8]. DQSA continues to operate at 100% utilization even under overload conditions and with its fair queueing would not suffer from the overload breakdown that afflicted cell systems during the recent East Coast blackout. DQSA works equally well with both conventional carrier modulation and with CDMA [10].

2. Broadband Wireless Access (BWA):   Internet access is increasingly being provided by means of fixed wireless. Current systems typically utilize IEEE 802.11 based protocols but the recently introduced IEEE 802.16 specifically addresses that market. An independent investigation has verified that when offered traffic follows a sporadic pattern, e.g., Poisson, throughput is double that of IEEE 802.11b [7]. One operator of an existing wireless based Internet access system, after studying the performance of DQSA, is confident that they could triple their revenue for a given bandwidth usage by a combination of increased utilization and premium QoS services. The DQSA priority facility supports background transmission of low priority traffic that ensures 100% utilization of revenue generating data slots, with no impact on performance of high priority traffic. DQSA works well with all carrier mechanisms including OFDM as specified for IEEE 802.16.

3. GEO Satellite:   The distributed nature of DQSA makes it particularly suitable for GEO satellite networks. Conventional GEO systems utilize the satellite as little more than a transponder resulting in a minimum of two up-and-down trips for a user to request service. Using DQSA the satellite still acts as little more than a transponder in that requests for service are “turned around” at the satellite and transmitted back to the ground stations where the distributed control of DQSA determines which station transmits. In addition to the full utilization of the dataslots and asynchronous and synchronous capability, access time is reduced by 50%. This halving of the 240 ms round trip to a ground base station to 120 ms provides a qualitative improvement in service for interactive access using a GEO network.

4. LEO Satellite:    The hand-off capability of DQSA required for LEO service was described previously. Another feature of DQSA particularly suited to LEO networks is the ability of DQSA to efficiently take an inventory. Assume that in a military operation there is a total of 100,000 troops, vehicles, and other objects, each equipped with GPS-equipped radio, in the service area of a passing satellite. Assuming a 10 Mbps data rate and a 80 microsecond time slot a DQSA-equipped satellite will obtain a complete inventory/roll call in approximately 100,000 x 80 x 10^-6 = 8 seconds. The implementation of CDQ (Cascaded Distributed Queue), another member of the DQSA family, in the satellites themselves provides all the DQSA features on a world-wide basis.

• Terrestrial:

1. Synchronous:    Despite the fact that virtually all traffic is increasingly packet-oriented there has been no cessation in the installation and expansion of STM (Synchronous Transfer Method) and OCx synchronous plant in the form of SONET, optical switches, and WDFM. DQSA enables “naked” synchronous circuits to provide efficient network services to users distributed over thousands of kilometers. The ability to support a mixture of asynchronous and synchronous services utilizing already existing T1, E1, E3, etc., synchronous circuits makes DQSA attractive to the world’s carriers. A carrier such as AT&T could provide either virtual or physical private networks for its customers using only the existing synchronous infrastructure: No Routers.

2. Copper:    The majority of packets transmitted in the world travel wholly or in part over copper networks under the control of Ethernet switches or Ethernet hubs. A DQSA-based Ethernet switch or hub can be implemented that satisfies all Ethernet interface requirements but also supports an unrivalled level of priorities plus synchronous circuits.

3. Cable TV:   DQSA provides a simpler solution than current approaches, yet provides a superior level of service.

• Fiber:

  DQSA utilizes the fiber itself as the switch; a DQSA-based fiber network requires only the appropriate NICs to operate at speeds ranging from 1 Gbps to 40 Gbps.

1. Metro:    Hundreds or even thousands of users can be serviced from a single passive fiber network. A DQSA fiber MAN would support fixed synchronous service to some customers while providing asynchronous service with priorities to other customers using the same passive medium.

2. Last Mile:   DQSA will be the switch of choice for the delivery of voice and video services via packet. The efficiency of DQSA means that only those TV channels that are being watched need be delivered, along with on-demand viewing and high-speed Internet access. DQSA will support either high-capacity fiber links into the home or lower-capacity links attached to a high-capacity trunk.

3. Virtual Server:   A multi-gigabit/s DQSA fiber backbone of several thousands of kilometers length could act as a server. A popular website instead of installing a switching capacity to support possible hundreds of thousands of nearly simultaneous “hits”would instead continuously transmit the popular pages over the fiber. The fiber circuit stretching across the country would service quite literally millions of “hits” per second.

4. Cluster Computing:    DQSA provides flexibility in that almost all features desired for parallel computing such as single messages, one-to-many transmission, many-to-one transmissions, fixed-bandwidth channels are supported. Many specialized high-cost switches do not support the features available on a DQSA passive fiber linked cluster.

• Backplane and Internal Bus:

  All the applications described so far utilize serial transmission but DQSA can also be implemented on parallel busses. DQSA offers enormous advantages over existing bus interface standards such as EISA, SCSI and PCI in that a master controller is not required. Infiniband™ is a recently introduced standard that substitutes a serial buses and switching fabric for the conventional parallel bus in order to obtain higher throughput over greater physical distances. DQSA accomplishes the same by using passive fiber in place of the switching fabric, at a considerable reduction in both capital cost and maintenance.

DQSA can also be implemented inside a chip. It has special value in chips containing multiple functional units that operate asynchronously.

Conclusion

DQSA offers a universal solution to networking: a DQSA switch can be deployed over virtually every physical medium in use today and supports all higher layer protocols. DQSA enables the building of the ultimate in low capital and maintenance cost networks in that all control resides in IADs/NICs that are no more costly than the current interface cards used to connect devices to router-based or Ethernet switch-based networks.

Three prototype systems, utilizing respectively10 Mbps copper, T1, and 200 Mbps passive fiber, have verified the performance claims presented.

Professor Graham Campbell (Ret) and his students at the Illinois Institute of Technology developed DQSA. This paper is available at www.dqsa.net. Reference material available at www.iit.edu/~dqrap.

References

• [1] US Patents 6,278,713 (2001), 6,292,493 (2001), 6,408,009 (2002).
• [2] G. Campbell “The Role of DQSA in Communications”, Qnet LLC White Paper, Oct 2001.
• [3] W. Xu and G. Campbell "DQRAP - A Distributed Queueing Random Access Protocol for a Broadcast Channel", presented at SIGCOMM '93, San Francisco.
• [4] C.T. Wu and G. Campbell, "Extended DQRAP (XDQRAP): A Cable TV Protocol Functioning as a Distributed Switch", Proceedings of 1st International Workshop on Community Networking, July 1994, San Francisco. Computer Communication Review, Vol 23, No. 4, Oct 1993, pp. 270-278.
• [5] C. T. Wu and G. Campbell "CBR Channels on a DQRAP-based HFC Network", SPIE '95 (Photonics East), Philadelphia, PA Oct. 1995.
• [6] H. J. Lin and G. Campbell, "PDQRAP - Prioritized Distributed Queueing Random Access Protocol", Proc. of 19th Conference on Local Computer Networks, Oct. 1994, pp 82 - 91.
• [7] Spectrum Wireless Assessment of the DQRAP MAC Protocol in Wireless Point-to-Multipoint Applications. Celestica Corporation. Report 1550001-1 November 10, 2000.
• [8] H.J. Lin and G. Campbell "Using DQRAP (Distributed Queueing Random Access Protocol) for Local Wireless Communications." Proceedings of Wireless '93, July 14, 1993, pp. 625-635.
• [9] C.T.Wu and G. Campbell, "DQLAN - A DQRAP Based LAN Protocol”, Proceedings of the 1st Workshop on High-Speed Network Computing, 9th Int'l Parallel Processing Sym­posium, Santa Barbara, CA, April 1995.
• [10] L. Alonso, R. Agusti, O. Sallent “A Near Optimum MAC Protocol based on the Distributed Queueing Random Access Protocol (DQRAP) for a CDMA Mobile Communication System”, IEEE Journal on Selected Areas in Communications, Vol. 18, No 9, September 2000, pp 1701-1718.
• [11] M. Miramica and G. Campbell "Robustness Analysis of the DQRAP Protocol." DQRAP Research Group Report 93-6.

Home