In random broadcasting or dynamic broadcast, source packets that have to be broadcast to all the other nodes are generated at each node of a network or a parallel/distributed system at random instances or in an uncoordinated manner. In this paper, we propose a priority-based routing scheme, to be referred to as prioritized dominating-set broadcasting (PDB), for random broadcasting in k-ary n-cubes. PDB can lead to a family of algorithms optimized for different switching techniques and communication models. It is also applicable to various other network topologies. Our goal is to minimize the average reception delay under heavy load, without compromising the maximum achievable throughput.

The holy grail for medium access control is freedom from collision, while the holy grail for prioritization is absolute differentiation, where higher-priority packets can be transmitted without being affected by lower-priority packets. Fairness can then be provisioned among packets of the same traffic category, and lower-priority traffic categories may be allowed some bandwidth to avoid starvation. However, even though absolute differentiation may be realized in wired networks or single-hop wireless networks without difficulties, it is a problem that has never been solved in distributed multihop wireless networks, including ad hoc, mesh, and sensor networks. In this paper, we present a technique called "detached binary countdown", where the well-know binary countdown mechanism is applied before data packet transmission/reception, but with a gap between them. Different traffic categories have different ranges for their gaps, but contrary to intuition, the secret is to allow higher-priority traffic categories to use larger durations for their gap, granting them the privilege to reserve the channel earlier. As shown through a mathematical proof, absolute differentiation can be achieved by the technique. The technique is of significant theoretical importance in that it is the very first solution reported in the literature thus far that can achieve absolute differentiation in distributed multihop wireless networks with variable packet lengths. Detached binary countdown also leads to freedom from collision, and the hidden and exposed terminal problems naturally do not exist.

Quality-of-service (QoS) is among the most important issue for multimedia networking. In multihop wireless networks, high collision rates prevent TCP from provisioning reasonable QoS for time-sensitive ap- plications. Also, collisions disable the capability for QoS guarantee and large backoff time resulted from repeated collisions leads to intolerable delay and jitter. In this paper, we propose multi-narrow-band prohibition (MNBP) that can considerably reduce the collision rates or even achieve col- lision freedom (i.e., virtually 0% collision rate) in multihop networks such as wireless mesh, mobile ad hoc, and sensor networks. Smaller collision rates offer the basics for QoS provisioning; they also translate to higher energy efficiency, which is particularly important to mobile ad hoc net- works (MANET) and sensor networks. We apply MNBP to the multiple access collision prevention (MACP) scheme, leading to multi-narrow-band collision prevention (MNB-CP) that has strong QoS differentiation capabil- ity. We also apply MNBP to receiver-centric busytone, leading to mixed- band busytone multiple access (MBTMA) that is naturally asynchronous. Carefully-designed MNB-CP and MBTMA protocols can be made back- ward compatible to IEEE 802.11/11e/11s and other CSMA devices and/or frequency-hopping appliances even if those devices are not aware of the proposed techniques or equipped with busytone.

Wi-Fi mesh networks and WiMAX are two new emerging wireless access technologies for the delivery of broadband services to mobile users in the metropolitan area. To take advantage of the strengths of these two, we propose a novel architecture for next generation wireless metropolitan area networks. In this architecture, no wired backhaul connections for Wi-Fi mesh portals are needed, which considerably reduces the deployment cost and at the same time improves the system scalability. Due to the unique feature of wireless mesh networks which is a part of the architecture, previously proposed mobility management protocol can not work properly in this network environment. We propose a hierarchical mobility management scheme for mobile stations to maintain network connectivity while roaming within the Wi-Fi mesh networks. In this scheme, the dynamic forwarding chain is used to reduce the signalling traffic involved in the mobility management including registration and handoff procedures. The results of the performance evaluation justified the benefits of our proposed mechanism.

This paper proposes a multi-channel medium access control (MAC) protocol for wireless mesh networks (WMNs) by using busy tones to prevent data packet collisions at data channels. Multi-channel MAC schemes can achieve higher network throughput than single channel MAC schemes in multi- hop wireless networks. It is especially appealing to exploit multiple channels in WMNs which has high capacity requirement to support backbone multimedia applications. Most previously proposed MAC protocols make use of the RTS/CTS mechanism to deal with data packet collisions caused by exposed/hidden terminal problems in multi-hop environment. However, when multiple channels are used for data transmissions, the traditional RTS/CTS mechanism can no longer handle the exposed/hidden terminal successfully. By investigating the special features of WMN architecture, we apply the busy tone solution into the medium access control mechanism for WMNs, in which mesh nodes have no limit on power consumption. In this paper, we clearly presented the idea and operation of our proposed multichannel MAC protocol for WMNs. Comprehensive simulations are conducted to investigate the effects of various factors on the system performance. Also, the performance of our proposed mechanism is compared with that of previous RTS/CTS-based MAC protocols.

Extensive research work has been done to improve the performance of micro-mobility management schemes on handling fast moving mobile hosts within a local administrative domain. However, most of previous work is focused on reducing the location update cost and handoff latency, without considering any integrated form of quality of service (QoS). With the advancement of wireless access technologies and emergence of numerous multimedia applications over Internet, mobile users require not only the seamless mobility support but certain level of QoS guarantee. Multiprotocol Label Switching (MPLS) protocol has been developed as the solution to IP quality of service, gigabit forwarding, network scaling, and traffic engineering in Internet core network. Motivated by the advanced characteristics of MPLS technology, in this paper, we propose a MPLS-enabled micro-mobility management protocol which aims to enhance the end-to-end QoS provisioning and traffic engineering capabilities while dealing with intra-domain movement in all-IP future generation wireless networks.

Busytone was proposed three decades ago and has been the most famous solution to the hidden terminal problem. However, no busytone-based protocols have ever been deployed in practice. Most previous papers attributed this fact to its dual transceiver requirement, and some also pointed out the overhead and inefficiency problem due to the additional energy and bandwidth consumed by busytone. However, the actual issue that prevents busytone from being used for decades is the receiver busytone self-interference (RBTSI) problem. In short, the busytone signals transmitted by a receiver considerably interfere with its own data signal reception even if they are transmitted/received in different frequencies, since the busytone signal strength is significantly higher than the received data signal strength at the receiver location, and filters are not perfect. In this paper, we propose the detached busytone approach that transmits busytone signals before the associated data signals. This is the first busytone solution that can get around the aforementioned RBTSI issue. It is also the first continuous busytone solution that can support single transceiver per node. We also proposed the shortened busytone technique, which is the first solution that can address the dialogue-induced idleness problem. Both the proposed DBT approach and shortened busytone technique can be applied to various previous busytone-based protocols such as DBTMA and PCMA.

To achieve high throughput in wireless networks, collision rate must be very small, while communication overheads (e.g., RTS/CTS dialogues) and channel idleness (e.g., due to backoff) should be both relatively small as compared to data packet durations. Low collision rate is also essential to QoS provisioning in any network employing exponential backoff or a similar strategy. Our proposed solution to the preceding contradicting requirements is to employ prohibition-based mechanisms, which replace the functionality of RTS/CTS dialogues that have been shown to suffer from high communication overhead but only provide limited protection against the hidden terminal problem while in multihop networking environments. The resultant prohibition-based MAC protocols combine binary countdown with busytone, thus inheriting important advantages from both worlds including collision freedom/controllability, prioritization capability, and elimination of hidden terminals. They can also support asynchronous operations which are of practical importance.

In this paper, we propose the carrier sense multiple access with binary countdown (CSMA/BC) scheme for medium access control (MAC) in WLANs with crowded access points (APs) or mesh points (MPs), as well as mobile multihop networks such as ad hoc networks and multi- hop WLANs. CSMA/BC is a special case of the multiple access collision prevention (MACP) paradigm with novel dual prohibition mechanism with sender-oriented competition, where RTS/CTS-type dialogues are not em- ployed. Contrast to dual prohibition multiple access (DPMA), which uti- lizes dual competition, CSMA/BC-based protocols do not require prior ar- rangements between the sender-receiver pair for simultaneous competition. Important advantages of CSMA/BC over the CSMA/IC scheme include power control capability, resolution to the prohibition-range exposed termi- nal problem, interference awareness, and feasible prohibition ranges. Ad- vantages of CSMA/BC over IEEE 802.11/11e-type protocols include colli- sion freedom/controllability, strong differentiation capability, interference awareness, better spatial reuse, as well as being not vulnerable to colli- sions of RTS/CTS messages. Also, suitably-designed CSMA/BC protocols only require single transceiver per node and can be made backwards com- patible to IEEE 802.11/11e, which are critical advantages over previous busytone-based MAC protocols. We propose various CSMA/BC extensions that have their respective advantages, including single-channel CSMA/BC. When synchronization is feasible, CSMA/BC protocols and their variants appear to be strong candidates for multiple access in multihop networks as well as conventional single-hop WLANs but with crowded APs.

There are two main problems with the current paradigm for medium access control (MAC) in multihop wireless LANs, especially when quality of service (QoS) is required. The first is that it employs mandatory carrier sensing to avoid collisions, but such a transmitter- centric paradigm is vulnerable to the hidden terminal problem, and is inefficient in terms of spatial reuse especially when power controlled. The second is that it relies on RTS/CTS dialogues to mitigate the hidden terminal problem, but RTS/CTS messages are collision-prone and thus unreliable/ineffective for this purpose. In this paper, we propose a MAC scheme based on the receiver-centric paradigm called receiver prohibition multiple access (RPMA) with mixed-band busytone (MB) that can resolve the aforementioned problems. Advantages of RPMA-based protocols over IEEE 802.11/11e include collision freedom/controllability, higher energy efficiency, as well as being not vulnerable to collisions of RTS/CTS messages. Advantages of MB-based protocols over previous busytone protocols include the capability for interference prevention against CSMA or frequency-hopping devices that are not aware of busytone or MB. A resultant RPMA/MB protocol may be more complex and require additional hardware as compared to IEEE 802.11/11e, but it is expected to become feasible and competitive in cost with the advance of VLSI technology. Moreover, it can achieve the aforementioned advantages with backward compatibility to IEEE 802.11/11e, in the presence of other CSMA or frequency- hopping appliances.

In an ad hoc network, broadcast data communication is an unavoidable type of data transmission that provides synchronization, routing, and other messages to all the neighboring devices. Guaranteeing that all neighboring MTs receive broadcast messages is a hard task in multi-hop wireless ad hoc networks, especially when the traffic load is heavy. In this paper, we propose the sequential medium access control (SeMAC) protocol which aims at collision-free communication and reduced overhead for predictable broadcast message to sustain dynamic changes in network topology, as well as facilitate smooth operation of peer-to-peer unicast in multi-hop ad hoc networks SeMAC is intended to complement the IEEE 802.11 DCF function and is shown in this paper to greatly enhance the performance of broadcast and unicast communication of the IEEE 802.11.

In wireless sensor and pervasive networks, multihop networking is expected to be the norm, rather than exception. However, the current paradigm for medium access control (MAC) in wireless LANs/PANs cannot handle the interference issue well and lead to high collision rates in multihop networks, resulting in considerable waste of energy. Also, it is particularly beneficial to employ directional antennas in sensor networks due to its static topology and requirement for energy efficiency and security. In this paper, we propose to use in sensor and pervasive networks the receiver-centric interference management (RIM) method that supports directional antennas and spread scheduling. RIM for sensor networks employs directional busy-tone and/or directional receiver prohibition to coordinate RIM-aware devices and to protect them from legacy WiFi/CSMA devices. Advantages of RIM-based protocols include collision freedom/controllability, better interference robustness, higher energy efficiency, higher throughput, better security, as well as being not vulnerable to collisions of RTS/CTS messages.

The currently most popular medium access control (MAC) protocol, namely IEEE 802.11 distributed coordination function (DCF), is not energy efficient. In this paper we present the principles of achieving energy-efficiency in MAC protocol design for WLANs. Along these principles, we propose a novel dual-channel MAC protocol, called power-control binary-countdown-carrier-sense/request-to-send (RTS)/clear-to-send (CTS)/ensure-to-send (ETS) (PBRCE). PBRCE aims not only at energy-efficiency, but also at higher network throughput. The enhanced network performance is achieved by easing the "exposed terminal" and "hidden terminal" problems. The energy efficiency is achieved by reducing the collision rate-thus saving energy through avoiding retransmission of the same packets-and by controlling the signal transmission power and going to sleep mode to avoid the unnecessary passive listening

In next generation wireless networks, mobile users will roam across different wireless access networks. Mobile IP is employed as the mobility management protocol in the all-IP wireless environment. But mobile IP has scalability problem when dealing with micro-mobility and cannot provision QoS for multimedia applications of mobile users. In this paper, we propose dynamic hierarchical mobile MPLS (DHMM) protocol for micro-mobility management, at the same time facilitating the system with traffic engineering and QoS provisioning capabilities. By employing DHMM protocol in the all-IP wireless access network, the end-to-end delay can be considerably reduced and the traffic distribution in the network can be well balanced through MPLS traffic engineering.

In this paper, we investigate the ability of the standard IEEE802.11e to support quality of service (QoS) in wireless ad-hoc networks. Inspired by IEEE 802.11e, we propose the dual-channels request to send - RTS, clear to send CTS, and ensure to send -ETS (DRCE) scheme for effective quality of service (QoS) support in mobile ad hoc networks. We evaluate the performance of IEEE 802.11e and DRCE by simulation and find that the DRCE outperforms the IEEE 802.11e protocol in terms of average packet delay and network throughput by easing the "hidden terminal", and "exposed terminal" problem. Furthermore, the DRCE optimizes the QoS performance for different priority packets compared to IEEE 802.11e.

High collision rates in multihop wireless networks constitute an issue that has to be resolved in order to achieve satisfactory application quality in such networking environments. In this paper, we propose random ID countdown with ACK (RICK) based on dual prohibition for medium access control (MAC) in ad hoc networks, multihop wireless LANs, sensor networks, and mesh networks. RICK is a new collision-controlled multiple access (CCMA) protocol that can resolve several important problems encountered in previous MACP, CCMA, or RTS/CTS-based protocols, while improving/retaining their important advantages, including strong differentiation capability and the ability to reduce the collision rate and control it to a satisfactory level.

The carrier sense multiple access/ID countdown (CSMA/IC) is an emerging MAC protocol, designed for multi-hop ad hoc wireless networks, that differs from CSMA/CA. CSMA/IC is based on the binary countdown technique and, thus, fairness is commonly regarded at a disadvantage in this kind of MAC protocol. We propose the fair ID countdown (FIDC) scheme that only inserts one additional slot to the original protocol as an effective solution for the fairness problem. To prevent further nodal starvation in multi-hop environments, we also propose starvation-prevented FIDC. We show that our FIDC protocols can result in perfect fairness, without reducing the achievable network throughput.

This paper investigates the problem of optimal diverse routing for shared path-based protection in the complete routing information scenario on mesh optical networks, where a novel Integer Linear Programming (ILP) formulation is introduced such that the least-cost link-disjoint working and protection path-pair can be derived in a single step. The proposed ILP formulation is characterized by the facts that it is solvable with the commercially available Linear Programming (LP) solvers and that it can deal with the dependency between working and spare capacity in the network, which is a step ahead of the most state-of-the-art techniques in the design of diverse routing algorithms for shared protection. To verify the proposed ILP, an experiment is conducted to compare it with four reported schemes for end-to-end shared protection on two network topologies, namely APFPBC, MLR, ITSA, and ILP-2S, where blocking probability is taken as the performance metric with connection requests being dynamically launched into the networks. The simulation results show that the ILP formulation yields the best performance while the ILP-2S scheme investigating less network states yields the worst. We also use the results by the proposed ILP to evaluate the four heuristic-based schemes adopted in the simulation in terms of two performance indexes – the percentage of optimality (denoted as %opti) and the offset of optimality (denoted as Q).

In this paper, we investigate on penalty-based adaptable reservation admission (PARA) as an effective tool for quality of service (QoS) differentiation at the network layer and MAC layer. PARA enables resource reservation, allocation, and admission control to be adaptive to traffic conditions and the stress conditions at individual nodes. It also facilitates efficient differentiation between the service quality for applications with different QoS requirements, leading to an effective tool for DiffServ. Such capabilities are particularly useful for wireless networks and the Internet, resolving the QoS guarantee issues in the presence of mobility and bursty traffic. An important advantage and unique characteristic of PARA is that such differentiated service provisioning is under the control of network operators or individual nodes, in contrast to previous approaches in QoS adaptation. Our analytical results show that PARA can achieve considerably lower blocking rates for high-priority traffic as compared to previous resource management schemes without PARA.

Summary form only given. In random broadcasting, source packets that have to be broadcast to all the other nodes are generated at each node of a network or a parallel/distributed system at random instances. We propose several priority-based routing schemes for random broadcasting in general product networks and vertex and edge symmetric networks. Our goal is to achieve the maximum possible load factor /spl rho/ /spl ap/ 1 and optimal average reception delay (e.g., O(nd + 1/1-/spl rho/) at the same time. Our routing schemes are the first and only approaches reported in the literature thus far that lead to optimal throughput and average delay in many important networks, such as n-ary d-cubes, hypercubes, generalized hypercubes, and star graphs.

Summary form only given. Fast Fourier transform (FFT) is among the most important problems in computer science and engineering, with a variety of important applications including multimedia processing, communications, and numerical computation. Previous butterfly-based FFT implementations are not optimal even if the layouts employed are optimal for butterfly networks. We propose the expanded indirect swap networks (EISN) that is particularly suitable for FFT operations and have efficient layouts. Based on EISN, we propose the first and only optimal VLSI layouts (within a factor of 1+o(1)) reported in the literature thus far for performing FFT under the Thompson model, the extended grid model, and the multilayer 2D grid model. We show that N-point FFT circuits with throughput 1 (i.e., time I after pipelining) can be laid out with area N/sup 2//4/spl lfloor/L/sup 2//2/spl rfloor/+o(N/sup 2//L/sup 2/) and volume LN/sup 2//4/spl lfloor/L/sup 2//2/spl rfloor/+o(N/sup 2//L), under the multilayer 2D grid model where only one active layer (for network nodes) is required and L layers of wires are available, 2 /spl les/ L /spl les/ o(/spl I.nroot/N). We use AT/sup 2/L/sup 2/ or 2AT/sup 2//spl lfloor/L/sup 2//2/spl rfloor/ as a new parameter for characterizing the area-time complexity for multilayer VLSI, and show that AT/sup 2/L/sup 2/ /spl ap/ N/sup 2//2for N-point Fourier transform.

We investigate a new collision-free MAC protocol for ad hoc wireless networks, namely carrier sense media access/ID countdown (CSMA/IC), which can achieve 100% collision-free performance by solving both the "hidden terminal" and the concurrent sending problems. Furthermore, we propose an efficient ID assignment mechanism for CSMA/IC. With the new ID assignment mechanism, the length of the medium competition period before data transmission is greatly decreased. This further leads to an increase in network throughput, especially in high speed wireless networks.

In this paper, we propose an approach of optimal protection domain allocation, called OPDA (optimal protection domain allocation), for dynamically allocating spare capacity for a given working lightpath in WDM networks with partial wavelength conversion capability. The optimization process is formulated as a shortest path searching problem in a transferred graph of cycles and wavelength graph of paths. We conduct a series of experiments to verify the proposed approach on four networks with different topologies and traffic load. We conduct experiments to compare the blocking probability of using OPSA with four reported schemes. The results show that OPDA achieves the best performance.

In this paper, we propose the multichannel variable-radius multiple access (M-VRMA) scheme for power-controlled multichannel medium access control (MAC) in mobile ad hoc networks. We propose the RTS/object-to-sending (OTS)/VP-CTS (ROV) protocol based on M-VRMA, multiple access with lag time, OTS, and VP-CTS for efficient variable-radius supports in heterogeneous ad-hoc networks, without relying on busy-tone or any mechanisms that require expensive specialized hardware or more than one transceivers per device. Our simulation results demonstrate that for the same radio bandwidth, ROV can achieve considerably higher throughput as compared to fixed-radius IEEE 802.11 or previous power-controlled RTS/CTS protocols without variable-radius supports.

In this paper, we investigate a new class of collision-prevention MAC protocols, called carrier sense multiple access with collision prevention (CSMA/CP), for wireless ad hoc networks. We proposed a collision-free MAC protocol called BROADEN based on CSMA/CP. To the best of our knowledge, BROADEN is the first distributed MAC protocol that can achieve 100% collision-free transmissions in both the control channel and data channel in multihop ad hoc networks. Furthermore, BROADEN can solve the hidden, exposed, and moving terminal problems at the same time. It also improves the performance of previous MAC protocols in terms of average packet delay and network throughput. Moreover, our protocol effectively supports quality-of-service (QoS) provisioning based on prioritization and reservation.

We propose the robust middleware approach to transparent fault tolerance in parallel and distributed systems. The proposed approach inserts a robust middleware between algorithms/programs and system architecture/hardware. With the robust middleware, hardware faults are transparent to algorithms/programs so that ordinary algorithms/programs developed for fault-free networks can run on faulty parallel/distributed systems without modifications. Moreover, the robust middleware automatically adds fault tolerance capability to ordinary algorithms/programs so that no hardware redundancy or reconfiguration capability is required and no assumption is made about the availability of a complete subnetwork (at a lower dimension or smaller size). We also propose nomadic agent multithreaded programming as a novel fault-aware programming paradigm that is independent of network topologies and fault patterns. Nomadic agent multithreaded programming is adaptive to fault/traffic/workload patterns, and can take advantages of various components of the robust middleware, including the fault tolerance features and multiple embeddings, without relying on specialized robust algorithms.

We propose optimal VLSI layouts for butterfly networks under the multilayer 2-D grid model, the Thompson model, and the extended grid model. We show that an N-node butterfly network can be laid out with area N/sup 2///spl lfloor/L/sup 2//2/spl rfloor/log/sub 2//sup 2/N+ o(N/sup 2//L/sup 2/log/sup 2/N), volume LN/sup 2///spl lfloor/L/sup 2//2/spl rfloor/log/sub 2//sup 2/N+ o(N/sup 2//Llog/sup 2/N), and maximum wire length N//spl radic//spl lfloor/L/sup 2//4/spl rfloor/log/sub 2/N+o(N/LlogN) under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L wiring layers (for network links) are available, 2 /spl les/ L /spl les/ o(/spl I.nroot/N). We also show that the proposed multilayer butterfly layouts are optimal within a factor of 1+o(1) when adjacent wiring layers have orthogonal wires (to be referred to as X-Y layouts) and the area is calculated by a slanted encompassing rectangle. The proposed layouts are the first and only optimal butterfly layouts reported in the literature thus far for L /spl gsim/ 3, and match the best previous layout for L=2. We propose to use AT/sup 2/L2 or 2AT/sup 2/ /spl lfloor/L/sup 2//2/spl rfloor/ as a new parameter for characterizing the space-time complexity for multilayer VLSI, and show that AT/sup 2/L/sup 2//spl ap/ 2R/sup 2/for RxR butterfly networks, where R=N/log/sub 2/N+o(N/logN).

We propose a priority-based balanced routing scheme, called the priority STAR routing scheme, which leads to optimal throughput and average delay at the same time for random broadcasting and routing. In particular, the average reception delay for random broadcasting required in n/sub 1//spl times/n/sub 2//spl times/.../spl times/n/sub d/ tori with n/sub i/=O(1), n-ary d-cubes with n=O(1), or d-dimensional hypercubes is O(d+1/(1-/spl rho/)). We also study the case where multiple communication tasks for random 1-1 routing and/or random broadcasting are executed at the same time. When a constant fraction of the traffic is contributed by broadcast requests, the average delay for random 1-1 routing required in any d-dimensional hypercube, any n-ary d-cube with n = O(1), and most n/sub 1//spl times/n/sub 2//spl times/.../spl times/n/sub d/ tori with n/sub i/=O(1) are O(d) based on priority STAR. Our simulation results show that the priority-based balanced routing scheme considerably outperform the best previous routing schemes for these networks.

We propose the prioritized binary countdown (PBC) scheme for effective quality of service (QoS) supports in mobile ad hoc networks. We evaluate the performance of PBC, IEEE 802.11,802.11e, and two extensions to 802.11e in terms of their differentiation capability, throughput, delay, discarding ratio, blocking rate, and collision rate. Our simulation results show that PBC has considerably higher throughput and smaller delay, dropping ratios, blocking rates, and collision rates as compared to CSMA/CA of IEEE 802.11. We also show that PBC have considerably stronger differentiation capability than IEEE 802.11e and its extensions in multihop ad hoc networking environments

We introduce and evaluate the performance of penalty-based resource management (PRM) based on mathematical analysis. In PRM, the penalties associated with connections/sessions and packets facilitates efficient differentiation on delay, blocking/handoff-rejection rates, and utilizations between applications with different QoS requirements, lending itself to an effective tool for DiffServ in the next-generation wireless networks and Internet. An important advantage and unique characteristic of PRM is that such differentiated QoS provisioning is under the control of network operators, in contrast to previous approaches for QoS adaptation. We introduce several Markov fluctuated arrival rate (M-FAR) processes for realistic modeling and feasible analysis of heterogeneous wireless networks. We then present two approaches for the generation of arrival events and service times based on the proposed M-FAR Poisson processes. We derive the PRM theorem, which can provide the exact blocking rates for PRM as well as their closed-form upper and lower bounds. Our analytical results validate our previous simulation results for PRM, and show that PRM can achieve considerably lower blocking rates as compared to previous resource management schemes without PRM mechanisms.

In this paper, we propose a number of QoS differentiation mechanisms for heterogeneous wireless networks and the next-generation Internet. We propose distributed differential scheduling and prioritized k/sub i/-ary countdown for differentiated channel access in mobile ad hoc networks and multihop wireless LANs. We also propose a differentiated backoff control scheme for distributed flow control and DiffServ supports in ad hoc networks. The proposed mechanisms have considerably stronger differentiation capability as compared to IEEE 802.11e.

In this paper, we propose the interference-aware power-engineered multiple access (IPMA) protocol for medium access control (MAC) in ad hoc networks and multihop wireless LANs. IPMA is the first distributed MAC protocol that is interference aware without relying on busy tone or dual transceivers per mobile device. Enabled by its interference awareness, IPMA can naturally support efficient power-controlled variable-radius multichannel transmissions, power engineering, and directional antennas. Our simulation results demonstrate that for the same radio bandwidth, IPMA can achieve considerably higher throughput in ad hoc networks as compared to previous RTS/CTS protocols that are not interference aware.

In this paper, we propose time/space-division CDMA (TSD-CDMA), a TCDMA MAC protocol for 4th-generation (4G) integrated wireless networks. We propose several novel mechanisms for TSD-CDMA to work efficiently in combination with a distributed CDMA protocol. Such a complementary MAC approach greatly increases the scalability of TSD-CDMA networks. We propose novel approaches based on differentiated orthogonal-code channels and directional mutual interference metric for power-controlled variable-radius multiple access with directional antennas, leading to low power and high throughput. We also employ differentiated channel access, prioritized scheduling, differentiated CDMA disciplines, wireless MPLS, and several other QoS differentiation mechanisms for DiffServ and QoS guarantees in TSD-CDMA. We show through simulations that wireless tree channel access of TSD-CDMA can achieve high utilization and bounded delay, reducing the control channel overhead and enhancing its QoS provisioning capability.

In this paper, we present a new collision-free MAC protocol-carrier sense media access with ID countdown (CSMA/IC) for ad hoc wireless networks that can achieve 100% collision-free performance by solving the "hidden terminal" problem and the concurrent sending problem. Compared to CSMA/IC of IEEE 802.11, it also improves the network's performance in decreasing the network's throughput significantly. Furthermore, it can enable different packets with different priority to access the media and thus gain QoS.

In this paper, we present a new collision free MAC protocol-multi-channel binary-countdown-carrier-sense / Request-to-send (RTS)/Object-to-send (OTS) / Agree-to-send (ATS)/Disagree-to-send (DTS) / Ensure-to-send (ETS)/Neaten-to-send (NTS) (BROADEN) for ad hoc wireless networks that can achieve 100% collision free performance. Furthermore, it can totally solve the "exposed terminal", "hidden terminal", and "moving terminal" problems. It also decreases the bandwidth consumed per transmitted data packet and thus improve the network's performance in decreasing the average delay of packet sending, dropping discard ratio, and increase the network's throughput significantly. Finally, the scheme can enable different packets with different priorities access the media according to their priority level and thus gain their desired QoS.

In this paper, we present multiple access with lag time (MALT) for medium access control (MAC) with strong quality-of-service (QoS) supports and throughput-efficient power control in mobile ad hoc networks. On lop of conventional priority-based techniques such as different interframe spaces and backoff algorithms, MAPS supports effective differentiated service employing the distributed differentiated scheduling (DDS) to allow packets with higher priority or urgent deadline to schedule for a packet slot that is farther into the future. In this way, these higher-priority packets can schedule for their transmissions without competition from lower priority packets since the latter are not allowed to make reservation during slots with conflicting schedules yet. We demonstrate through simulations that MALT is considerably stronger than IEEE 802.11e and a power-controlled dual-channel variant of IEEE 802.11e in terms of its differentiation capability for delays, discarding/blocking ratios, and throughput. Our simulation results also show that MAPS can achieve higher throughput as compared to EDCF of IEEE 802.11e due to its supports for power-controlled variable-radius transmissions.

We propose an architecture for provisioning non-disrupted QoS guarantees in mobile ad hoc networks, and extend the scalable resource reservation protocol (SRRP) for signaling in ad hoc networks. In particular, we present a number of techniques that can enable QoS guarantees in ad hoc networks, including geographical reservation and clusterhead election (GRACE), the request-to-reserve/object-to-reserve/clear-to-reserve (ROC) reservation mechanism, and ad-hoc MPLS. We introduce a scalable adaptable reservation architecture (SARA) as a common architecture for reservation in SRRP. SARA is a scheme for signaling, reservation and QoS adaptation in ad hoc mobile wireless networks and which can also be used in the Internet. Finally, we propose geographical subpath protection, geographical circumscribed protection, and geographical extension protection with shared virtual reservation for non-disrupted QoS guarantees in the presence of interference, high mobility, bursty traffic, and/or other faults, without wasting expensive radio resources unnecessarily.

We propose a differentiated CDMA (D-CDMA) protocol for 3.5/sup th/-generation (3.5G) wireless cellular networks. D-CDMA employs an adaptive channel access scheme and a differentiated frame structure to support QoS differentiation and guarantee. From our simulation and analytical results, we show that D-CDMA with penalty-based adaptable reservation and admission (PARA) can achieve smaller blocking rate, given an arrival rate, and higher throughput, given a blocking rate objective, as compared to previous protocols without PARA.

We formulate array robustness theorems (ARTs) for efficient computation and communication on faulty arrays. No hardware redundancy is required and no assumption is made about the availability of a complete submesh or subtorus. Based on ARTs, a very wide variety of problem, including sorting, FFT, total exchange, permutation, and some matrix operations, can be solved with a slowdown factor of 1+o(1). The number of faults tolerated by ARTs ranges from o(min (n/sup 1-1/d/, n/d, n/h)) for n-ary d-cubes with worst-case faults to as large as o(N) for most N-node 2-D meshes or tori with random faults, where h is the number of data items per processor The resultant running times are the best results reported thus far for solving many problems on faulty arrays. Based on ARTs and several other components such as robust libraries, the priority emulation discipline, and X'Y' routing, we introduce the robust adaptation interface layer (RAIL) as a middleware between ordinary algorithms/programs and the faulty network/hardware. In effect, RAIL provides a virtual fault-free network to higher layers, while ordinary algorithms/programs are transformed through RAIL into corresponding robust algorithms/programs that can run on faulty networks.

An advantage of CDMA-based protocols is that packets can be transmitted immediately without prior channel access or resource reservation. In this paper, however, we propose to incorporate a reservation mechanism into CDMA-based protocols for next-generation wireless networks with data, voice, and multimedia applications. The resultant paradigm is called code division multiple access with adaptable reservation (CDMA/AR). The motivations for this change include that QoS guarantees can continue to be provisioned in CDMA/AR-based systems even when many handoff mobile stations enter an already heavily utilized cell. Our simulation results and mathematical analysis show that the adaptable reservation and differentiated admission control mechanisms of CDMA/AR can considerably reduce the handoff-rejection and call-blocking rates for higher-priority traffic to very small values, while achieving throughput close to 100% at the same time.

In this paper, we propose the Ad-hoc Cellular Network (ACENET), a heterogeneous wireless network architecture for 3.5-generation (3.5G) and fourth-generation (4G) mobile systems. We propose an IP-based integrated wireless routing scheme for the integration of heterogeneous wireless networking technologies in 3.5G and 4G ACENET. We also propose an integrated wireless MAC scheme for 4G ACENET. ACENET integrates cellular networks, wireless LAN, and ad hoc networks and enables heterogeneous wireless devices and technologies such as CDMA, IEEE 802.11, Bluetooth, and/or HiperLAN/2 to coexist and assist each other for communications with higher throughput, lower power, better quality-of-service (QoS), versatility, and low cost.

We propose a heterogeneous CDMA (H-CDMA) protocol, a time code division multiple access (TCDMA) protocol consisting of a centralized single-allocation function (CSF), a centralized multiple-allocation function (CMF), and a distributed multiple-allocation function (DMF). CSF or CMF can achieve high throughput and support differentiated service quality in conventional cellular networks without relaying capability or in dynamic cellular networks with multihop relaying capability, respectively, while CSF combined with DMF can transform a conventional cellular network into a dynamic cellular network. Moreover, DMF can considerably increase the scalability and efficiency of CMF by employing them concurrently. H-CDMA is designed for medium access control (MAC) in 4G wireless systems that integrate cellular networks, ad hoc networks, and wireless LANs, and provides an evolutionary path from the third-generation (3G) wireless systems to 3.5G and fourth-generation (4G) wireless networks such as ad hoc cellular networks (ACENETs).

In this paper, we show that N-point fast Fourier transform (FFT) circuits with throughput 1 (i.e., time 1 after pipelining) can be optimally laid out with area N2/(4⌊ L2/2 ⌋) + o(N2/L2) under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available, 2 ≤ L ≤ o(*√[3]N). We further propose AT2L2 or 2 AT2 ⌊ L2/2 ⌋ as a new parameter for characterizing the area-time complexity for multilayer VLSI, and show that AT2L2 ≈ N2/2 for N-point Fourier transform.

In this paper, we propose the Request-to-send/Object-to-send/Agree-to-send/Declare-to-receive (ROAD) medium access control (MAC) protocol for heterogeneous ad-hoc networking. ROAD can support both fixed-radius and variable-radius transmissions, either single-channel, dual control/data channel, or multichannel ad hoc networks, both unicast and reliable multicast, as well as prioritization and QoS guarantees. ROAD also enables several novel ad-hoc networking paradigms and switching techniques. Moreover, the techniques and mechanisms proposed for ROAD can be applied to obtain extensions to IEEE 802.11 and Bluetooth with better performance or stronger capability for coexistence.

During the past few years, IP with multiprotocol label switching (MPLS) over WDM has emerged as the paradigm of choice for the future optical Internet. However, MPLS is complex and does not take into account mobility in wireless networks, so the current version of MPLS cannot be applied to wireless networks to establish connections in an end-to-end manner. We propose ad hoc MPLS, a light-weight version of MPLS with an ad hoc LSP (label switched path) extension for the realization of end-to-end virtual-connection-oriented ad hoc networks, which in turn enables end-to-end QoS provisioning, traffic engineering and protection/restoration.

We propose differentiated engineered adaptable routing (DEAR) for quality-of-service (QoS) routing in ad hoc mobile wireless networks. In DEAR, traffic is engineered for both its locations (as in conventional traffic engineering) and its amount according to the proposed demand-engineered QoS routing. Moreover, QoS is provisioned in a differentiated manner through the proposed differentiated QoS routing, and is adaptable to traffic and network conditions through the proposed adaptable QoS routing. DEAR is generally applicable to previous routing paradigms and QoS routing algorithms based on on-demand, table-driven, or localized routing. We also develop DEAR STAR (selective table-driven ad hoc routing) and DEAR POWER (power-aware on-demand wireless embedded routing) to enable QoS-guaranteed and power-aware routing in ad hoc networks by utilizing stationary wireless stations and/or through dynamic maintenance of virtual stationary nodes. Finally, we apply backward learning to QoS routing in ad hoc networks.

We propose time division multiple access with circular reservation (TDMA/CR), a time/space division multiple access (TSDMA)-based medium access control (MAC) protocol for wireless mobile networks with control units, including wireless LANs, cellular networks with ad hoc relaying capability, and ad hoc networks with access points or clusterheads. Different from the MAC protocol of IEEE 802.11, TDMA/CR is centralized and can utilize the computation capability of base stations or access points to increase network throughput, reduce latency, and provide QoS guarantees. We evaluate the performance of TDMA/CR and show that the utilization achievable by the wireless-tree (or splitting) channel access mechanisms of TDMA/CR is about 40% to 46% and the channel access delay is small and bounded. Moreover, TDMA/CR can achieve considerably higher throughput (e.g., by a factor of about 3 or higher) due to its support for variable-radius transmissions in ad hoc wireless networks.

We introduce a variety of mechanisms to enable scalable, adaptive, and reliable quality of service (QoS) guarantees across heterogeneous networking environments. The resultant scalable resource reservation scheme (SRRS) is the first resource management scheme that provides efficient fault protection based on the virtual reservation mechanism and a penalty-based adaptable reservation mechanism, so that QoS can continue to be guaranteed in the presence of faults without wasting expensive network resources unnecessarily. Based on the proposed geographical reservation mechanism and virtual IP addressing, SRRS can enable QoS guarantees in ad hoc mobile wireless networks. Also, resource reservation and allocation in SRRS are adaptive to the networking environments so that wireless QoS-guarantee issues can be resolved in the presence of mobility, making SRRS suitable for wireless mobile networks. We evaluate the performance of SRRS based on simulation and analysis, and show that SRRS can achieve considerably lower blocking rates as compared to previous reservation protocols.

The index-permutation graph (IPG) model is a natural extension of the Cayley graph model, and super-IPGs form an efficient class of IPGs that contain a wide variety of networks as subclasses. In this paper, we derive a number of efficient algorithms and embeddings for super-IPGs, proving their versatility. We show that a multitude of important networks can also be emulated in super-IPGs with optimal slowdown. Also, the intercluster diameter average intercluster distance, and bisection bandwidth of suitably constructed super-IPGs are optimal within small constant factors. Finally we show that when parallel computers, built as multiple chip-multiprocessors (MCMP), are based on super-IPGs, they can significantly outperform those based on hypercubes, k-ary n-cubes, and other networks in carrying out communication-intensive tasks.

In this paper we propose a mathematical game, called the ball-arrangement game (BAG). A game with a different set of rules (e.g., permissible moves) gives rise to a different network, and the algorithm that solves the game gives rise to a routing algorithm in that network. Based on the insights provided by BAG, we propose several new classes of symmetric and modular networks, called super Cayley graphs, that have optimal (intercluster) diameters and average (intercluster) distances, small (intercluster) node degrees, high bisection bandwidth, strong embedding capability, and optimal communication algorithms given their (intercluster) node degrees.

We solve an open question posed by Akers and Krishnamurthy in 1986 concerning VLSI layout of star graphs. We show that the area of the optimal layout of an N-node star graph, hierarchical cubic network (HCN), or hierarchical folded-hypercube network (HFN) is N/sup 2//16/spl plusmn/o(N/sup 2/) under the Thompson model, or under the extended grid model where a node occupies a rectangle of sides that may range from n-1 to o(/spl radic/N) for the n-star, log/sub 2/N+1 to o(/spl radic/N) for the HCN, and log/sub 2/N+2 to o(/spl radic/N) for the HFN. An n-dimensional star graph this requires less area than any possible layout of a similar-size hypercube, but more than that of the much smaller n-cube. We also derive multilayer layout for star graphs that has area N/sup 2//8[L/sup 2//2]/spl plusmn/o(N/sup 2//L/sup 2/), where a node occupies a rectangle of sides ranging from [n-1/4] to o(/spl radic/N/L) and the number L of wiring layers satisfies 2/spl les/L=o(/spl radic/N/n). Finally we show that the bisection width of an N-node star graph is N/4/spl plusmn/o(N) and the bisection width of an HCN or HFN is exactly N/4.

We propose the robust algorithm-configured emulation (RACE) scheme for efficient parallel computation and communication in the presence of faults. A wide variety of algorithms originally designed for fault-free meshes, tori, and k-ary n-cubes can be transformed to corresponding robust algorithm through RACE. In particular optimal robust algorithms can be derived for total exchange (TE) and ascend/descend operations with a factor of 1+o (1) slowdown. Also, RACE can tolerate a large number of faulty elements, without relying on hardware redundancy or any assumption about the availability of a complete subarray.

We propose a scalable networking scheme for high-speed networks where quality of service (QoS) is important. The main objective of the scheme is to provide QoS guarantees and to achieve scalability to very large traffic volume and link bandwidth. Other important goals include extensibility, small to moderate buffer requirements, high throughput, small latency, and loss-free communication. The proposed scheme can service a wide variety of traffic classes and is applicable to various switching and multiplexing techniques.

Current VLSI technology allows more than two wiring layers and the number is expected to rise in future. In this paper we show that, by designing VLSI layouts directly for an L-layer model, the layout area for a variety of networks can be reduced by a factor of about (L/2)/sup 2/ compared to the layout area required under a 2-layer model, and the volume and maximum wire length can be reduced by a factor of about L/2, leading to considerably lower cost and/or higher performance. The proposed layouts for k-ary n-cubes, hypercubes, butterfly networks, cube-connected cycles (CCC), folded hypercubes, generalized hypercubes, k-ary n-cube cluster-c, hierarchical hypercube networks, reduced hypercubes, hierarchical swap networks, and indirect swap networks, are the best layouts reported for these networks thus far and are optimal within a small constant factor under both the Thompson model and the multilayer grid model. All of our layouts are optimally scalable in that we can allow each network node to occupy the largest possible area (e.g., o(N/L/sup 2/) for hypercubes) without increasing the leading constant of the layout area, volume, or maximum wire length.

We present a scheme for optimal VLSI layout and packaging of butterfly networks under the Thompson model, the multilayer grid model, and the hierarchical layout model. We show that when L layers of wires are available, an N-node butterfly network can be laid out with area 4N2/L2 log22 N + o (N2/L2 log2 N), maximum wire length 2N/L log2 N + o (N/L log N), and volume 4N2/L log22 N + o (N2/L log2 N) , under the multilayer 2-D grid model, where only one active layer (for network nodes) is required and L layers of wires are available.

In this paper, we present the index-permutation (IP) graph model, and apply it to the systematic development of efficient hierarchical networks. We derive several classes of interconnection networks based on IP graphs to achieve desired properties; the results compare favorably with popular interconnection networks, as measured by topological (e.g., node degree and diameter) and algorithmic properties, and are particularly efficient in view of their sparse inter-module communication patterns. In particular, the diameters of suitably-constructed super-IP graphs, a subclass of IP graphs, are optimal within a factor of 1+o(1), given their node degrees. The IP graph model can also be used as a common platform that unifies the architectures and algorithms for a vast variety of interconnection networks.

The Petersen graph is a Moore graph that has node degree 3, diameter 2, and optimal network size 10. In this paper, we present a class of interconnection networks, called cyclic Petersen networks (CPNs), which efficiently extend the Petersen graph to obtain larger networks with small diameter and node degree. We derive balanced routing algorithms and efficient embeddings for CPNs. In particular, we show that many normal mesh algorithms can be emulated on CPNs with a slowdown factor of about 1.1. We also show that complete CPNs can embed meshes, tori, meshes of trees, and folded Petersen networks with dilation 3, hypercubes and generalized hypercubes with dilation 4, and pyramids with dilation 5.

In this paper, we propose a new presentation of graphs, called the index-permutation (IP) graph model, and apply it to the systematic development of communication-efficient interconnection networks. We derive several new classes of interconnection networks based on IP graphs to achieve the desired properties. We show that the diameters of some classes of IP graphs are optimal within a factor of 1+0(1) given their node degrees. Designs based on IP graphs can balance system resources by appropriately selecting network parameters, thus providing adaptability to future technology and application requirements.

The dynamic broadcast problem is the communication problem where source packets to be broadcast to all the other nodes are generated at each node of a parallel computer according to a certain random process, such as a Poisson process. The lower bounds on the average reception delay required by any oblivious dynamic broadcast algorithm in a d-dimensional hypercube are /spl Omega/(d+1/1-/spl rho/) when packets are generated according to a Poisson process, where p is the load factor. The best previous algorithms for hypercubes only achieve /spl Omega/(d/1-/spl rho/) average reception delay. In this paper, we propose dynamic broadcast algorithms that require optimal O(d+1/1-/spl rho/) average reception delay in d-dimensional hypercubes and n/sub 1//spl times/n/sub 2//spl times//spl middot//spl middot//spl middot/n/sub d/ tori with n/sub i/=O(1). We apply the proposed broadcast scheme to a variety of other network topologies for efficient dynamic broadcast and present several methods for assigning priority classes to packets.

We propose a new class of interconnection networks, called macro-star networks, which belong to the class of Cayley graphs and use the star graph as a basic building module. A macro-star network can have node degree that is considerably smaller than that of a star graph of the same size, and diameter that is sublogarithmic and asymptotically within a factor of 1.25 from a universal lower bound (given its node degree). We show that algorithms developed for star graphs can be emulated on suitably constructed macro-stars with asymptotically optimal slowdown. This enables us to obtain through emulation a variety of efficient algorithms for the macro-star network, thus proving its versatility. Basic communication tasks, such as the multimode broadcast and the total exchange, can be executed in macro-star networks in asymptotically optimal time under both the single-port and the all-port communication models. Moreover, no interconnection network with similar node degree can perform these communication tasks in time that is better by more than a constant factor than that required in a macro-star network. We show that macro-star networks can embed trees, meshes, hypercubes, as well as star, bubble-sort, and complete transposition graphs with constant dilation. We introduce several variants of the macro-star network that provide more flexibility in scaling up the number of nodes. We also discuss implementation issues and compare the new topology with the star graph and other popular topologies.

In this paper we propose simple and efficient algorithms for sorting on incomplete meshes. No hardware redundancy is required and no assumption is made about the availability of a complete submesh. The proposed robust sorting algorithms are very efficient when only a few processors are faulty and degrade gracefully as the number of faults increases. In particular we show that 1-1 sorting (1 key per healthy processor) in row-major or snakelike row-major order can be performed in 3n+o(n) communication and comparison steps on an n/spl times/n incomplete mesh that has an arbitrary pattern of o(/spl radic/n) faulty processors. This is the fastest algorithm reported thus far for sorting in row-major and snakelike row-major orders on faulty meshes and the time complexity is quite close to its lower bound.

In this paper, we propose a new class of interconnection networks, called swapped networks, for general-purpose parallel processing. Swapped networks not only generate a wide class of high-performance interconnection networks, but also generalize, and serve to unify, many proposed parallel architectures as well as their algorithms. We show that swapped networks can efficiently emulate hypercubes, high-dimensional meshes, or generalized hypercubes, while having node degrees significantly smaller than the emulated network in each case. We also show that some subclasses of swapped networks can achieve asymptotically optimal diameters. Swapped networks are highly modularized, make the use of fixed-degree building blocks possible for any practically realizable system, and lead to the construction of high-performance scalable networks with reasonable cost.