4G systems employ discontinuous reception (DRX) mechanism to conserve energy by intermittently suspending network connections. Moving to 5G, a wide range of applications with diverse characteristics need to be supported. Especially, machine-type communication (MTC) has been identified as one of the three generic 5G services. Compared with that of human-type communication (HTC), the traffic patterns of MTC could be very bursty and even nonstationary. Thus, using the legacy DRX mechanism will cause longer access delay and/or higher power consumption. In this paper, we propose a new online learning-based DRX mechanism, called AC-DRX, with aim to improve device energy efficiency for MTC services by adapting to varying traffic pattern. In AC-DRX, the time is slotted into intervals and actor-critic (AC) algorithm is used for adjusting DRX cycles by learning the traffic statistics at the beginning of every time interval. To accelerate the learning process, we propose a symmetric sampling method in the AC algorithm. Numerical results show that our proposed AC-DRX mechanism significantly outperforms the legacy DRX and extended DRX mechanisms in terms of both delay and energy efficiency. The performance is fairly close to the upper bound where perfect traffic knowledge is assumed known.

To address the increase of multimedia traffic dominated by streaming videos, user equipment (UE) can collaboratively cache and share contents to alleviate the burden of base stations. Prior work on device-to-device (D2D) caching policies assumes perfect knowledge of the content popularity distribution. Since the content popularity distribution is usually unavailable in advance, a machine learning-based caching strategy that exploits the knowledge of content demand history would be highly promising. Thus, we design D2D caching strategies using multi-agent reinforcement learning in this paper. Specifically, we model the D2D caching problem as a multi-agent multi-armed bandit problem and use Q-learning to learn how to coordinate the caching decisions. The UEs can be independent learners (ILs) if they learn the Q-values of their own actions, and joint action learners (JALs) if they learn the Q-values of their own actions in conjunction with those of the other UEs. As the action space is very vast leading to high computational complexity, a modified combinatorial upper confidence bound algorithm is proposed to reduce the action space for both IL and JAL. The simulation results show that the proposed JAL-based caching scheme outperforms the IL-based caching scheme and other popular caching schemes in terms of average downloading latency and cache hit rate.

4G systems employ Discontinuous Reception (DRX) mechanism to conserve energy by intermittently suspend network connections. Moving to 5G, using the same DRX will cause longer access delay and higher power consumption for Machine-Type traffic. To address this problem, we propose to use actor- critic algorithm for choosing DRX cycles based on traffic statistics and to use symmetric sampling to accelerate online learning. Numerical results show that the new AC-DRX mechanism performs significantly better than DRX in both delay and energy efficiency. The performance is actually fairly close to the upper bound where perfect traffic knowledge is known.

The millimeter wave (mmWave) radio band is promising for the next-generation heterogeneous cellular networks (HetNets) due to its large bandwidth available for meeting the increasing demand of mobile traffic. However, the unique propagation characteristics at mmWave band cause huge redundant handoffs in mmWave HetNets that brings heavy signaling overhead, low energy efficiency and increased user equipment (UE) outage probability if conventional Reference Signal Received Power (RSRP) based handoff mechanism is used. In this paper, we propose a reinforcement learning based handoff policy named SMART to reduce the number of handoffs while maintaining user Quality of Service (QoS) requirements in mmWave HetNets. In SMART, we determine handoff trigger conditions by taking into account both mmWave channel characteristics and QoS requirements of UEs. Furthermore, we propose reinforcement-learning based BS selection algorithms for different UE densities. Numerical results show that in typical scenarios, SMART can significantly reduce the number of handoffs when compared with traditional handoff policies without learning.

The millimeter wave (mmWave) radio band is promising for the next-generation heterogeneous cellular networks (HetNets) due to its large bandwidth available for meeting the increasing demand of mobile traffic. However, the unique propagation characteristics at mmWave band cause huge redundant handoffs in mmWave HetNets if conventional Reference Signal Received Power (RSRP) based handoff mechanism is used. In this paper, we propose a reinforcement learning based handoff policy named LESH to reduce the number of handoffs while maintaining user Quality of Service (QoS) requirements in mmWave HetNets. In LESH, we determine handoff trigger conditions by taking into account both mmWave channel characteristics and QoS requirements of UEs. Furthermore, we propose reinforcement-learning based BS selection algorithms for different UE densities. Numerical results show that in typical scenarios, LESH can significantly reduce the number of handoffs when compared with traditional handoff policies.

Proper patrol route planning increases the effectiveness of police patrolling and improves public security. In this paper we present a new approach for the real-time patrol route planning in a dynamic environment. We first build a mathematic framework, and then propose a fast algorithm developed from the Cross Entropy method to meet the real-time computation requirement needed for many applications. In addition, as the randomness is an important factor for practices, the entropy concept is used for designing the randomized patrol routes schedule strategy. Numerical studies demonstrate that the approach has fast convergence property and is efficient in dynamic patrol environment.

Public security is a key concern around the world. Efficient patrol strategy increases the effectiveness of police patrolling and improves public security. In this paper we propose a new general security measure by defining the security level function. Based on this, we present the balanced patrol districting solution for the multiple units assignment problem. For the patrol routing problem in a patrol district, we first formulate the patrol routing process as a graph-based Markov decision process, and then propose an ε-optimal patrol routing strategy to deal with the curse of dimensionality. The strategy is derived based on the concept of ε-optimal horizon approximation. Numerical studies demonstrate that the strategy is adaptive to the generalized security measure by security level function, and has significant performance improvement over the referenced strategies in previous works. In addition, as the randomness is an important factor for practices, we design the randomized patrol routing strategy on the basis of the randomized exploration method in the Reinforcement Learning.

In the offering of broadband wireless services a common objective for a service provider (carrier) is to choose a resource allocation policy for multiple service classes that maximizes profit. However, when doing so the policy may not be utility-optimal. This causes users to decrease their consumption, which leads to a decrease of profit for service providers. Therefore, a service provider should choose a Pareto-efficient resource allocation policy so that both the profit of the service provider and the utility of the users can be optimally balanced. In this paper, we develop a framework for finding the necessary and sufficient condition for Pareto-efficiency, derive the Pareto-efficient resource allocation policies and propose an efficient solution for achieving it in Orthogonal Frequency Division Multiplexing systems.

The anti-collision mechanism is an important part in Radio-frequency Identification (RFID) technology. Recently, many anti-collision algorithms were designed based on the EPCglobal standards. These works mainly focused on the tag population estimation. But they chose frame size based on the classical results of Random Access (RA) systems. We show that a new theory is needed for the optimization of the RFID systems as they have characteristics very different from the RA systems. We model the reading process as a Markov Chain and derive the optimal reading strategy through first-passage-time analysis. We show that the optimal strategy can be easily incorporated into the EPCglobal standards to give significant performance improvement.

The anti-collision algorithm is an important part of the Radio-Frequency Identification (RFID) system. Of the various possible algorithms, the Framed Aloha based (FA) algorithms have been most widely used due to their simplicity and robustness. Previous studies have focused mainly on the tag population estimation, choosing the frame size based on the classical results of Random Access (RA) systems. We show that a new theory is needed for algorithm design for RFID systems, because RFID and RA systems are fundamentally different. The Philips RFID system is studied in this paper. We model the reading process as a Markov Chain and derive the optimal reading strategy by first-passage-time analysis. The optimal frame sizes are derived analytically and numerically.

The anti-collision mechanism is a very important part in RFID systems. Among all the algorithms, the Framed Aloha based (FA) ones are most widely used due to its simplicity and robustness. Previous works mainly focused on the tag population estimation, but determined the reading strategy based on the classical results of Random Access (RA) systems. We show that a new theory is needed for the optimization of the RFID systems as they have characteristics very different from the RA systems. We model the reading process as a Markov Chain and derive the optimal reading strategy through first-passage-time analysis. We show that the optimal strategy can be easily incorporated into the EPCglobal standards to give significant performance improvement.

In the broadband mobile service market, it is reasonable that the carrier (service provider) should choose a Pareto-efficient resource allocation policy so that both the revenue of the carrier and the utility of users can be maximized. In this paper, we investigate the fundamental problem of the existence of resource allocation policies that are Pareto-efficient between the revenue and the utility. We show that the revenue-maximizing policy is not always equal to the utility-maximizing policy and that the two distinct policies, if any, generate a set of Pareto-efficient resource allocation policies. To make a Pareto-efficient resource allocation schedule, we develop a mathematical framework, where we study the existence of the Pareto-efficient policies, a necessary and sufficient condition for Pareto-efficiency, which can be used for finding the set of all the Pareto-efficient policies, and an efficient and exact solution method to find a Pareto-efficient resource allocation schedule.

The anti-collision mechanism is a very important part in Radio-frequency Identification (RFID) systems. Among all the algorithms, the Framed Aloha based (FA) ones are most widely used due to simplicity and robustness. Previous works mainly focused on the tag population estimation, but determined the reading strategy based on the classical results of Random Access (RA) systems. We show that a new theory is needed for the optimization of the RFID systems as they have characteristics very different from the RA systems. In this paper, We propose a new approach to minimize the total expected reading time by choosing the most suitable frame size based on the tag population distribution. We show that the optimal strategy can be used in different applications. The mathematical analysis and computer simulation show our approach outperforms the previous optimization works in the literature.

In this paper, we study precise localization using Angle of Arrival (AOA) estimations by smart-antenna equipped beacons in Ad-Hoc networks. The node to be localized sends a signal to its surrounding beacons. The beacons estimate the signal directions with high resolution AOA methods and feed them back to the node for position calculation. In other words, position calculation is not required at beacons. When AOA estimates from three or more beacons are received, ambiguity occurs. Three resolution methods, namely (a) simple averaging (b) Minimax and (c) Precision-weighted averaging are proposed and compared. As estimation bias is heavily dependent on antenna orientations the center-facing approach is found to give better performance in a square field.

We present a new method for data gathering that maximizes lifetime for wireless sensor networks. It involves three parts. First, nodes organize themselves into several static clusters by the Hausdorff clustering algorithm based on location, communication efficiency and network connectivity. Second, clusters are formed only once but the role of cluster-head is optimally scheduled among the cluster members. We formulate the cluster-head scheduling that maximizes the network lifetime as an integer programming problem and propose a greedy algorithm for its solution. Third, after cluster-heads are selected, they form a backbone network to periodically collect, aggregate, and forward data to the base station, where a minimum energy (cost) routing is used. Comparing with other known methods, significant lifetime extension is obtained with the use of this method.

This paper presents a new method for subcarriers and power allocation for orthogonal frequency division multiple access (OFDMA) with the purpose of minimizing the instantaneous buffering latency of all users. Numerical results show that the average packet delay can be reduced by up to 50% and the spectrum utilization can be increased by 0.5 bits/s/Hz when compared to the scheme used in IEEE 802.16a.

Sleeping scheduling is a common energy-conservation solution for sensor networks. For application whereby coordination of sleeping among sensors is not possible or inconvenient, random sleeping is the only option. In this article, we study the asynchronous random sleeping(ARS) scheme whereby sensors (i) do not need to synchronize with each other, and (ii) do not need to coordinate their sleeping schedules. The stationary coverage probability and the expected coverage periods for ARS are derived. For surveillance application, we derive in addition the detection probability and detection delay distribution. The correctness of our results is validated through extensive simulations. We compare ARS with other synchronous and asynchronous sleeping scheduling algorithms and show that ARS offers better performance in terms of detection delay in the lower duty-cycle regime. We also conduct simulations to demonstrate that our results can be a good approximation for clock drifting case.

Prefix-randomized query-tree (PRQT) protocol has been proposed for multiple tag identification in RFID systems. The optimal performance of PRQT can be achieved with a proper choice of the initial prefix length according to the tag set size. In this paper, we propose an initial prefix length adaptation algorithm for PRQT protocol when the tag set size is unknown before identification. The algorithm starts with the setting of a small initial prefix length l followed by the polling of all 2lprefixes. The initial prefix length is then increased repeatedly until the collision ratio satisfies a prescribed condition. We derive the optimal increment step size and the respective sequence of decision thresholds. Simulation results show that PRQT with initial prefix length adaptation can significantly reduce the expected tag read time for all range of tag set size when compared to the use of query-tree protocol.

In this paper we present a new tree search-based protocol for the anti-collision problem of RFID systems. This protocol builds a binary search tree according to the prefixes chosen randomly by tags rather than using their ID-based prefixes. Therefore, the tag identification time of the proposed protocol is no longer limited by the tag ID distribution and ID length as the conventional tree search protocol. The time complexity of the protocol is derived and shown that it can identify tags faster than the Query-Tree protocol.

This paper presents DONet, a data-driven overlay network for live media streaming. The core operations in DONet are very simple: every node periodically exchanges data availability information with a set of partners, and retrieves unavailable data from one or more partners, or supplies available data to partners. We emphasize three salient features of this data-driven design: 1) easy to implement, as it does not have to construct and maintain a complex global structure; 2) efficient, as data forwarding is dynamically determined according to data availability while not restricted by specific directions; and 3) robust and resilient, as the partnerships enable adaptive and quick switching among multi-suppliers. We show through analysis that DONet is scalable with bounded delay. We also address a set of practical challenges for realizing DONet, and propose an efficient member and partnership management algorithm, together with an intelligent scheduling algorithm that achieves real-time and continuous distribution of streaming contents. We have extensively evaluated the performance of DONet over the PlanetLab. Our experiments, involving almost all the active PlanetLab nodes, demonstrate that DONet achieves quite good streaming quality even under formidable network conditions. Moreover, its control overhead and transmission delay are both kept at low levels. An Internet-based DONet implementation, called CoolStreaming v.0.9, was released on May 30, 2004, which has attracted over 30000 distinct users with more than 4000 simultaneously being online at some peak times. We discuss the key issues toward designing CoolStreaming in this paper, and present several interesting observations from these large-scale tests; in particular, the larger the overlay size, the better the streaming quality it can deliver.

In order to enable fast deployment of new emerging services over multihop wireless networks, it is important to design an efficient service-based platform with the necessary traffic management capabilities. In this paper, we propose a new distributed service-oriented framework for wireless multihop networks, called MultiServ, in which it adopts a quantitative approach toward optimal traffic distribution. Under Multiserv framework, an efficient overlay network can be easily constructed that can greatly facilitate the deployment of new services. We use media streaming and application level multicast as examples to illustrate how the services can be supported. The performance results demonstrate that MultiServ can substantially outperform the conventional approach and achieves comparable performance obtained by a centralized scheme.

The random access channel (RACH) in a universal terrestrial radio access-frequency division duplex (UTRA-FDD) system is a contention-based channel mainly used to carry control information from mobile stations (MS) to base stations (BS). The transmission of a random access request contains two steps: preamble transmission and message transmission. In preamble transmission, the power ramping technique is used to favor the delayed preambles by stepping up the transmission power after each unsuccessful access. In doing so, the success of transmitting a long-delayed preamble is increased due to the power capture effect. This paper analyzes the blocking, throughput, and delay performance of preamble transmission under three power ramping schemes with fixed, linear, and geometric step sizes. The interference caused by different power ramping schemes is also compared.

The random access channel (RACH) in a universal terrestrial radio access frequency division duplex (UTRA-FDD) system is a contention-based channel mainly used to carry control information from mobile stations to base stations. The transmission of a random access request contains two steps, preamble transmission and message transmission. In preamble transmission, a power ramping technique is used to favor the delayed preambles by stepping up the transmission power after each unsuccessful access. In doing so, the success of transmitting a long-delayed preamble is increased due to the power capture effect. We analyze the blocking and throughput performance of preamble transmission under three power ramping schemes with fixed, linear and geometric step sizes. Also, we compare the interference caused by different power ramping schemes.

In universal terrestrial radio access (UTRA) systems, orthogonal variable spreading factor (OVSF) codes are used to support different transmission rates for different users. In this paper, we first define the flexibility index to measure the capability of an assignable code set in supporting multirate traffic classes. Based on this index, two single-code assignment schemes, nonrearrangeable and rearrangeable compact assignments, are proposed. Both schemes can offer maximal flexibility for the resulting code tree after each code assignment. We then present an analytical model and derive the call blocking probability, system throughput and fairness index. Analytical and simulation results show that the proposed schemes are efficient, stable and fair.

The delay differentiated service was proposed as a DiffServ model to provide quality of service (QoS) guarantee on the Internet. In this model, packets are scheduled for transmission according to some specific delay metrics. waiting time priority (WTP) is one of this kind of scheduling algorithms that assign the priority to the packet according to its waiting time. WTP incurs implementation difficulty due to its computational complexity. In this paper, we propose a modified algorithm based on WTP called shifted waiting time priority (S-WTP). S-WTP reduces the computational complexity of WTP from O(n) to O(log(n)) without losing the basic functionality of WTP. Simulation results illustrate the effectiveness of S-WTP for delay differentiated service.

In this paper, a novel model named MultiServ is proposed to alleviate the congestion and to provide better quality of service for end-host using overlay network. In MultiServ, a special overlay is built so that end-host and its neighbors can cooperatively transmit data efficiently. Meanwhile, a joint congest control scheme is proposed for multiple path data transmission. As a result, the traffic in the underlying network can be balanced and smoothed and the congestion can be alleviated or avoided. This provides a promising solution for application with demand of good quality of service for throughput sensitive transmissions.

We derive the closed-form delay distributions of slotted ALOHA and nonpersistent carrier sense multiple access (CSMA) protocols under steady state. Three retransmission policies are analyzed. We find that under a binary exponential backoff retransmission policy, finite average delay and finite delay variance can be guaranteed for G<2S and G<4S/3, respectively, where G is the channel traffic and S is the channel throughput. As an example, in slotted ALOHA, S<(ln2)/2 and S<3(ln4-ln3)/4 are the operating ranges for finite first and second delay moments. In addition, the blocking probability and delay performance as a function of r/sub max/ (maximum number of retransmissions allowed) is also derived.

In UTRA systems, orthogonal variable-spreading-factor (OVSF) codes are used to support different transmission rates for different users. In this paper, we first define an index for measuring the flexibility of an assignable code set. Based on this flexibility index, a single-code assignment scheme, namely rearrangeable compact assignment (RCA), is proposed for accommodating multi-rate traffic. RCA can offer maximal flexibility to the resulting assignable code set after each code assignment. Analytical and simulation results show that RCA is efficient, stable and fair.

In this paper, we propose a scheme for implementing multiparty videoconferencing service on SONET/ATM rings. We focus on the architectural design and bandwidth demand analysis. Different multicasting methods on SONET/ATM rings are discussed and compared. A new multicast virtual path (VP) called "Multidrop VP" which is particularly suitable for SONET/ATM rings is proposed. An add-drop multiplexer (ADM) structure for rings capable of multidropping is also presented. Several VP assignment schemes are proposed and their bandwidth utilizations are compared.

The random access channel (RACH) in UTRA-TDD is defined as an uplink contention-based transport channel that is mainly used to carry control information from mobile stations to base stations. We study the throughput performance of RACH on an additive white Gaussian noise (AWGN) channel whereby successful transmission of a burst requires the spreading code chosen to be collision-free and the burst error-free after convolutional decoding. Based on this model, the code-collision probability, the data bit error probability and the RACH channel capacity are derived. For spreading factor Q equal to 8 or 16 as specified in the standard, the maximum throughput obtained is 1.74 and 3.67, respectively.

In UTRA systems, orthogonal variable-spreading-factor (OVSF) codes are used to support different transmission rates for different users. In this paper, we first define an index for measuring the flexibility of an assignable code set. Based on this flexibility index, a single-code assignment scheme, namely nonrearrangeable compact assignment (NCA), is proposed for accommodating multi-rate traffic. NCA can offer maximal flexibility to the resulting assignable code set after each code assignment. As a result, it gives better blocking, throughput and fairness performance when compared to random assignment (RA) scheme.

The performance of today's database systems is usually limited by the speed of their I/O devices. Fast I/O systems can be built from an array of low cost disks working in parallel. This kind of disk architecture is called RAID (Redundant Arrays of Inexpensive Disks). RAID promises improvement over SLED (Single Large Expensive Disks) in performance, reliability, power consumption, and scalability. However, a general fact about RAID is that the "write" operation is difficult to speedup. In this paper, we propose a new RAID architecture, called Dynamic Multiple Parity (DMP) Disk Array, for serial transaction processing database systems. Serial transaction processing database systems include engineering database systems, fully replicated database systems using a completely centralized algorithm and distributed systems using the conservative timestamp ordering algorithm. DMP Disk Array can significantly increase the I/O throughput by incorporating multiple parity disks. Due to the inherent distributed sparing property, DMP Disk Array can provide normal service to the users under single disk failure condition. Delay and maximum throughput analysis on DMP Disk Array is performed. Results show that, for a typical "write" job proportion of 20 percent, DMP Disk Array can provide nearly 20 percent improvement on I/O throughput over that of RAID level 5 when one extra parity disk is used.

Dynamic routing has been adopted in circuit-switched networks in many parts of the world. Most of the routing algorithms used are least loaded routing (LLR) based for its simplicity and efficiency. Rerouting is the practice of routing calls on alternate paths back to direct paths or to other less congested alternate paths. It allows the continuous redistribution of network loads for the relief of the congestion on direct paths. In this paper, we present an original analysis of an LLR-based rerouting scheme. Through numerical examples and confirmation by computer simulation, the throughput gain of rerouting is established.

This paper presents the dynamic reservation protocol for supporting variable-rate data services on time-division multiple-access based wireless networks. It allows a large number of data terminals to access data applications by sharing a reserved data-carrier. Through dynamic reservation data terminals can get their needed radio channels for uplink transmission without contention. The protocol performance is evaluated by queuing analysis and verified by computer simulation.

In this paper, we study the use of reroutable assignment for multipoint videoconferences in a high-speed network. A conference model is constructed and conference calls are classified. A conference of a particular type can ride on different route-configurations. According to the location of the current speaker, a conference has different modes of operation. Two network management functions are discussed: call admission ensures a preset quality-of-service requirement by blocking new calls that causes congestion; route-configuration assignment determines the multicast tree for distributing the video of the current speaker. The reroutable route-configuration assignment is introduced. It allows a change of route-configuration when there is a change of speaker. Two reroutable assignment schemes are studied. In the normal scheme, a conference is always rerouted to the least congested route-configuration; while in the sticky scheme, a conference is only rerouted when the current route-configuration is congested. The video freeze probability, rerouting probability and the extended capacity space are derived. An example shows that the video freeze probabilities of the two schemes do not differ significantly. The sticky scheme, however, is superior as it gives a much smaller rerouting probability than the normal scheme. © 1998 John Wiley & Sons, Inc.

Node placement problem in ShuffleNets is a combinatorial optimization problem. In this paper an efficient node placement algorithm, called the gradient algorithm, is proposed. A communication cost function between a node pair is defined and the gradient algorithm places the node pairs one by one, based on the gradient of the cost function. Then two lower bounds on the traffic weighted mean internodal distance h are proposed. The performance of the gradient algorithm is compared to the lower bounds as well as to some algorithms in the literature. Significant reduction of h is obtained with the use of the gradient algorithm, especially for highly skewed traffic distributions. For a ShuffleNet with N=64 nodes, the h found is only 22% above the lower bound for the uniform random traffic distribution, and 14.7% for a highly skewed traffic distribution with skew factor /spl gamma/=100.

A multirate network can support services with different bandwidth requirements, service characteristics and revenue earning rates. In this paper we compare four call admission policies under the least congestion adaptive routing rule in a multirate network. The purpose of call admission control is to prevent the dominance of network capacity by a particular class of calls. Analysis on fully connected networks shows that the limited occupancy (LO) and the guaranteed bandwidth (GB) policies can all be used to manipulate the relative blocking probabilities of different classes of calls provided that the bandwidth reservation parameters are suitably selected. On the other hand, they all tend to reduce the revenue of the network when compared to the complete sharing (CS) policy. The direct-link packing (DP) policy, however, is found to give significant reductions in both blocking probabilities and revenue loss when compared to the CS policy. Thus the DP policy offers the best overall performance under the least congestion routing rule.

This paper presents a new media access control protocol for multi-priority multi-rate data services on GSM networks. In this protocol, which we named dynamic reservation protocol, data terminals can get their uplink channels through contention-free reservation. Therefore this protocol can achieve very high channel utilization efficiency and can significantly improve the service performance under heavy traffic load. The reservation scheme can adapt to traffic variations, by dynamically changing the transmission cycle length. Simulation results show that this protocol offers significantly better delay/throughput performance when compared to other protocols proposed in the literature. Since this protocol is built on the top of the GSM physical layer, its implementation should be very straight forward.

Dynamic routing has been adopted in many circuit switched networks in many parts of the world. A number of dynamic routing schemes have been designed and studied with the aim of maximizing the network throughput. The least loaded routing (LLR) is simple and efficient, while other more elaborate routing schemes can only provide marginal throughput gain over that of LLR. Re-routing is the practice of routing calls on alternate paths to direct paths or other less congested alternate paths. It allows the continuous redistribution of network loads so that the congestion on direct paths can be relieved. We study a re-routing scheme based on LLR. An original analysis of re-routing is performed and numerical examples confirm the significant throughput gain over LLR routing.

This paper describes a two tier architecture for high speed data distribution. The architecture consists of a database interface network which distributes information from a central database to a number of servers, and a user interface network which distributes information from the servers to the user terminals. The database interface network uses the Selective Broadcast technique to distribute data on a high speed channel. Analytical results and design examples showed that Selective Broadcast technique can provide an order of magnitude smaller response time under normal traffic conditions when compared to the nonselective broadcast technique such as the Datacycle/sup TM/ system.

A new packet switch architecture using two sets of time-division multiplexed buses is proposed. The horizontal buses collect packets from the input links, while the vertical buses distribute the packets to the output links. The two sets of buses are connected by a set of switching elements which coordinate the connections between the horizontal buses and the vertical buses so that each vertical bus is connected to only one horizontal bus at a time. The switch has the advantages of: (1) adding input and output links without increasing the bus and I/O adaptor speed; (2) being internally unbuffered; (3) having a very simple control circuit; and (4) having 100% throughput under uniform traffic. A combined analytical-simulation method is used to obtain the packet delay and packet loss probability. Numerical results show that for satisfactory performance, the buses need to run about 30% faster than the input line rate. With this speedup, even at a utilization factor of 0.9, each input adaptor requires only 31 buffers for a packet loss rate of 10/sup -6/. The output queue behaves essentially as an M/D/1 queue.

A state reduction technique for the exact analysis of fork/join queueing systems is presented in this paper. The technique is based on the standard Markov model and can be applied to systems having K homogeneous exponential servers. For a closed system with M jobs, the technique reduces the size of the state space from (M+1)/sup K/-M/sup K/ states to (M+K-1/K-1) states. This amounts to more than five orders of magnitude of state reduction for a typical value of K=M=10. The state reduction technique can also be applied to the analysis of an open fork/join queueing system. It reduces the size of the state space from (B+1)/sup K/ states to (B+K/K) states where B is the maximum number of jobs allowed in the open queueing system. The state reduction amounts to more than six orders of magnitude for a typical value of K=10 and B=500.

Since call termination as a result of handoff failure is considerably less desirable from the user's viewpoint than the blocking of a new call, a prioritized handoff scheme is essential. Especially for microcellular systems where the mobile cell boundary crossing rate is high. Therefore an efficient DCA should give priority to handoff calls. Two DCA strategies for prioritized handoff are proposed based on a DCA called BDCL (borrowing with directional channel locking): (i) FCA with BDCL for handoff calls, and (ii) BDCL with channel reservation. FCA with BDCL for handoff calls allows a handoff call to borrow a channel using BDCL strategy if no free nominal channel in the call arrival cell is available. In BDCL with channel reservation, both the new call and handoff call can use a borrowed channel. But a fixed number of nominal channels in a cell are reserved for exclusive use of handoff calls. To study the performance of the two proposed strategies, a widely accepted mobility model is adopted. Based on this model, we derive the handoff call arrival rates and channel holding time from the given mean mobile speed. The performance of the two proposed algorithms is studied by simulations and we found that they are very effective in reducing the handoff call blocking probability while not affecting the new call performance.

This paper describes a two tier architecture for high speed data distribution. The architecture consists of a database interface network which distributes information from a central database to a number of servers, and a user interface network which distributes information from the servers to the user terminals. The database interface network uses the selective broadcast technique to distribute data on a high speed channel. Data requested by users are filtered out by the servers and sent to the user terminals through the user interface network. The user interface network can be any conventional local area network for connecting the servers and the user terminals. A very tight upper bound on the mean response time of the system for uniform request distribution is first derived. This is followed by an approximate analysis for general request distributions. Simulation results and design examples showed that selective broadcast technique can provide an order of magnitude smaller response time under normal traffic conditions when compared to the nonselective broadcast technique such as the Datacycle system.

We develop a simple but very accurate analytical model for a channel borrowing based dynamic channel assignment strategy in linear microcellular systems. Our approach is to decouple a particular cell together with its neighbors, i.e., those cells under its interference range, from the rest of the system for finding the blocking probability of that cell. We call this the cell group decoupling analysis. This analysis is applicable to both homogeneous and heterogeneous traffic distributions. We show that the effect of this decoupling causes the blocking probability so obtained to be an upper bound. The bound is found to be very tight when compared with simulation results. Besides, this analysis gives accurate results to boundary cells as well as inner cells, and is therefore quite different from the other approaches which neglect boundary effects.>

To ensure the quality of a multimedia teleconference, it is essential that sufficient bandwidth be allocated for its use. In this paper a conference traffic model is formulated and link level and conference level congestion measures are derived. Motivated by the advantages of sharing transmission resources in TASI related voice communication systems, an analogous transmission policy for conference videos is proposed. The quantification of conference traffic also enables us to set an admission policy so that the network can accommodate as many conferences as possible without violating conference quality constraints.>

A (p,k) ShuffleNet is a type of regular multihop network with kp/sup k/ nodes. If only some of the nodes are extraordinarily busy, these so-called active nodes can be assigned to specific ShuffleNet locations to minimize the average hop count. An exhaustive search for the optimal node placement is not feasible for any reasonable size networks, particularly for networks requiring frequent reconfigurations, i.e. adding and dropping active nodes and changing traffic rates. The authors propose a computationally efficient algorithm that can give near optimal solution to the above problem. The procedures of adding and dropping of active nodes are also described.>

Analyzes an adaptive routing rule in a WDM lightwave network. Each switching node in the network may have a number of wavelength converters which can be used to resolve wavelength conflicts in multi-hop paths. The authors found that without any wavelength converters, the wavelength conflict possesses an inherent blocking to alternate route traffic and that the use of wavelength converter to resolve wavelength conflicts does not give any significant reduction of blocking probability.>

In this paper, we propose the phantom cell analysis for dynamic channel assignment. This is an approximate analysis that can handle realistic planar systems with three-cell channel reuse pattern. To find the blocking probability of a particular cell, two phantom cells are used to represent its six neighboring cells. Then by conditioning on the relative positions of the two phantom cells, the blocking probability of that particular cell can be found. We found that the phantom cell analysis is not only very accurate in predicting the blocking performance but also very computationally efficient. Besides, it is applicable to any traffic patterns and any cellular layouts.>

The Maximum Mean Time to Blocking (MTB) Routing is a state- and time-dependent adaptive routing scheme. In this scheme, overflowed calls are routed to an alternate path having the longest mean time to blocking. The mean time to blocking of a link is a function of the trunk group size, the traffic rate, and the instantaneous trunk group occupancy and is a particularly suitable measure of the busy status of links in networks with nonuniform trunk group sizes and asymmetric traffic rates. The computation of the mean time to blocking of a path is very demanding and two approximations are proposed. A comparative performance evaluation through a call-by-call computer simulation shows that the MTB routing can give a superior throughput-blocking performance.>

A new distributed protocol which supports concurrent message transmissions on different ring segments in a ring network is proposed. This protocol allows the destination station to remove the message body from the ring and to issue a new token for the succeeding stations to establish another transmission in the remaining ring segment. This protocol requires only one-bit latency at each station and supports variable size messages. We derived the maximum throughput of the pipeline ring and found it to be heavily dependent on the message size distribution. The maximum throughput of a single ring for exponential messages and fixed size messages are 1.23 and 1.68 respectively; while for the double ring, the per-ring throughput is 1.7 and 3.25 respectively. Due to analytical complexity, the delay performance is obtained by simulation. Two service disciplines are compared. It is found that the furthest within segment (FWS) discipline always performs better than the first come first serve (FCFS) discipline. The short message transmission scheme is introduced. Under bimodal traffic, it can significantly increase the ring efficiency.>

In this paper we present an address coding mechanism for multicast source routing packets in packet-switched networks. A simple algorithm for processing these address codes at intermediate output link adaptors is presented. It involves only the recognition of a particular link label at the front part of the address code and the stripping off of a front segment of the address code and so can easily be implemented in hardware. Recognizing that the recipients of a multicast packet very often need to respond to the source node, we designed the reverse path address code that allows an individual destination node to retrieve the reverse path address without searching the topology database and invoking any route computation program.>

Cable networks can offer a variety of video services such as video-on-demand, video conferencing, videotex, and real-time monitoring, besides broadcasting TV programs. These services can be extended when optical fibers, equipping tremendous bandwidth, are used to carry the traffic. Most of the newer cable systems are indeed using fibers as the distribution media. In the paper the authors propose a dynamic channel assignment strategy for an integrated-services cable system. The strategy allows the dynamic sharing of channels among the three types of video traffic, the real-time traffic, the broadcast traffic and the delayable traffic. Simulation results show that it can greatly increase the channel utilization without affecting service requirements.>

A modular architecture is proposed for distributing broadcast and switched video. The architecture consists of a set of concentration buses (or input buses), a TDM-based bus matrix and a set of distribution buses (or output buses). The transmission time in each output bus is divided into fixed size frames. Dedicated time slots in a frame are reserved for broadcast video. The remaining time slots are allocated to switched video on a first-come-first-served basis. Videos are switched via time slot assignments which determine the connections within the bus matrix. Two slot assignment algorithms are designed, one for point-to-point transmissions and the other for point-to-multipoint transmissions. The advantages of this architecture include: (1) accommodation of multirate video, (2) support of video broadcasting and multicasting, and (3) modular growth at distributed locations.>

ShuffleNet is one of the many architectures proposed for multihop lightwave networks. Its advantages include low mean-internodal distance and simple routing. Modular growth of ShuffleNets, however, is generally difficult and requires many hardware and software reconfigurations. The authors consider a multistar implementation of ShuffleNet and discuss how a (p,k) ShuffleNet can be expanded to a (p,k+1) ShuffleNet in modular phases, where each phase increases the number of nodes by only a small fraction and requires only minor hardware and software reconfigurations.>

By analyzing mathematical models, it is shown that combining channel borrowing with a coordinated sectoring or overlying scheme provides effective ways to handle hot-spots in the system. Blocking probabilities with these arrangements are derived, and the dynamic sharing with bias (DSB) rule is suggested for increasing the trunking efficiency. A simple handoff model is formulated and analyzed for comparing the probabilities of additional handoffs due to sectoring and overlaying of cells. With the nominal allocation of 60 channels per cell and a donor cell having a load of 30 Erlangs, numerical results show that at a blocking requirement of 1%, the traffic load in the hot-spot cell can be increased from 47 to 63 Erlangs with the use of the channel borrowing with the cell sectoring scheme: while with the use of the DSB rule, the load can be increased further to 71 Erlangs. A slightly higher load can be carried in the hot-spot cell with the use of cell overlaying arrangement.>

The tone sense multiaccess with partial collision detection (TSMA/PCD) protocol is particularly suitable for a packet satellite system serving an area with a dense population of earth stations. By incorporating a narrowband ground radio channel for broadcasting busy ones, the earth stations are able to avoid packet collisions by sensing for the absence of busy tones before transmitting packets. Partial collision detection capability can also be achieved. Single-tone TSMA/PCD gives 97% of the carrier-sense multiaccess with collision detection (CSMA/CD) throughput when N=10 tones are used, while for multitone and slot-by-slot announcement TSMA/PCD protocols only N=8 and N=2, respectively, are sufficient to drive the system to the CSMA/CD performance.>

A wavelength division multiaccess network with buffer sharing among stations is studied. All stations in the network are connected to a passive optical star coupler and each station has a different fixed wavelength laser for transmitting packets. Each station in the network reports its packet backlog to a scheduler which computes and then broadcasts a transmission schedule to all the stations through a control channel in each time slot. A transmission schedule includes two types of assignments: (1) to assign a maximum number of stations for conflict-free transmissions, and (2) to assign to relocation of packets from congested stations to uncongested relaying stations through idling transceivers for distributed buffer sharing. The major benefit is the reduction of packet loss due to buffer overflow. Results show that as much as 75% of the buffers can be saved with buffer sharing.>

A novel packet switch architecture using two sets of time division multiplexed (TDM) buses is proposed. The horizontal buses collect packets from the input ports while the vertical buses distribute the packets to the output ports. The two sets of buses are connected by a set of switching elements which coordinate the connections between the horizontal buses and the vertical buses so that each vertical bus is connected to only one horizontal bus at a time. The switch has the advantages of: (1) it adds input and output ports without increasing the bus and I/O adaptor speed; (2) it is internally unbuffered; (3) it has a very simple control circuit; and (4) it has 100% potential throughput under uniform traffic. A combined analytical-simulation method is used to obtain the packet delay and packet loss probability. Numerical results show that for satisfactory performance the buses need to run about 30% faster than the input line rate. With this speedup, even at a utilization factor of 0.9, the input queue can give a packet loss of 10/sup -6/ with only 31 buffers per input adaptor. The output queue behaves essentially as an M/D/1 queue.>

A protocol called the simple tone sense (STS) protocol is designed for multihop packet radio networks (PRNs) with multiple directional antennas stations. The protocol can minimize transmission interference by using a group of tones to identify the active neighbors. A variation of the STS protocol called the variable power tone sense (VPTS) protocol is also designed to further reduce interference. Algorithms for assigning tones and for determining the orientation and broadcasting angles of the directional antennas are designed. Design examples are given. Simulation result shows that the STS protocol gives better throughput-delay performance than the busy-tone multiple access protocol, especially when the traffic is heavy. The VPTS protocol gives still better throughput-delay performance than the STS protocol.>

An address coding mechanism is presented for multicast source routing packets in packet-switched networks. A simple algorithm for processing these address codes at intermediate output link adaptors is presented. It involves only the recognition of a particular link label at the front part of the address code and the stripping off of a front segment of the address code and so can easily be implemented in hardware. Recognizing that the recipients of a multicast packet very often need to respond to the source node, a reverse-path address code is designed that allows individual destination nodes to retrieve the reverse path address without searching the topology database and invoking any route computation program.>

This protocol is fully distributed and no onboard processing is required for the satellite. A control parameter f is used to adaptively control the packet transmission rate such that maximum system capacity can be attained and the average delay is always minimized for a given throughput. The controlled protocol is found to give a smaller average delay than slotted ALOHA even when the throughput is as low as 0.05. On the other hand, under heavy traffic conditions, it can provide a throughput close to unity and an average delay not much more than one round-trip propagation delay. The system performance is also robust, in the sense that a 15% error in throughput estimation results in no more than a 3% increase of the overall average packet delay.>

A two-level distribution network for broadcast and interactive video is studied as an example of the hierarchical distribution method. This two-level design has the following advantages: it facilitates switch growth and enhances switch reliability; it reduces the overall circuit mileage of the video distribution system; and video requests can be processed independently by local switches, rendering a large call processor at the central switch unnecessary. A traffic model for this network is formulated and the optimum capacities of the central and local switches are determined for a given blocking requirement. By adding a small crosspoint switch between the two levels, the output ports of the central switch can be dynamically allocated to the local switches. This sharing of output ports can significantly reduce the size of the central switch.>

An analysis is made of an alternate-path routing rule called maximum free circuit routing (MFCR). In the use of MFCR, a call is routed to the alternate path that has the maximum number of free circuits when the direct path is blocked. Analytical results show that in conjunction with trunk reservation, this routing rule can offer a stable throughput at high traffic conditions and can increase the call carrying capacity by about 20% (compared to direct path routing) under a blocking requirement of 10/sup -2/ on a fully connected symmetrical nonhierarchical network.>

A two-level distribution network for broadcast and interactive video is proposed. This two-level design replaces a large switch by a network of smaller switches, facilitating switch growth and enhancing switch reliability. The second-level switches (or the local switches) can be located at convenient places in their respective service districts, reducing the overall circuit mileage of the video distribution system. Video requests can be proposed independently by the local switches, rendering a large call processor at the central switch unnecessary. A traffic model for this network is formulated, and the optimum capacities of the central and local switches are determined for a given blocking requirement. Adding a small crosspoint switch between the two levels allows the output ports of the central switch to be dynamically allocated to the local switches. It is shown that this sharing of output ports can significantly reduce the size of the central switch.>

An improvement of the announced retransmission random access (ARRA) protocol for packet satellite communication, called the scheduled retransmission multiaccess protocol, is introduced. Besides avoiding collision between new and retransmitted packets, the improved protocol eliminates reservation conflicts between different slots. Explicit acknowledgement is used, so that traffic to other zones served by the same satellite can also be accommodated. Assuming that 3% of the channel capacity is used for retransmission reservation, fixed frame and dynamic-frame SRMAs achieve effective maximum throughputs of 0.65 and 0.89, respectively. Both protocols give average delays considerably lower than slotted ALOHA, even when the throughput is as low as 0.2.>

The contention-based lookahead reservation (CLAR) protocol can provide fast circuit-switching services that are particularly advantageous for networks supporting integrated services. The delay and throughput performance for message transmission are obtained, and they agree closely with that obtained by simulation. The delay performance of CLAR is similar to that of the M-CSMA protocol for an M-channel network, but only CLAR can give a stable maximum throughput of (M-1)/M independent of the cable length. Moreover, CLAR requires only two sets of transceivers, while M-CSMA requires M. The lookahead reservation technique can provide 9% throughput increase for fixed-size messages and 19% for geometrically distributed messages.>

Freedom from store-and-forward (S/F) deadlocks in a packet-switched network can be guaranteed with the use of deadlock avoidance protocols. However, these protocols put so many restrictions on the use of buffers that even under normal circumstances the buffer utilization is small. We propose instead a deadlock detection and resolution algorithm that is completely invisible under normal circumstances. As soon as certain channels in the network have trouble in accepting and transmitting packets due to the lack of buffers, the deadlock detection phase of the algorithm is invoked. When a deadlock is identified, the deadlock resolving phase of the algorithm is executed. Once the deadlock is resolved, the control is removed. The algorithm can be used in conjunction with either the complete partitioning or the sharing with maximum queue lengths output buffer allocation strategies. A proof on the correctness of the algorithm is given. Simulation results show that the network can maintain a relatively high throughput even when deadlocks are being detected and resolved. In addition, several properties of deadlocks are shown: i) deadlocks start to increase abruptly once the network operates beyond its capacity; and ii) under heavy load conditions, increasing the buffer pool size will not delay the occurrence of deadlocks.

In this paper we study a message resequencing problem in a store-and-forward computer network where messages may go out of order while traversing logical channels. The logical channels are assumed to consist of multiple physical links which may be of different capacities. A message is dispatched to the fastest available link. Resequencing methods suggested in the literature [3] (resequencing at the channel level and resequencing at the virtual circuit level) are investigated for this link selection rule. The analysis is done on a two-node network connected by multiple links. The source node together with the set of outgoing links are modeled as anM/M/mqueue with servers of different rates. The resequencing delay distribution and the average resequencing delay are derived. On multihop networks, the effect of message length, link numbers, link service rates, and the resequencing methods on resequeucing delay are investigated by simulation.

A new adaptive rule for balancing the load on many parallel queues is designed. The queueing system can accommodate different types of customers where each type is persistent in joining a particular set of queues. The rule makes use of a set of bias levels to compare the queue lengths and makes use of the majority-vote rule for propagating the routing decisions to the different types of customers. Delay and blocking probability comparisons between this rule and three other adaptive load balancing rules, the JSQ (join-the-shortest-queue) rule, the GBQ (generalized biased queue) rule, and the MRT (minimum response time) rule, show that it is always superior under widely different conditions on a three-parallel-queue system.