[ntp:questions] DQSA and Universal Networking - http://www.dqsa.net/index.php

Johnson Luqaz jluqaz at streamyx.com
Mon Mar 27 06:47:02 UTC 2006


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.
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.
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.
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:

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].

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.

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.

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:

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.

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.

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.

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.

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.

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.

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 Symposium, 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.

-- 
Kuala Lumpur
MALAYSIA : UTC +08:00
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/




More information about the questions mailing list