Abstract — A near-ideal MAC, i.e., an algorithm that enables a communications channel to provide an arbitrary number of users with both synchronous and asynchronous services over any distance and at any speed, could be the basis of a novel enhancement to Internet switching. Such an algorithm would enable a high capacity optical-fibre based circuit, instead of simply transporting packets from one router to another, to itself act as a distributed switch providing service to hundreds or thousands of users over a large area. Such a MAC is in fact available and this paper describes how this MAC could be used as a basis for Distributed Queue (DQ) switching to allow a not inconsiderable portion of Internet traffic to bypass routers by assigning users to DQ-based Distributed Service Areas (DSA) that are not geographically limited. Cascaded Distributed Queue switching is introduced, a form of switching that supports congestion-free transport between DSAs.

Keywords—Switch; router; networks; MAC; packet-switching; DQ; DQSA.

I. INTRODUCTION

Distributed Queueing (DQ), also referred to as DQSA (Distributed Queue Switch Architecture), is proposed as a switching/routing system for portions of the Internet, one that supports both congestion-free packet and dynamically invoked fixed-bandwidth services. DQ is made feasible by the availability of a suitable Medium Access Control (MAC) and fibre optic circuits operating up to the petabit per second range. A DQ switch is distributed in that a single communication channel is efficiently shared over any distance at any bit rate by an arbitrary number of users; all control resides in the Network Interface Cards (NICs) that reside at each node; there is no central control. DQ switching could, for a significant portion of Internet traffic, utilize existing infrastructure in a broadcast/multicast mode and in effect move the routing function from the Network Layer to the MAC/Data Link layer, reducing the number of routers.

DQ does rely on an almost ideal MAC so let us address that topic before moving on. There are citations to specific seminal papers later but for the present the reader is directed to “Goodbye, Aloha!” by Laya [6], a paper that compares the DQ protocols with most other protocols in current use. Of more importance than details on performance is the extensive list of citations that demonstrates the amount of research over the past near quarter century into the protocols underlying DQ. Thus the reader can concentrate on thinking about the applications, not only those presented in this paper, but those that might occur to the reader, when such a MAC is available.

The current packet switching infrastructure employs routers that in turn utilize an underlying circuit-switching infrastructure that is an optical fibre version of the POTS (plain old telephone system) in use for almost a hundred years, i.e., it makes possible the establishment of a circuit between virtually any two points. POTS started by serving individual communities, Local Service Areas (LSA), with voice service supported by a central office that connected each of the hundreds or thousands of local customers via a pair of copper wires in a star topology. The individual copper lines ofttimes had multiple customers on a single line, a “party line”.

The invention of the electron tube enabled the interconnection of LSAs on a country-wide basis. Direct- dialing eliminated manual operators and solid-state logic led to digital voice circuits and the introduction of computers. For the first time entities, albeit not human, could transmit meaningful amounts of information in microseconds, a challenge to the circuit-switching infrastructure designed to support a circuit that would be in use for minutes. The solution was to digitize all information, carry it in packets that contained both destination and source addressing. And utilize a switch that did not require apriori information, a switch that became the ubiquitous router. But the existing circuit- switched infrastructure was still used to interconnect those routers, the same infrastructure that today in the main utilizes optical fibre circuits and optical switches. Thus today the Internet relies on an underlying infrastructure that is really a hybrid of two physical networks, although traffic is carried on a single physical circuit.

Unfortunately, packet-switching is challenged by the very type of traffic that it was designed to support - a surfeit of packets leads to congestion, and in addition routers are not amenable to providing the equivalent of fixed-bandwidth circuits, the type of circuit most suitable for the delivery of streaming video. The result is that from the first, over- engineering was necessary for effective operation and remains so.

II. DQ SWITCHING

DQ returns to the original POTS concept in that it utilizes the existing circuit-switched infrastructure to provision Distributed Service Areas (DSAs). A DSA utilizes a modern version of the “party line” that was in use for a hundred years, modern in the sense that the MAC employs multiplexing to serve thousands or even hundreds of thousands of customers using but a single circuit. In place of the restricted geographical area served by an LSA, a DSA can serve a community of users distributed over thousands of Km, e.g., a business with 100 branches nationwide or even a branch of the military, say all the army bases in the country.

Why refer to what appears to be an old-fashioned shared- Ethernet LAN, albeit gigantic, as a switch? The DQ MAC algorithm utilizes fixed-size segments that have three advantages over the existing MACs that directly support variable length, e.g., Ethernet frames:

1. Variable length Ethernet frames are still supported by segmenting into 64/128/256 byte chunks, at the cost of fragmentation overhead in the final frame.

2. Standard ranging techniques are used to support access over any distance.

3. The individual frames can be allocated either in a sequence, to support an individual Ethernet packet, or on a recurring basis making available isochronous channels of almost arbitrary overall bit rate.

A switch is generally thought of as a black box with multiple ports but consider that almost every router built directs traffic from input ports into a common buffer where a decision is made to direct a packet to a specific output port. This is what a DQ switch accomplishes excepting that the “buffer” is now distributed, a circuit that accepts all segments (the MAC ensures there are no collisions). The segments are delivered to all ports, simplifying the “switching” since each port recognizes and retrieves only its own traffic. There are still queues but they are virtual and since the physical segments are distributed across all nodes the individual node queues can control the input, thus no congestion. For transmission a node can either request the specific number of slots that will contain a specific Ethernet frame or can request a single slot on a recurring basis and thus acquire a bone fide isochronous channel.

DQ augments the “rough” granularity of optical switches with a “fine” granularity that supports the switching of 64/128/256-byte segments thus enabling packets to be transported efficiently and collision-free from source to destination(s) utilizing only the PHY and MAC/Data Link layers. The need for routers is eliminated in this portion of the network.

III. IMPLEMENTING DQ IN THE INTERNET

Any portion of the Internet that satisfies some simple rules on commonality, either geographic or functional, could be converted to DQ switching. A Virtual Private Network (VPN), is used to demonstrate the use of DQ. A VPN is used by an organization to obtain the security of a private packet network yet gain the economies of using resources that are used and paid for by all, the Internet. The VPN utilizes Internet resources whose overall topology can be described as a mesh with nodes consisting of routers around the country. Figure 1 illustrates the implementation of several VPNs in a packet network, color-coded to show which nodes are interconnected. Plotting the traffic flow of one of the VPNs, as shown in Figure 2, and assuming a shortest-path algorithm is used, all traffic flows to/from the root along branches that conform to a physical tree-and-branch topology. Note the similarity to traffic flow in a wireless network where traffic flows to/from a central node. Where these patterns exist in the Internet it is proposed that DQ can provide improved efficiency at a lesser cost.



The topology of a DQ-based DSA that should provide better service is shown in Figure 3; congestion is eliminated and utilization of the physical media is increased by up to 50%. Each DSA utilizes a separate physical network rather than sharing a physical circuit as do routers but there are two reasons why this does not lead to underutilization of the physical circuit:

1. A DQ-based DSA can be designed for over 90% average use -- offered traffic surges exceeding 100% of capacity cause no problems -- thus leading to greater overall utilization of the physical circuits.

2. A DSA can itself be “virtual”, i.e., central nodes of dozens of VPNs can be co-located so as to utilize a single “fat” channel rather than multiple smaller channels, thus gaining the advantage of multiple use of a circuit as characterized by typical VPNs.

Proposed changes to the architecture of the Internet are subject to a lengthy and expensive review process before implementation but in the case of DQ it is possible to at least very quickly ascertain the potential benefits, both economic and operational, before having to decide on major expenditures. Why? For any prospective DQ-based DSA a simple linear or tree-and-branch network can be sketched. The expected traffic will dictate the required capacity of the necessary circuits, assuming 90% utilization, which provides the basis for accurate estimates of costs. The NIC at each node is less complex than a standard Ethernet NIC. This estimated cost along with operation benefits of support for async/sync services and no packet discard can be compared with existing cost/performance and thus provide a solid basis for any decision to proceed with the deep-pocket evaluation. There are three major classes of users that would benefit from DQ-based DSAs:

1. Telecommunications Service Providers (TCP) could establish multiple DSAs to serve their territory, each DSA in turn supporting multiple virtual DSAs.

2. Public and private entities could deploy private DSAs.

3. Content Delivery Networks (CDNs) could deploy DQ to improve performance. More on this later.

Back of the envelope calculations suggest that the amortization period for implementing a DSA network, after development, could be months, if not weeks.

IV. THE ALGORITHMS THAT MAKE DQ FEASIBLE

The close-to-ideal MACs used by DQ are DQRAP, described by Xu and Campbell [1], and XDQRAP as described by Wu and Campbell [2]. DQRAP supports full utilization of a channel when the offered traffic consists of fixed-size segments, e.g., ATM (Asynchronous Transfer Method) cells or single readings from RFID tags. XDQRAP is a major enhancement that while still utilizing fixed-length segments, multiple segments can be requested thus supporting variable length traffic, e.g., Ethernet frames, that are segmented for transmission but most importantly with no further overhead, except for fragmentation. An important feature of DQ is the ability to support both packet and fixed- bandwidth services as described by Wu and Campbell [3]. DQ supports true priorities that for instance allow preemption of a jumbo Ethernet frame during transmission. See Lin and Campbell [4].

The simplicity of the DQ algorithms is exemplified by the fact that a basic DQRAP algorithm could be implemented with the equivalent of a four-state machine plus two binary counters.

V. CASCADED DISTRIBUTED QUEUE SWITCHING

1. Inter-DSA Switching: It was obvious that theoretically a DQ-based DSA of virtually any size could be implemented. But it was also obvious that practical constraints including latency would make multiple DSAs preferable. This led to several years research on developing a switch that would allow such interconnection and at the same time overcome the problems of a conventional router. The result is Cascaded Distributed Queue (CDQ) switching as described by Chang and Campbell [5] wherein a QNode serves as both a node on a DSA and the hub of an adjacent DSA. Thus a packet can “cascade” over intermediate DSAs to reach a destination.

2. CDQ Performance: Packets will travel from New York to San Francisco in the network of Figure 4 without encountering congestion even when the offered traffic represents 90% of capacity. The total delay encountered by a packet in a CDQ network consists of three parts:

   a) The access time to enter the first DQ network, i.e., request is made, station enters distributed queue, and reaches head of queue.

   b) The propagation delay between the origin and the destination.

   c) The delay between arriving at each QNode and exiting that QNode.

Figure 4 illustrates a CDQ network that interconnects metro-based DQ networks across the USA from New York to San Francisco. Individual metropolitan networks, possibly more than one in each area, are connected to a hub that functions both as a hub for a conventional DQ network in that area but is also connected to adjacent hubs. We use the QNode in Kansas City to explain the operation. The Kansas City QNode acts as a central hub to the QNode at St. Louis in that St. Louis sends requests to Kansas City when it wants to transmit. It is competing with stations in Kansas City. The QNode in Kansas City sends requests to Denver when it must transmit. This is repeated across the country; duplex facilities take care of traffic in the other direction.

A 10-segment CDQ network was simulated with 80%-90% total loading of Poisson point traffic that was made up of varying mixtures of through and local traffic. The local traffic consisted of both single segment traffic and traffic traveling more than one segment. The access time and propagation delay are fixed so that the only variable is the Qnode delay which was shown in simulation to range from slightly over one slot time to under two slot times. The queue length never exceeded 50 during simulation, thus overcoming the congestion problem of conventional routers.

QNodes have "routing" tables that are utilized very differently from those in conventional routers. When a packet reaches a QNode the destination is checked and if it is on the local network it can be assumed that the packet has reached its destination node and thus can be discarded.

VI. SUGGESTED RESEARCH TOPICS RELATED TO DQ

1. Benefits of DQ-Based DSA: A rough estimate of the potential of DQ switching can be determined fairly quickly with minimal resources. If expected traffic is known, a DSA can be designed by sketching a linear or tree-and-branch topology that connects the sites. Assume 90% average loading since surges up to double capacity are absorbed by the distributed buffers and determine the cost of the required circuits. And that is the rough cost of a DQ network. This does neglect the cost of the Ethernet-like NICs and “or” gate connections and other internal modifications. Compare with current costs, taking into account the lack of congestion and support of inter-mingled sync and async services. This study could be extended to estimate what percentage of total Internet traffic could benefit, assuming high capacity DQ networks supporting multiple virtual DSAs. The results could possibly justify an accelerated interest in DQ.

2. A DQ-Based DSA as Distributed Server: Investigate the potential of using a modified DQ- based DSA carrying thousands of the initial pages of popular websites, repeatedly, thus providing millions with almost instant connection and access to those websites; follow-on requests would utilize existing practice. The same feature could be used to distribute popular videos. As mentioned previously, this is somewhat related to the functions of a CDN.

3. CDQ Enhancement: There is a need to adapt CDQ to support synchronous switching as well as congestion-free switching of individual segments. In addition the basic algorithms used by CDQ could be used as pointers towards developing a general- purpose switch operating at the PHY/Mac-Data Link layer that would support all packet switching in the Internet, thus removing the need for conventional routers.

4. DQ Switching in ICs:Reducing distances to hundreds of microns rather than kilometres we recognize that ICs face the same problems with sharing a parallel bus as does a wireless network. The DQ algorithms are amenable to parallel operation so an interesting research problem is adapting the algorithms for use in ICs.

5. DQ Switching in Backplanes: The same arguments presented in 4 apply to backplane switching.

6. DQ and Sensors: Xu and Campbell [1] explain that the key to the success of the DQ algorithms is that they utilize two queues: (1) transmission, and (2) collision resolution. Thus, transmission starts almost immediately and continues while collisions in requests are resolved. In practice this means if one million sensors in a DQ network simultaneously report an event and the cycle time for polling and response is one microsecond then the first successful sensor transmission will occur in approximately 15 microseconds and all information will have been received from the million sensors in one million microseconds. The development of nanoscale elements for sensing in medical and other fields suggests there will be applications where literally hundreds of thousands could be be utilized, with the possibility that all nodes could report simultaneously. Thus virtually every application in the Internet of Things could possibly benefit by utilizing DQ.

7. DQ and Backhaul: Backhaul is a major problem in virtually every area of communications, Internet, satellite networks, etc. DQ switching as described above when deployed as backhaul provides the equivalent of the venerable add-drop function in use for decades in synchronous switching. But whereas the minimum time, measured in bits, for conventional add-drop, as with optical switching, at the bit-rates being considered could be in the tens of millions of bits, the DQ version of add-drop allows for the efficient dropping/insertion of blocks of data as short as 64 bytes, thus supporting both packet and circuit services.

8. Fibre-Wireless-Copper Circuits. The flexibility of DQ means that a backhaul circuit could seamlessly transverse a sequence of fibre, high capacity 5G circuits and copper. Thus while it has been stated that in general there is little advantage to converting consumer-related cell and WiFi to DQ, it would be well to include the DQ MAC algorithms in 5G wherein it is functionally a part of the “backbone”.

9. Ultra-high Speed and High Capacity Circuits. DQ switching as described above can be deployed using existing 10 Gigabit/second facilities but research will be necessary to implement the algorithms using petabit per second and higher bitrates in parallel. DQ switching supports asymmetry and parallel operation: these features could be utilized in designing for transport of streaming video. These features along with inherent unicast, multicast and broadcast capability suggest that DQ should be considered as the go-to solution for video transport.

Research in this area could lead to the integration of the CDN function into the basic support infrastructure of the Internet, leading to homogeneity of facilities.

This list could go on but it can be argued that every entity existing that requires three or more constituent components to communicate could be investigated to determine whether it would benefit, economically or functionally or both, by utilizing DQ switching.

VII. COMMENTS

The problems that plague the router were well-known in advance of its initial use but despite continuous and still- ongoing research there has been little success in mitigating these effects. The ability to support the phenomenal amount traffic has as much to do with Moore's Law and its equivalent developments on related technologies. And of course the same can be said about DQ, i.e., while a DQ algorithm will work anywhere it is the impressive increase in capacity of circuits, especially fibre-based, that make the concept of shared switching feasible, only this time over-engineering will not be necessary. And with ever-increasing bit-rates it means that shared switching should be considered in any future developments in switching.

MACs are generally considered as applicable only to wireless circuits but since most wireless networks are at the “edge” of the net there would not be much benefit to having DQ if the backbone did not support the sync/async features of DQ. There would be increased utilization of the physical circuit but as with the router functions over-engineering has been very successful in supporting the ever-increasing traffic. An exception, as pointed out above, could be 5G and backhaul.

Another plus for DQ switching is that the segments are “naked”, i.e., not wedded to any protocol. However, previous implementations and this paper assumes that Ethernet frames will be used such that compatibility issues should be few.

VIII. CONCLUSIONS

DQ switching is proposed as an enhancement to the switching infrastructure of the Internet. In those areas of the Internet where it is feasible to establish a DSA these benefits, i.e., packet and circuit-switched services accompanied by reduced costs, could be made available in a relatively short period of time. In the longer run DQ and CDQ could point towards a universal switching system that

1. Supports both asynchronous and synchronous services at the PHY/MAC-Data Link layer.

2. Enables a circuit to maintain synchronicity across fibre, wireless and copper media.

A switching system with these features could then assume the mantle worn by POTS for almost a century, i.e., a universal switching system that satisfied virtually all communications requirements.

REFERENCES

W. Xu and G. Campbell "DQRAP - A distributed queueing random access protocol for a broadcast channel", presented at SIGCOMM '93, San Francisco. Computer Communication Review, Vol 23, No. 4, Oct 1993, pp. 270-278

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.

C. T. Wu and G. Campbell "CBR channels on a DQRAP-based HFC network", SPIE '95 (Photonics East), Philadelphia, PA Oct. 1995.

H.J. Lin and G. Campbell “PDQRAP - Prioritized distributed queueing random access protocol”, Proceedings of 19th Conference on Local Computer Networks, Oct 1994, pp 82-91.

Andrew Chen-Hung Chang and G. Campbell "Cascaded distributed queue switching", Unpublished.

A. Laya, C. Kalalas, F. Vázquez-Gallego, L. Alonso, J. Alonso- Zarate. “Goodbye, ALOHA!” IEEE Access, Vol. 4, pp. 2029 – 2044, April 2016.