Previous work on differentiated services in the Internet has defined new notions of QoS that apply to aggregates of traffic in networks with coarse spatial granularity. Most proposals for differentiated services involve traffic control algorithms for aggregate service levels, packet marking and policing, and preferential treatment of unmarked packets in the network core. The issue of routing for enhancing aggregate QoS has not received a lot of attention. This study investigates the potential benefit of using alternate routing strategies in support of differentiated services. We propose a traffic control scheme, called simple alternate routing, wherein portions of unmarked packet flows can be assigned to alternate paths through a service provider network (SPN) in response to congestion feedback information. The scheme is simple, requiring only minor changes to the SPN border routers so that alternately routed packets can be tunneled via conventional paths to an intermediate border node and then tunneled from there to the original egress border node. We present distributed algorithms for (1) discovering congestion within the SPN, and (2) allocating traffic to alternate paths that are uncongested. We have implemented the scheme in a packet-level simulation, and we have examined the transient response of the algorithm to perturbations in the nominal traffic levels experienced by the SPN. The experimental study of this paper provides some understanding of the scheme's ability to adapt in routing packets around congestion. Our results indicate that the alternate routing framework shows promise and warrants further consideration.

The routing and signaling protocols for supporting multipoint-to-multipoint connections in ATM networks have been presented earlier. VP-merge and VC-merge techniques have been proposed as the likely candidates for resolving the sender identification problem associated with these connections. The additional buffer requirements in the VC-merge mechanism and the excessive rise of VPI/VCI space in the VP-merge mechanism have been the main reasons for concern about their effective utility. We propose improvements to the traditional VC-merge technique to minimize the need for additional buffers at intermediate merge points. Aptly named dynamic multiple VC-merge (DMVC), fixed multiple VC-merge (FMVC) and selective multiple VC-merge (SMVC), these mechanisms define a generic scheme for merging the data from multiple senders onto one or more outgoing links. By appropriately choosing the number of connection identifiers per connection, these schemes lead to a large reduction in the buffer requirements and an effective utilization of the VPI/VCI space. Based on extensive simulations, we show that by using two connection identifiers per connection, there is an 80% reduction in buffer requirements for DMVC and FMVC when compared to the buffer required for traditional VC-merge.

In this paper, we present a scalable dynamic multicast routing algorithm based on a dynamic Steiner tree approach. First, we analyze a hierarchical multicast routing algorithm which introduced the use of core nodes in each peer-group to support multicasting under the private network-network interface (PNNI) framework. Based on this analysis, we conclude that finding near-optimal multicast trees in each peer-group is important. Our proposed algorithm produces improved results by computing better multicast trees within each peer-group. This scheme also eliminates the dependency of core node selection, on the quality of overall multicast tree generated. We compare the two schemes based on simulations on several randomly generated graphs of size ranging from 115 to 170 nodes. Based on these simulations, we show that our algorithm performs 35% better than the hierarchical algorithm. Our algorithm is scalable, allows incorporation of fault-tolerance and can easily be extended to incorporate a QoS criterion in routing.

The authors present the issues involved in the design of a special-purpose processing array system, called HAM, which accelerates computationally intensive wire routing tasks. It is especially suited for double-sided surface-mounted boards, which require complex three-dimensional search operations over multiple wiring planes. The novel features of the design include a hexagonal interconnection scheme to improve workload distributions during multilayer concurrent search operations and the VLSI custom design of the processors. Particular emphasis has been placed on the demands of maze routing. A cell-address propagation scheme, which is quite different from the traditional grid-coordinate approach, is discussed. It provides rapid lookup of pertinent routing information and can be extended to any distributed memory multiprocessor system. A global pipelining scheme of cell updates and expands is discussed. Experimental results are presented relating the speedup to various criteria for two different modes of parallel wave propagation.>

A host-driven reconfiguration scheme, called HEX-REPAIR, is proposed for hexagonal processor arrays characterized by a large number of relatively simple cells. Such arrays have been shown to be the most efficient for many digital signal processing applications, such as matrix multiplication, and for some classes of filtering operations. Reconfiguration for these arrays is made difficult by the asymmetric nature of the interconnection network and the need for keeping the switching overheads at a minimum. The algorithm presented meets these requirements. In addition, it has excellent fault-coverage characteristics, even in the presence of multiple faults, and can accommodate multiple rows/columns of spare cells. The restructured array is transparent to users and no modification is required in any application program using the array.>

A novel hardware accelerator comprised of several fast processors interconnected in the form of a hexagonal mesh with wraparound connections is proposed. The novelty of the proposed architecture stems from the fact that it is suitable not only for single-layer routing, but also for routing in parallel on multiple layers. A hexagonal machine of dimension square root kG, with about 3kG processors, can handle a k-layer grid consisting of kG/sup 2/ grid points at about the same speed as a full-grid machine with kG/sup 2/ processors. A technique for measuring the performance of a hardware accelerator in terms of the average delay incurred over a full-grid machine is suggested. This has been formalized in the case of the hexagonal architecture, and is presented for various nets and mesh dimensions. The results have been accurately verified by extensive simulation done in C++ language. It is demonstrated that the hexagonal mesh, by virtue of its additional links for expansion, is resilient to about 10% of failure in the links and processing elements. A detailed design for a chip implementation of the hexagonal machine is discussed.>

The authors investigate a C-wrapped hexagonal mesh architecture (called HAM, for hexagonal array machine) for the physical implementation of the Lee algorithm. They show the high promise of such a machine in handling routing on single as well as on multiple layers. The mapping corresponding to a C-wrapped hexagonal interconnection of N processing elements (PEs) results in an interprocessor cycle length of N. This is much superior to the N/2 results obtained by other researchers. Consequently, fewer conflicts arise during wave-front expansion and a good quality routing can be achieved in a much shorter period. The authors show that a hexagonal mesh with 3 kG PEs can do routing on k-layer grids with kG/sup 2/ grid points at speeds comparable to the full grid machine.>