waashk/dblp huggingface dataset:
multicast and self-routing in atm radix trees and banyan networks. considers methods that perform all point-to-multipoint permutations in atm radix tree and banyan networks. the authors investigate the relationship between the structure of the routing tab and the ease of performing multicasting. they first consider a simple explicit addressing scheme that requires (n-1)(log/sub 2/n+1) routing bits. they then present an addressing filtering scheme that requires n routing bits. next they propose a new method, the vertex isolation addressing (via) scheme, which requires r(n-1)/(r-1) bits for radix-r tree networks. thus for binary trees the routing tab i 2(n-1) bits long and as r approaches n the routing tab approaches n bits. the authors demonstrate that the "excess" bits in the via routing tab provide certain error detection capabilities. encoding and decoding algorithms and hardware implementations for the via method are presented. modified via schemes are then investigated for large tree networks. finally the authors show that the via scheme and its modifications are applicable to banyan networks.
virtual path bandwidth allocation in multi-user networks. considers a multi-user network that is shared by noncooperative users. each user sets up virtual paths that optimize its own, selfish, performance measure. this measure accounts for both the guaranteed call level quality of service, as well as for the cost incurred for reserving the resource. the interaction between the user strategies is formalized as a game. the authors show that this game has a unique nash equilibrium, and that it possesses a certain fairness property. they investigate the dynamics of this game, and prove convergence to the nash equilibrium of both a gauss-seidel scheme and a jacobi scheme. they extend their study to various general network topologies.
bandwidth quantization in the broadband isdn. the authors indicate that the number of rates supportable in an asynchronous transfer mode (atm) broadband network has to be limited unless a network is acceptable without knowing its grade of service. the quantization of the channel bandwidth, given the traffic arrival rate as a function of requested bandwidth, is considered. capacity sharing models in atm networks are presented. the calculation procedure for blocking probability which will be affected by the quantization problem is described. a class of control methods that can render a product-form solution is introduced. the results indicate that there is little performance difference between a quantized channel and a continuous-rate channel as the level of quantization exceeds ten
a generalized non-preemptive priority queue. in this paper, we analyze a generalized non-preemptive queue with two priority classes. when the server serves the low priority queue, up to l customers are served before the server returns to the high priority queue. we study the embedded markov chain at departure epochs and obtain the transforms of the queue-length and sojourn-time distributions. from these transforms, it is easy to find the moments.
fault tolerance of banyan using multiple-pass. in order to utilize multiple-pass routing schemes, a faulty banyan network must possess the dynamic full access (dfa) property. the authors determine a necessary and sufficient condition for a banyan network to possess the dfa property and design a general testing procedure based on the condition. they also enumerate the probability that a banyan network loses the dfa property, given the number of faulty switch elements. it is found that, as long as faults do not occur in switch elements located in the first and last stages, this probability is very small even when there are quite a few faulty switch elements. therefore, multiple-pass routing schemes can be very useful if the switch elements in the first and last stages are well protected
a fair high-speed copy network for multicast packet switch. a fair high-speed copy network for multicast packet switching is described. the authors modify the architecture of the copy network proposed by t.t. lee (1988) to make it fair to all the inlets, and reduce the clock rate requirement of the switching fabric. fairness is achieved by adding a banyan network to perform cyclic shifts in front of the copy network. a pipelined architecture is proposed to avoid a huge internal speed-up. the clock rate requirement of the proposed copy network is evaluated and compared with that of the original design. it is found that the clock rate requirement can be reduced significantly if the number of inlets is larger than 64
optimization of a wdm optical packet switch with wavelength converters. this paper investigates a wavelength-division-multiplexed optical packet switch with wavelength converters which can shift optical packets to any wavelength of their destined outbound links. wavelength conversion can reduce packet dropping probability due to wavelength contentions. however, not all the packets need conversion, and hence conversion should be optimized to reduce the number of converters and improve the quality of signals by reducing unnecessary conversion. we derive the maximum number of conversions in a packet switch with l inbound/outbound links and w wavelengths per link and develop a switch control algorithm to minimize the number of wavelength conversions while maintaining the same minimum number of dropped packets. simulation results show that the packet dropping probability decreases significantly with wavelength conversion and that fewer converters than the maximum number of conversions are needed.
characterization of statistical multiplexing of heterogeneous atm sources. two asymptotic analyses of the queue length distribution at a statistical multiplexer supporting heterogeneous exponential on-off sources are considered. the first analysis is performed by approximating the cell generation rate as a multidimensional ornstein-uhlenbeck process and then applying the benes queueing formula. in the second analysis, we start with a system of linear equations derived from the exact expressions of the dominant eigenvalue of the matrix governing the queue length distribution. assuming that there are a large number of sources, we obtain asymptotic approximations to the dominant eigenvalue. based on the analyses, we define a traffic descriptor to include the mean and the variance of the cell generation rate and a burstiness measure. a simple expression for the quality of service (qos) in cell loss rate is derived in terms of the traffic descriptor parameters and the multiplexer parameters (output link capacity and buffer size). this result is then used to quantify the factors determining the required capacity of a call taking the statistical multiplexing gain into consideration.
performance and correctness of the atm abr rate control scheme. we study both the correctness and performance of the source/destination protocol of the available bit rate (abr) service in asynchronous transfer mode (atm) networks. although the basic source/destination protocol for congestion management is relatively simple, the protocol specification has to cope with several "real-world" cases such as failures and delayed/lost feedback which may introduce complexity. rigorous proofs of the correct functioning of the protocol based on a formal specification is necessary. we use a formal extended finite state machine (efsm) model to show that the abr source/destination protocol is free of live-locks, so that under all conditions both resource management (rm) and data cells will be transmitted. we also show that the network options of explicit forward congestion indication (efci) and explicit rate (er) interoperate correctly. we use the understanding of the informal english description of the source/destination behavior and of our efsm model to derive conditions that ensure that the source transmission rate is stable in the presence of delayed or lost feedback rm cells, especially under the operation of a source rule that requires the reduction of the source rate under these conditions. we arrive at bounds on the number of consecutive rm cell losses tolerated while the rate remains stable. we also provide a worst-case analysis of the delay in turning around rm cells at the destination station and the worst-case inter-departure time of forward rm cells from the source.
matching output queueing with a multiple input/output-queued switch. we have previously proposed an efficient switch architecture called multiple input/output-queued (mioq) switch and showed that the mioq switch can match the performance of an output-queued switch statistically. in this paper, we prove theoretically that the mioq switch can match the output queueing exactly, not statistically, with no speedup of any component. more specifically, we show that the mioq switch with two parallel switches (which we call a parallel mioq (pmioq) switch in this paper) can provide exact emulation of an output-queued switch with a broad class of service scheduling algorithms including fifo, weighted fair queueing (wfq) and strict priority queueing regardless of incoming traffic pattern and switch size.to do that, we first propose the stable strategic alliance (ssa) algorithm that can produce a stable many-to-many assignment, and prove its finite, stable and deterministic properties. next, we apply the ssa algorithm to the scheduling of a pmioq switch with two parallel switches, and show that the stability condition of the ssa algorithm guarantees for the pmioq switch to emulate an output-queued switch exactly. to avoid possible conflicts in a parallel switch, each input-output pair matched by the ssa algorithm must be mapped to one of two crossbar switches. for this mapping, we also propose a simple algorithm that requires at most 2n steps for all matched input-output pairs. in addition, to relieve the implementation burden of n input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of n physically-separate memories. in conclusion, we demonstrate that the mioq switch requires two crossbar switches in parallel and two physical memories at each input and output to emulate an output-queued switch with no speedup of any component.
an asymptotic analysis of a threshold load balancing policy. this paper describes and analyzes a specific threshold load balancing policy in a distributed computer system that executes a priority scheduling on jobs according to the location of job origination. an approximate analysis is carried out to obtain the response time performance of the system under the load balancing policy. in the analysis we assume that the arrival of jobs at a node transferred from other nodes are governed by a p0isson process. this allows us to decompose the behavior of the system into separate models of each of the nodes. we then map the behavior of each node into the framework of queueing systems subject to breakdown to obtain a closed-form expression for the mean response time of a job. we prove that the poisson assumption on the job transfers is asymptotically exact and hence the performance predictions of the model is asymptotically exact as the number of nodes in the system increases. simulation studies reveal that the poisson job transfer assumption is good even for small systems when we are interested in obtaining the response time performance of the system.
bandwidth allocation policies for unicast and multicast flows. using multicast delivery to multiple receivers reduces the aggregate bandwidth required from the network compared to using unicast delivery to each receiver. however, multicast is not yet widely deployed in the internet. one reason is the lack of incentive to use multicast delivery. to encourage the use of multicast delivery, we define a new bandwidth-allocation policy, called logrd, taking into account the number of downstream receivers. this policy gives more bandwidth to a multicast flow as compared to a unicast flow that shares the same bottleneck, without starving the unicast flows, however. the logrd policy also provides an answer to the question on how to treat a multicast flow compared to a unicast flow sharing the same bottleneck. we investigate three bandwidth-allocation policies for multicast flows and evaluate their impact on both receiver satisfaction and fairness using a simple analytical study and a comprehensive set of simulations. the policy that allocates the available bandwidth as a logarithmic function of the number of receivers downstream of the bottleneck achieves the best tradeoff between receiver satisfaction and fairness.
an on-demand qos routing protocol for mobile ad hoc networks. we propose an on-demand bandwidth routing protocol for qos (quality of service) support in mobile ad hoc networks. the qos routing feature is important for a mobile network to interconnect wired networks with qos support (e.g., atm, internet, etc.). the qos routing protocol can also work in a stand-alone mobile ad hoc network for real-time applications. under such a routing protocol, the source (or the atm gateway) is informed of the bandwidth and qos available to any destination in the mobile network. this knowledge enables the establishment of qos connections within the mobile network and the efficient support of real time applications. in addition, it enables more efficient call admission control. in case of atm interconnection, the bandwidth information can be used to carry out intelligent handoff between atm gateways and/or to extend the atm virtual circuit service to the mobile network with possible renegotiation of qos parameters at the gateway. simulation results suggest distinct performance advantages of our protocol calculating the bandwidth information. it is particularly useful in call admission control. furthermore, ''on-demand'' routing enhances the performance in the mobile environment because the source can keep more connectivity to a receiver in the path-finding duration. simulation experiments show this improvement.
queue response to input correlation functions: discrete spectral analysis. a new concept of spectral characterization of the wideband input process in high-speed networks is examined. the eigenstructure technique, through the modeling of input markov chains, helps localize wideband sources in a subspace, especially in a low frequency band. simple periodic chains are used for the construction of the input rate process. the input power spectral distribution is defined in a discrete frequency domain. each input traffic stream is characterized by an independent markov modulated poisson process (mmpp). the underlying markov chain is used to reflect the time autocorrelation properties of the input process at a macro level. expressions are derived for correlation and power spectral functions of the mmpp input. a queuing analysis with multiple periodic input functions is described. the queue response to input correlation functions is examined. the advantages of using the spectral domain to analyze and design network control and resource management are discussed
constant-time dynamic atm bandwidth scheduling for guaranteed and best effort services with overbooking. in this paper, we present an analysis of an existing rate-based abr scheduling algorithm described in [1], and propose an enhanced rate-based round robin (rbr) scheduling algorithm for atm switches and end systems. one of the novel aspects of rbr is that the scheduler supports available bit rate (abr) traffic as well as guaranteed bandwidth reservations. in addition, bandwidth overbooking is allowed by the scheduler for abr services to improve link efficiency as recommended by most flow control schemes. under competition, the scheduler distributes the bandwidth in a max-min fair way. any unused reservations for guaranteed services are reallocated to abr services. finally, the operations performed during each scheduling cycle are constant, independent of the number of connections. simulation results are also presented and analyzed.
effects of erlang call holding times on pcs call completion. previous performance studies of pcs channel allocation assumed that call holding times have an exponential distribution. the exponential call holding time assumption is justified for existing cellular systems, where wireless calls are charged based on the length of the call holding time. future pcs systems may exercise flat rate billing, and consequently a more general distribution is desirable to model the call holding times. this paper models the call holding times by the erlang distribution (a generalization of the exponential distribution) to investigate the effect of the variance of the call holding times on the call completion probability. our analysis indicates that the call completion probability decreases as the variance of the call holding times decreases. this effect becomes more pronounced as the variance of the cell residence times decreases.
the split and merge (sam) protocol for interactive video-on-demand systems. a true video-on-demand (vod) system provides the ultimate flexibility in video services by allowing users to select any video programs, at any time, and to perform any vcr-like user interactions. to allow true vod, one approach is to have a dedicated video stream for each customer. this is expensive, especially when multiple identical video streams are sent to multiple customers accessing the same video. to be commercially viable, vod service must be priced competitively with existing video rental services. batching may be used to reduce this cost. it allows multiple users accessing the same video to share the same video stream. the batching approach, however, complicates the provision of user interactions. existing batching schemes only allow near vod services. this paper describes a new protocol, called split and merge (sam), which offers true vod services while allowing multiple users to share the same video stream. this sharing is transparent to the users and it appears as if each has a dedicated video stream. our approach is to split an interactive user from the batch and to serve him with a dedicated video stream. we develop an innovative way to merge these individuals back to the batching streams when they resume normal play mode. the sam protocol therefore significantly improves the system resource utilization and the number of simultaneous users, and more importantly, allows true vod services.
multiple priority csma-type mulitchannel local area network. in this paper, we will introduce a new network access protocol for csma-type multichannel local area network (mlan). this new protocol has the capability of providing different network access priority among the various applications. from the earlier research, it has been shown that the csma-type mlan is superior to a single channel on the equal network bandwidth. on the basis of the developed mlan architecture, we construct a new network access protocol to provide multiple transmission priorities for various applications, e.q., text, voice, video, image, etc. this protocol is called multiple-priority multichannel local area network (mp-mlan). the data transmission of mp-mlan is collision-free, and we can find the throughput characteristics of mp-mlan are higher and more stable than the conventional csma/cd or multichannel csma/cd network from the analysis results. a queueing analysis model for representing the mp-mlan protocol is established, and simulation results are also provided to evaluate the performance of this network.
optimal sliding-window strategies in networks with long round-trip delays. a method commonly used for packet flow control over connections with long round-trip delays is "sliding windows". in general, for a given loss rate, a larger window size achieves a higher average throughput, but also a higher rate of spurious packet transmissions, rejected by the receiver merely for arriving out-of-order. this paper analyzes the problem of optimal flow control quantitatively, for a connection that has a cost per unit time and a cost for every transmitted packet. the optimal strategy is defined as one that minimizes the expected cost/throughput ratio, and is allowed to transmit several copies of a packet within a window. we present an algorithm for computing the optimal strategy and study its properties; in particular, we derive bounds on the optimal strategy cost/throughput performance, and show that it increases merely logarithmically with the time price, whereas the cost/throughput of the 'traditional' classic window scheme is linear in the time price.
maximizing throughput for optical burst switching networks. in optical burst switching (obs) networks, a key problem is to schedule as many bursts as possible on wavelength channels so that the throughput is maximized and the burst loss is minimized. most of the current research on obs has been concentrated on reducing burst loss in an "average-case" sense, and little effort has been devoted to understanding the worst case performance. since obs itself is an open-loop control system, it may exhibit a worst case behavior when adversely synchronized. on the other hand, most commercial systems require an acceptable worst case performance. in this paper, we use competitive analysis to analyze the worst case performance of a large set of scheduling algorithms, called best-effort online scheduling algorithms, for obs networks and establish a number of interesting upper and lower bounds on the performance of such algorithms. our analysis shows that the performance of any best-effort online algorithm is closely related to a few factors, such as the range of offset time, maximum-to-minimum burst-length ratio, and the number of data channels. a surprising discovery is that the worst case performance of any best-effort online scheduling algorithm is primarily determined by the maximum-to-minimum burst-length ratio, followed by the range of offset time. furthermore, if all bursts have the same burst length and offset time, all best-effort online scheduling algorithms generate the same optimal solution, regardless of how different they may look. our analysis can also be extended to some non-best-effort online scheduling algorithms, such as the well-known horizon algorithm, and establish similar bounds. based on the analytic results, we give guidelines for several widely discussed obs problems, including burst assembly, offset time setting, and scheduling algorithm design, and propose a new channel reservation protocol called virtual fixed offset-time (vfo) to improve the worst case performance. our simulation shows that vfo can also reduce the average burst loss rate.
global clock synchronization in sensor networks. global synchronization is important for many sensor network applications that require precise mapping of collected sensor data with the time of the events, for example, in tracking and surveillance. it also plays an important role in energy conservation in mac layer protocols. this paper describes four methods to achieve global synchronization in a sensor network: a node-based approach, a hierarchical cluster-based method, a diffusion-based method, and a fault-tolerant diffusion-based method. the diffusion-based protocol is fully localized. we present two implementations of the diffusion-based protocol for synchronous and asynchronous systems and prove its convergence. finally, we show that, by imposing some constraints on the sensor network, global clock synchronization can be achieved in the presence of malicious nodes that exhibit byzantine failures.