A Deterministic-Internet of Things (Det-IioT) network which supports ultra-low-latency machine-to-machine communications with Quantum-Safe cyber-security for cloud computing, industrial automation and Industry 4.0 is demonstrated. The Det-IioT combines several technologies, including: (i) an SDN (Software Defined Networking) control-plane to perform secure routing (bypassing the insecure Internet Protocol); (ii) an AI (Artificial Intelligence) based ZTA (Zero Trust Architecture) access control system, to control access to all layer-3 bandwidth; (iii) PQC (Post-Quantum-Cryptography) and SKC (Symmetric Key Cryptography) to achieve Quantum-Safe cyber-security; (iv) a fast low-jitter scheduling algorithm, based upon recursive Birkhoff-Von-Neumann (BVN) stochastic matrix decomposition, with 100% utilization and ultra-low latency; (v) low-cost Switches-On-Chips (SoCs) with 10s of Tbps (Terabits/second) capacities, using FPGAs (Field Programmable Gate Arrays) to lower the capital costs of layer-3. The existing layer-3 Best-Effort Internet typically operates at low link utilizations, resulting in large capital costs of $10s of billions(US)/year. The Det-IioT can achieve 100% link utilizations, thereby reducing energy and capital costs. The demonstration video will illustrate a saturated Det-IioT network, with 8 linear stages of 16x16 FPGA-based packet switches, delivering one thousand Quantum-Safe authenticated and encrypted deterministic traffic flows from end-to-end. Each flow receives near-perfect deterministic service, with ≥ 99% link utilizations and ultra-low latencies. Buffer sizes in the Det-IioT are reduced by factors of ≈ 1,000 - 100,000, relative to the existing Best-Effort Internet, enabling the logic for a Quantum-Safe deterministic switch with 10s of Tbps capacity to fit on a single FPGA.

Today’s Industrial Internet of Things (IIoT) suffers from millions of classical cyber-attacks annually, including insider, outsider, Denial of Service (DoS) and eavesdropping attacks. Several proofs establish that Quantum Key Distribution (QKD) networks achieve unconditional security guaranteed by the laws of physics in theory. These proofs assume ideal QKD nodes with zero information leakage exist, which implies immunity to classical cyber-attacks that leak information. In contrast, many security agencies state that QKD is vulnerable to classical cyber-attacks, creating a Quantum Security Paradox between theory and practice. It is shown that: (i) Existing proofs of QKD’s unconditional security do not hold in practice, since the assumption of zero information leakage in the classical network is not met; and (ii) Real QKD networks are vulnerable to classical insider attacks and backdoors, which leak information. Global-scale Space-Ground QKD networks will integrate micro-satellites in space with ground-stations on earth. A new vulnerability is presented. These QKD networks are vulnerable to classical backdoors and global surveillance, wherein millions of secret QKD keys may be exposed. Unconditional-security requires complimentary methods to ensure zero information leakage in the classical network. A Quantum-Safe Deterministic IIoT (Det-IIoT) network that exploits SDN (Software Defined Networking), Artificial Intelligence (AI) and a Zero Trust Architecture (ZTA) access control system (ACS) is explored. The ZTA-ACS supports programmable deterministic classical communications between authorized QKD nodes or applications, and blocks communications from cyber-attackers. The Det-IIoT can be placed within satellites to strengthen Space-Ground QKD, by mitigating classical cyber-attacks that leak information.

The design of exceptionally-strong security and privacy in an ultra-dense green 5G Deterministic Radio Access Network (DRAN) for the Internet of Things (IoT) is proposed. The ultra-dense DRAN exploits fiber-optics and 802.11ad Multi-GHz WiFi technology to transport both fronthaul and backhaul traffic in a unified low-cost Crosshaul network. The Crosshaul network is similar to a very large highly-utilized IEEE Time Synchronized Channel Hopping (TSCH) network, where collision-free scheduling becomes critical. Traditional Omnidirectional Antennas and Media-Access-Control (MAC) protocols cannot be used with 5G systems. This paper shows that the combination of: (1) a centralized SDN control-plane, (2) deterministic low-jitter scheduling, and (iii) lightweight encryption in layer 2, offers a new approach for wireless security and performance with several benefits; (i) All active radio links are identified in advance and can be optimally scheduled. Every transmission has a deterministic time-slot, source, destination, and wireless channel; (ii) Any unauthorized transmissions, even a single packet transmission, can be detected quickly and reported to the SDN control-plane for corrective action; (iii) Wireless interference can be minimized by using pre-programmed Directional-Antennas; (iv) Wireless buffer sizes and queueing delays can be reduced to near-minimal values; and (v) Wireless Crosshaul bandwidth requirements can be reduced significantly. Our 5G DRAN can embed thousands of Deterministic Virtual Networks (DVNs) or Deterministic Network Slices, to ensure exceptionally-strong security and privacy between different M2M or D2D systems. The secure 5G DRAN can also integrate seamlessly with a future secure deterministic Industrial-Tactile IoT.

Computational offloading can improve the energy efficiency of mobile devices, by executing some tasks of a mobile application in the cloud. In this paper, a new algorithm called 'Dynamic Programming with Randomization' (DPR) is presented. The DPR algorithm iteratively improves an offloading decision vector, by generating random bit strings with a biased probability of generating 0s, which represent a decision to offload a task. If fragments of these bit strings improve the decision vector, they are incorporated into the decision vector (which is similar to genetic optimization). The DPR algorithm also uses a hamming distance termination criterion, with a preference to offload tasks, to find a nearly-optimal offloading solution quickly. The DPR algorithm will offload as many tasks as possible to the cloud server when the network transmission bandwidth is high, thereby improving the total execution time of all tasks and minimizing the energy consumption of the mobile device. The DPR algorithm can find excellent quality solutions with low computational overhead, by using biased randomization. Furthermore, the DPR algorithm can scale to handle larger offloading problems without loosing computational efficiency or solution quality, as the computational time grows linearly (with a slope less than unity) with the problem size. Performance evaluation shows that the proposed DPR algorithm can minimize energy requirements while meeting an application's execution time constraints, and it is able to find a nearly-optimal offloading decision vector in a few iterations.

An Enhanced-Internet network that provides ultra-low-latency guaranteed-rate (GR) communications for Cloud Services is proposed. The network supports two traffic classes, the Smooth and Best-Effort classes. Smooth traffic flows receive low-jitter GR service over virtual-circuit-switched (VCS) connections with negligible buffering and queueing delays, up to 100% link utilizations, deterministic end-to-end quality-of-service (QoS) guarantees, and improved energy efficiency. End-to-end delays are effectively reduced to the fiber “time of flight.” A new router scheduling problem called the Bounded Normalized-Jitter integer-programming problem is formulated. A fast polynomial-time approximate solution is presented, allowing TDM-based router schedules to be computed in microseconds. We establish that all admissible traffic demands in any packet-switched network can be simultaneously satisfied with GR-VCS connections, with minimal buffering. Each router can use two periodic TDM-based schedules to support GR-VCS connections, which are updated automatically when the router's traffic rate matrix changes. The design of a Silicon-Photonics all-optical packet switch with minimal buffering is presented. The Enhanced-Internet can: 1) reduce router buffer requirements by factors of ≥ 1000; 2) increase the Internet's aggregate capacity; 3) lower the Internet's capital and operating costs; and 4) lower greenhouse gas emissions through improved energy efficiency.

A switch controller which achieves low-latency deterministic `Guaranteed-Rate' (GR) connections in packet switched networks is demonstrated on a `Field Programmable Gate Array' (FPGA) device. A Software Defined Networking (SDN) control plane can configure the FPGA controllers to establish deterministic GR connections in a forwarding plane of IP routers or layer-2 packet switches. The use of deterministic GR connections can reduce queueing delays to negligible values, so that the end-to-end delays are reduced to the fiber latency. The switch controller can operate routers, switches and links at 100% loads, while simultaneously guaranteeing very low end-to-end queueing delays. A testbed consisting of 8 switches in a linear array is synthesized on an Altera Cyclone IV FPGA. An SDN control plane routes 128 traffic flows through the testbed to saturate the switches and links. Packets move through the forwarding plane at a clock rate of 52 MHz, transferring millions of packets per second, and statistics are recorded. The demonstration shows that all traffic flows in the testbed achieve deterministic GR service. The FPGA demonstration is accompanied by a video which visually illustrates packet forwarding in the network. The GR technology applies to IP routers and layer 2 packet switched networks, with thousands of nodes spanning arbitrary distances. The FPGA controller also applies to layer 2 MPLS (Multiprotocol Label Switching) and Ethernet switches, and to `Optical Packet Switched' networks, to achieve deterministic GR services and to operate links at 100% loads.

An FPGA controller which can establish low-latency deterministic `Guaranteed-Rate' (GR) transport connections for cloud services is explored. An SDN control-plane can create deterministic GR connections in a forwarding-plane of electrical or optical packet switches, where end-to-end delays are reduced to the fiber latency. A testbed for the proposed deterministic GR technology is presented. A forwarding-plane consisting of 8 controllers and minimum-complexity packet-switches are synthesized on an Altera Cyclone IV FPGA. An SDN control plane routes 128 traffic flows through the forwarding plane, which saturate the packet-switches. Several deterministic schedules are precomputed and loaded into the controller lookup tables, which control each packet-switch for each time-slot in a scheduling frame. The FPGA testbed is clocked at 52 MHz, allowing millions of packet transfers per second, and statistics are recorded. The testbed confirms the establishment of deterministic GR transport connections configured on a programmable underlay network, where the end-to-end delays are effectively reduced to the fiber latency. An inexpensive FPGA controller can add deterministic GR services to IP routers, MPLS, Ethernet, InfiniBand and Fibre channel switches, and layer-2 electrical or optical packet-switches, spanning 100s of nodes over distances of 1000s of miles. By using existing Silicon-Photonics technology, an SDN control-plane can manage deterministic GR connections in a programmable underlay network of integrated single-chip Optoelectronic Packet Switches, with aggregate capacities in the 100s of Terabits/sec.

Accurate analytic models for the area, delay and power of the Hypermesh NoC topology, realized with the Altera family of FPGAs, are presented. Hypermeshes are based on the concept of hypergraphs, which consist of a set of nodes and a set of hyperedges, where the hyperedges represent low-latency switches which interconnect multiple nodes with deterministic latencies. Three different switch designs for the hyperedges are proposed and evaluated. Two parallel algorithms are considered; (a) the Bitonic sorting algorithm, and (b) the FFT parallel algorithm. The analytic models are shown to be very accurate, typically within 6 percent. The 2D Hypermesh is compared to the 2D layouts of the binary hypercubes (BHC) and generalized hypercubes (GHC) in terms of area, energy per algorithm, and theEnergy-Area product. TheEnergy-Area productis proposed as an useful design metric to evaluate NoCs, which combines both thecostand theperformancemetrics of an NoC into one. Our analysis indicates that the 2D Hypermeshes generally have considerably lower area, energy, andEnergy-Area productcompared to the 2D layouts of the Hypercubes.

A Constrained Multicommodity Maximum-Flow-Minimum-Cost routing algorithm is presented. The algorithm computes maximum-flow routings for all smooth unicast traffic demands within the Capacity Region of a network subject to routing cost constraints. The edge cost can be a distance, reliability, congestion or an energy metric. It is shown that every network has a finite Bandwidth-Cost capacity. The Bandwidth-Distance and the Bandwidth-Energy capacities are explored. The routing algorithm requires the formulation of two Linear Programs (LPs). The first LP finds a multicommodity Maximum-Flow, when the flows are constrained to a sub-graph of the network to enforce cost constraints. The second LP minimizes the routing cost, given that the maximum-flow is fixed. A related Constrained Multicast-Max-Flow-Min-Cost algorithm is also presented, to maximize the throughput of a multicast tree using network coding, subject to routing cost constraints. These algorithms have polynomial-time solutions, whereas traditional multipath routing algorithms can be NP-Hard. The addition of routing cost constraints can significantly reduce the size of the LPs, resulting in faster solutions, with lower edge utilizations and with higher energy efficiencies. The application of these algorithms to route aggregated video streams from cloud data centers in a Future-Internet network, with improved throughput, energy-efficiency and QoS guarantees is presented.

An adaptive traffic estimation algorithm for an Autonomic Future Internet which can provide improved throughput, energy-efficiency and QoS guarantees is proposed. The theory for a Future Internet which supports multiple service classes, i.e., the traditional Best-Effort (BE) class and a new Essentially-Perfect-QoS (QoS) class, has recently been proposed. In this Future Internet, the routers give preference to the QoS traffic class. All smoothened end-to-end traffic flows in the QoS class will never experience congestion and can achieve Essentially Perfect link-utilizations and end-to-end QoS guarantees, with significantly improved energy-efficiencies. Each Future Internet router must provision bandwidth for the QoS traffic class, and schedule this class with 100% throughput efficiency and strict QoS guarantees, using a recently-proposed mathematical scheduling algorithm. In this paper, adaptive traffic estimation algorithms which allow each Future Internet router to estimate its future QoS traffic demands and provision bandwidth for the QoS demands in anticipation of their arrival are proposed. An Autonomic Controller (AC) in each router maintains a history of its QoS and Best-Effort traffic demands over a long time horizon. Several variations of Autoregressive Integrated Moving Average (ARIMA) filters are used to estimate the future traffic demands. The AC can then provision resources for the QoS demands in anticipation of their arrival. To test the algorithms, real traffic measurements taken every 15 minutes over 4 months for a European backbone network are used. The estimates are shown to be very accurate, provisioning bandwidth for the QoS class with success rates between 93% ... 99%. An Autonomic Controller (AC) in each router can also be used to automate the bandwidth provisioning process for existing Differentiated-Services traffic classes in existing Best-Effort Internet routers.

We present experimental results for performance of the 2D hypermesh NoC topology, realized with the Altera Family of FPGAs. Hypermeshes are based on the concept of hypergraphs, which consist of a set of nodes and a set of hyper-edges, where the hyper-edges represent low-latency distributed switches. In a 2D hypermesh, the nodes in each row or column are members of a hyperedge, where packets can traverse a hyperedge without encountering router queuing delays. A comparison of the 2D hypermesh, the 2D mesh, and hypercube NoCs is presented. Extensive experimental results show that under the constraint of comparable bisection bandwidth, the 2D hypermesh outperforms the other graph-based network topologies.

A multicommodity Minimum-Cost Maximum-Flow algorithm for routing multiple unicast traffic flows in infrastructure wireless mesh networks, represented as commodities to be routed in an undirected or directed graph, is presented. The routing-cost per edge can be any metric, i.e, a delay, a SNR, etc. To minimize resource-usage and transmission power, the routing-cost is formulated as a Bandwidth-Distance product, where high-bandwidth backhaul flows are routed over shorter distance paths. The routing algorithm requires the formulation of two linear-programming (LP) problems. The first LP performs constrained multicommodity flow maximization, where the traffic flowing between any source/destination pair is constrained to a sub-graph of the original graph to enforce distance constraints. The second LP performs multicommodity cost minimization, under the constraint that the aggregate flow is maximized. Both LPs can be solved in polynomial time. No other multicommodity unicast routing algorithm can achieve a larger Maximum-flow, or the same Maximum-flow rate with a lower cost. The algorithm can also be faster than other known Maximum-Flow algorithms. Given the physical interference model and an appropriate antenna model, every vector of commodity flow-rates within the Capacity Region of an infrastructure network can be scheduled to achieve rigorous throughput and QoS guarantees, using a recently-proposed scheduling algorithm. The algorithm is tested in a hexagonal infrastructure wireless mesh network to maximize backhaul traffic flows.

The performance of a novel Monolithic Microwave CMOS Distributed Oscillator is reported over a temperature range of -25°C to 75°C for the first time, along with an analysis of its design characteristics and its temperature stability. The oscillator is stable over the entire temperature range of 100°C. The monolithic distributed oscillator (DO) is designed and fabricated in an industry standard 0.18 μ m CMOS process, using an n-FET-based traveling wave amplifier (TWA), coplanar waveguides (CPW), and a new coplanar interconnect structure called a 'folded CPW'. The measured loss of the “folded CPW” is 1.259 dB at 10 GHz. The distributed oscillator uses a novel architecture ofGm-varied gain cells and operates at a bias of 1.8 V. The measured oscillation frequency is 11.7 GHz with 6.1 dBm output power and the measured phase noise is -116.02 dBc/Hz at 1 MHz offset, which represent the best reported power and one of the best phase noise results for silicon DOs with temperature stability.

The multicasting of aggregated digital video over a proposed Future Internet backbone network with essentially perfect throughput, resource-utilization and QoS guarantees is summarized. The Future Internet routers require only minor modifications to the existing router designs. Buffers in existing internet routers are partitioned into 2 traffic classes which can co-exist, the Essentially-Perfect QoS class and the Best-Effort class, i.e., no new buffers are required. Each router includes an FPGA-based Scheduler Lookup Table for the essentially perfect QoS class. RSVP-TE is used to provision the multicast trees in an MPLS-TE network. Each router computes an essentially perfect transmission schedule for all its QoS-enabled traffic flows, which never experience interference or congestion. (This integer programming scheduling problem is a long-standing unsolved problem.) The Best-Effort traffic is scheduled using the usual Best-Effort schedulers. It is shown that thousands of bursty self-similar video streams can be multicast across the proposed Future Internet with essentially-perfect link efficiencies and QoS guarantees. The technology (i) can be added into new Internet routers with minimal cost (i.e., a few FPGAs); (ii) it allows for the co-existence of the Essentially-Perfect QoS and the usual Best Effort traffic classes; (iii) it is compatible with the existing IEFT DiffServ and MPLS-TE service models; (iv) it allows for Internet link efficiencies as high as 100%, and (v) it can reduce Internet router buffer and power requirements significantly.

Algorithms to provision backhaul traffic flows in an infrastructure Wireless Mesh Network (WMN) with near minimal delay and jitter and near-perfect QoS are described. The WMN consists of Base-Stations with multiple radio transceivers for backhauling, and one or more Gateway BSs. It has recently been established in theory that a recursive fair stochastic matrix decomposition algorithm can be used to schedule all provisioned backhaul traffic flows between BSs without primary conflicts. However, no extensive simulation results were reported and the practical application of the theory was not demonstrated. To demonstrate the theory, extensive simulations of an essentially saturated 64-node hexagonal WMN supporting backhaul traffic flows are reported. Upward and downward traffic distribution trees are provisioned in the WMN to carry backhaul traffic to and from the Internet through the Gateway BSs. Background point-to-point traffic flows are added between BSs to essentially saturate the WMN. The traffic flows are scheduled using the stochastic matrix decomposition theory, to yield a sequence of permutations for a TDMA/OFDMA scheduling frame. Each permutation is colored to assign orthogonal OFDMA radio channels to the active radio edges. Two greedy graph coloring algorithms are examined, the greedy-linear and greedy-random algorithms. The network is then extensively simulated, and the end-to-end delay, jitter and queue sizes for all backhaul traffic flows are recorded. Extensive simulations demonstrate experimentally that backhaul traffic flows can be delivered with near-minimal delay and jitter and near-perfect QoS under reasonable assumptions on wireless link quality.

Over the next decades, the Internet will evolve to support increasingly complex mission-critical services such as telerobotically controlled surgery. The world's first telerobotic surgery over the public Internet was performed in 2003, and since then several hundred more have been performed. Three critical requirements of these services include: (i) essentially 100% restoration capability, (ii) small and bounded end-toend queuing delays (ie < 250 millsec), and (iii) very low-jitter communications (ie < 10 millisec). In this paper, algorithms to provision mission-critical services over the Internet with essentially 100% restoration capability and essentially-perfect QoS are proposed, building upon two theoretical foundations. Mission-critical traffic is routed using the theory of shared backup protection paths or p-cycles, while background traffic is routed using multiple edge-disjoint paths. Mission-critical traffic is scheduled using the theory of recursive stochastic matrix decomposition to achieve two constraints: (i) near-minimal end to end queuing delay and jitter and (ii) essentially-perfect QoS. Designs of the Application-Specific Token-Bucket Traffic Shaper Queues (ASTSQs) and the Application-Specific Playback Queues (ASPQs) for telerobotic services are provided. To test the theory, extensive simulations of a saturated Internet backbone network supporting telerobotic services along with competing background traffic (ie VOIP, IPTV) are reported. It is shown that all missioncritical traffic can be delivered while meeting the three critical requirements, even in fully saturated backbone IP networks.

We present a novel distributed scheduling paradigm for Internet routers with input-queued (IQ) switches, called cooperative token-ring (CTR) that provides significant performance improvement over existing scheduling schemes with comparable complexity. Many classical schedulers for IQ switches employ round-robin arbiters, which can be viewed as non-cooperative token-rings, where a separate token is used to resolve contention for each shared resource (e.g., an output port) and each input port acquires a token oblivious of the state of other input ports. Although classical round-robin scheduling schemes achieve fairness and high throughput for uniform traffic, under non-uniform traffic the performance degrades significantly. We show that by using a simple cooperative mechanism between the otherwise non-cooperative arbiters, the performance can be significantly improved. The CTR scheduler dynamically adapts to non-uniform traffic patterns and achieves essentially 100% throughput. The proposed cooperative mechanism is conceptually simple and is supported by experimental results. To provide adequate support for rate guarantees in IQ switches, we present a weighted cooperative token-ring, a simple hierarchical scheduling mechanism. Finally, we analyze the hardware complexity introduced by the cooperative mechanism and describe an optimal hardware implementation for an N times N switch with time complexity of Theta(log N) and circuit size of Theta(N log N) per port.

A guaranteed-rate scheduling algorithm for packet-switched IP routers with rate, delay and jitter guarantees is proposed. The algorithm can be used to schedule traffic with 100% throughput in Input-Queued IP routers with unity speedup. The traffic is scheduled according to transmission frames of duration F time-slots. An N x N doubly stochastic traffic rate matrix specifies a traffic rate between each pair of IO ports. The matrix is quantized and recursively decomposed into a sequence of F permutations. Each permutation is used to configure the crossbar switch for one time-slot without requiring additional scheduling. The recursive fair stochastic matrix decomposition is based upon the routing of a permutation through a binary rearrangeable network. In the resulting transmission schedule, the expected Inter-Departure Time (IDT) of a cell equals the Ideal IDT (IIDT), and the maximum IDT and service lag of a cell are bounded by an integer number of IIDTs. The delay and delay jitter experienced along an end-to-end path in a packet-switched IP/MPLS network are therefore small and bounded by an integer number of IIDTs, and the buffer sizes within the IP routers are small and bounded. The proposed algorithm can be used to schedule Guaranteed-Rate traffic in packet-switched IP/MPLS networks, to provide near-optimal queueing delays and essentially-zero delay jitter along end-toend paths when playback buffers are employed.

The integration of thousands of optical input/output (I/O) devices and large electronic crossbar switching elements onto a single optoelectronic integrated circuit (IC) can place stringent power demands on the CMOS substrates. Currently, there is no sufficiently general analytic methodology for power analysis and power reduction of large-scale crossbar switching systems. An analysis of the power complexity of single-chip optoelectronic switches is presented, assuming the classic broadcast-and-select crossbar architecture. The analysis yields the distribution of power dissipation and allows for design optimization. Both unpipelined and pipelined designs are analyzed, and a technique to reduce power dissipation significantly is proposed. The design of a 5.12 Tbit single-chip optoelectronic switch using 0.18-/spl mu/m CMOS technology is illustrated. The pipelined switch design occupies < 70 mm/sup 2/ of CMOS area, and consumes <80 W of power, which compares favorably to the power required in electrical crossbar switches of equivalent capacity.

We present a novel scheduling algorithm for Internet routers with input-queued switches based on credit-based fair queueing. We present a flow-based iterative credit-based fair scheduler (iCBFS) for crossbar switches, that provides fair bandwidth distribution among flows at a fine granularity and achieves asymptotically 100% throughput, under uniform traffic. To reduce the implementation complexity of iCBFS, we present a port-based version of iCBFS that is tailored towards high-speed hardware implementation.

Optoelectronic integrated circuits can support thousands of integrated optical laser diodes and photodetectors bonded to a high-performance CMOS substrate, and can be used in the design of multi-Terabit optical local area networks. This paper describes the design of an integrated optoelectronic CMOS crossbar switch to interconnect approx. 128 parallel fiber ribbon optical links, each with 12 channels clocked at 2.5 Gigabit/sec, to achieve a local area network (LAN) with an aggregate capacity of 3.84 Terabits/second. A prototype switch core has been designed in 0.18 /spl mu/m CMOS technology. Logic optimization and synthesis was performed using the synopsis logic optimization tools, and VLSI layout was performed using the Cadence 2002 tools. It is shown that using 0.18 /spl mu/m CMOS technology, a 3.84 Terabit crossbar switch for an optoelectronic LAN occupies approx. 1.78 sq. cm of real estate, and consumes approx. 90 watts of power.

Three dimensional integration is an increasingly feasible method of implementing complex circuitry. For large circuits, which most benefit from 3-D designs, efficient placement algorithms with low time complexity are required.We present an iterative 3-D placement algorithm that places circuit elements in three dimensions in linear time. Using an order of magnitude less time, our proposed algorithm produces placements with better than 11% less wire lengths than partitioning placement using the best and fastest partitioner. Due to the algorithms iterative nature, wire-length results can be further improved by increasing the number of iterations.Further, we provide empirical evidence that large circuits benefit most from 3-D technology and that even a small number of layers can provide significant wire-length improvements.

Principles for designing practical self-routing nonblocking N/spl times/N circuit-switched connection networks with optimal /spl theta/(N/spl middot/log N) hardware at the bit-level of complexity are described. The overall principles behind the architecture can be described as "Expand-Route-Contract". A self-routing nonblocking network with w-bit wide datapaths can be achieved by expanding the datapaths to w+z independent bit-serial connections, routing these connections through self-routing networks with blocking, and by contracting the data at the output and recovering the w-bit wide datapaths. For an appropriate redundancy z, the blocking probability can be made arbitrarily small and the fault tolerance arbitrarily high. By using efficient space domain concentrators, the architecture yields self-routing nonblocking switching networks with an optimal O(N/spl middot/log N) bits of memory or O(N/spl middot/log N/spl middot/log log log N) logic gates. By using a linear-cost time domain concentrator, the architecture yields self-routing nonblocking switching networks with an optimal /spl theta/(N/spl middot/log N) bits of memory or logic gates. These designs meet Shannon's lower bound on memory requirements, established in the 1950s. The number of stages of crossbars can match the theoretical minimum, which has not been achieved by previous self-routing networks. The architecture is feasible with existing electrical or optical technologies. The designs of electrical and optical switch cores with Terabits of bisection bandwidth for Networks-of-Workstations (NOWs) are described.

An optimal N/spl times/N circuit switching network with /spl theta/(N/spl times/N) bandwidth has a lower bound of /spl theta/(N/spl middot/log N) hardware, which includes all crosspoints, bits of memory and logic gates, and a lower bound of /spl theta/(logN) set-up time. To date no known self-routing circuit switching networks with explicit constructions achieve these lower bounds. The authors consider a randomized routing algorithm on a class of circuit switching networks called "extended dilated banyans". It is proven that the blocking probability of an individual connection request is O[log/sub b/ N/spl middot/(k/d)/sup d/], where d is the dilation factor and k is a constant. With a dilation of /spl theta/(log log N) and a loading>

A Markov Chain based analysis for deflection routing in n-dimensional regular mesh networks is presented. Detailed analyses are given for the 2D mesh, and a generalization to higher dimensions is outlined. Analytic results are shown to agree very closely with simulations. A basic routing scheme in which all packets have equal priority and a priority scheme in which packets with fewer alternative routes are given priority are proposed and analyzed. Results show that the priority scheme gives higher maximum throughput and lower average packet delay than the basic scheme by reducing average deflections under heavy loads. With the priority scheme, the network performance is almost identical to that of the optimal diagonal routing scheme. By doubling the number of links the throughput is always more than doubled. The authors conclude that in the 2D case, bidirectional links are more cost-effective than unidirectional ones assuming the cost is the number of optical transceivers.>

The performances of centralized, fast packet switches based on the ShuffleNet and on multistage banyans are compared. Two cost criteria are used, viz., the number of crosspoints and the number of pin-limited ICs. The analytic comparison of the two networks built with arbitrary size infinite buffered nodes shows their cost performance to be similar. The analysis also provides the optimal node sizes for both the topologies. The best throughput per crosspoint is obtained with small nodes, but the best throughput per pin-limited IC is obtained with the largest possible nodes that can be built on an IC. With the IC criterion, for both the networks, small nodes are found to give small minimum delays (inside the network). With finite buffered nodes and a simple back-pressure flow control (like the one for the banyan network), the ShuffleNet based switch can have problems of congestion. It is also prone to deadlocks.>

Two implementations of a fiber-optic packet-switched hypercube are proposed. In the first, each directed link is implemented with a fixed wavelength laser and photodetector, and all optical transmissions are wavelength multiplexed onto one or more fibers. In the second, the electronic crosspoint matrices within the nodes are eliminated by allowing each laser to be tunable over a range of log N wavelengths. Assume that a hot potato, or deflection, routing algorithm is used; as soon as a packet is received at a node, a routing decision is made and the packet is sent out. The node attempts to send the packet towards its destination. The analysis indicates that a hypercube, hot-potato routing offers essentially optimal performance for random traffic, regardless of how large the hypercube grows, and it significantly outperforms traditional shortest-path routing with buffering and flow control. A few variations, including an algorithm which gives priority to packets closer to their destinations and one which gives priority to various classes of traffic, are also proposed and analyzed.>

The design and approximation analyses of discrete-time buffered crossbar and banyans with cut-through switching are presented. The crossbar switches can contain: (1) input FIFO (first in, first out) queuing, (2) input bypass queuing where the FIFO discipline is relaxed, (3) a novel scheme called restricted output queuing where the number of simultaneous arrivals to an output queue is upper bounded, or (4) a novel combination of input FIFO and restricted output queuing. An analysis for the delay distribution of a packet leaving the network is presented. Restricted output queuing (or combined input and restricted output queuing) can rival the performance of pure output queuing, while requiring far less hardware.>

Approximate Markov chains for the performance of banyan networks built with basic switches of arbitrary size containing input queues, output queues or a combination of input buffers and output queues are presented. These chains are also extended to model banyans where each link is replaced by a number of parallel links. Comparison with simulations indicates that the chains are reasonably accurate for practical network loads. It is shown that banyans built with switches containing a combination of single input buffers and output queues outperforms banyans built with switches containing only input queues or only output queues. Banyans built with larger nodes are shown to outperform banyans built with smaller nodes. It is shown that banyan-based networks with multiple links can be designed to have extremely low blocking probabilities.>

An analytic approximation for the blocking probability of a circuit-switched, multipath multistage interconnection network when it is required to perform arbitrary permutations under local control is presented. An analytic approximation for the expected number of conflict-free permutations realizable by a network in one pass under local control is also presented. In addition, an analytic approximation for the expected number of passes through a network required to realize an arbitrary permutation under local control is presented. These models give a quantitative measure of a network's ability to perform arbitrary permutations and of the inherent blocking in a network. These models are used to analyze two variations of banyan networks that have been discussed in the literature: dilated and augmented banyan networks. It is shown that these networks can be designed with very low blocking probabilities under permutation request patterns, and that they can be designed to realize almost all permutations in one pass under local control.

We present analytic models for the blocking probability of both unique path and multiple path multistage interconnection networks under the assumption of either permutation or random memory request patterns. The blocking probability of an interconnection network under the assumption of permutation requests is a quantitative measure of the network's permutation capability. We compare the performance of networks with approximately equivalent hardware complexity. It is shown that variations of banyan networks can be designed with extremely low blocking probabilities under the assumption of permutation requests.