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.
DQSAs 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. DQSAs 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 worlds 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 hitswould 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/
_______________________________________________
questions mailing list
[email protected]
https://lists.ntp.isc.org/mailman/listinfo/questions
