waashk/dblp huggingface dataset:
on the computational complexity and effectiveness of n-hub shortest-path routing. in this paper, we study the computational complexity and effectiveness of a concept we term "n-hub shortest-path routing" in ip networks. n-hub shortest-path routing allows the ingress node of a routing domain to determine up to n intermediate nodes ("hubs") through which a packet will pass before reaching its final destination. this facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. although this concept has been proposed in the past, this paper is the first to investigate it in depth. we apply n-hub shortest-path routing to the problem of minimizing the maximum load in the network. we show that the resulting routing problem is np-complete and hard to approximate. however, we propose efficient algorithms for solving it both in the online and the offline contexts. our results show that n-hub shortest-path routing can increase network utilization significantly even for n = 1. hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the internet.
slot allocation strategies for tdma protocols in multihop packet radio networks. the authors derive an upper bound of the minimum time division multiple access (tdma) frame length of any collision-free node assignment protocol in a packet radio network in which a node has multiple reception capacity. they also derive the optimum tdma frame length for any fully connected network with large reception capacity. when the total number of nodes in the network is unknown, a heuristics to generate a tdma protocol with frame length within some upper bound is presented for any network with large reception capacity
ip addressing and routing in a local wireless network. ip is the basic protocol in the internet. the authors explore a variety of possibilities to adapt the wireless environment to that of ip. they describe the requirements and show how these can be accommodated by using the existing ip. at the heart of the problem is the lack of a capability in the current ip routing services to track topological changes. several alternatives are described, each making use of a different combination of the addressing and routing features offered by ip. the alternatives are compared. the tradeoffs among these alternatives are explored
handover in a micro-cell packet switched mobile network. this paper proposes a distributed handover protocol for a micro-cell packet switched mobile network. in such a network, users move from one cell to another very often, and each change of location may result in misrouted and lost packets. the purpose of the new protocol is to minimize these consequences of location changes: as long as a mobile moves from one cell to another but stays in the same region, the protocol avoids loss of packets and preserves order of transmission. thus it increases the performance of the transport layer protocol by minimizing the need to retransmit packets.
an inversion algorithm for loss networks with state-dependent rates. we extend our recently developed algorithm for computing (exact) steady-state blocking probabilities for each class in product-form loss networks to cover general state-dependent arrival and service rates. this generalization allows us to consider, for the first time, a wide variety of buffered and unbuffered resource-sharing models with non-poisson traffic as may arise with overflows in the context of alternative routing. as before, we consider non-complete-sharing policies involving upper-limit and guaranteed-minimum bounds for the different classes, but here we consider both bounds simultaneously. major features of the algorithm are: dimension reduction by conditional decomposition based on special structure, an effective scaling algorithm to control errors in the inversion, the efficient treatments of multiple classes with identical parameters and the truncation of large sums.
performance of multistage atm switch architectures under nonuniform bursty traffic. a technique for the efficient analysis of multistage atm switch architectures is presented. it is flexible in that it permits arbitrary switching element sizes, a full range of hardware speedup and backpressure between stages. the arriving traffic is assumed to be bursty and the authors do not assume homogeneity of all traffic sources. the flow of cells through the network is approximated as a fluid process, yielding computational complexity that depends only on the representation of the arrival and departure processes of a queue, independent of the number of buffers. simulation results verify the accuracy of this approach. finally, the analysis is used to examine the effect of nonhomogeneous traffic, as well as to present a comparison of the various modes of operation and implementation parameters of the multistage switch, providing insights on design trade-offs.
a decomposition method for the exact analysis of circuit-switched networks. a general-purpose decomposition method is formulated for the exact analysis of blocking probabilities in multirate circuit-switched networks. the procedure is based on a decomposition and aggregation technique that exploits the sparsity that can be found in the routing matrix of a network. use is also made of a recursive algorithm developed by the authors (see ann. oper. res. vol.35, no.1-4, p.31-41, 1992). no special assumptions are made with regard to the structure of the network. by reducing the analysis to that of a set of interrelated subsystems and a reduced system, the overall dimensionality of the problem is diminished, and the computational costs are reduced significantly. this enables the efficient exact analysis of larger network models. an example is provided to illustrate the computational savings that can be realized
optimal cost/performance design of atm switches. the authors propose a methodology for performing an evaluation and optimization of the cost of an asynchronous transfer mode (atm) switching architecture under performance constraints given in terms of virtual connection blocking probability. an analysis of blocking networks is developed and combined with known results concerning nonblocking networks that provide a theoretical model which relates traffic characteristics, network topology, and blocking probability in a multirate/multiservice broadband environment. an analysis of the characteristics determining the cost of a generic atm switch implementation follows. the model is oriented to optimize both the topological parameters and the speed advantage, with respect to the main cost factors of vlsi-based switching networks
what's new: finding significant differences in network data streams. monitoring and analyzing network traffic usage patterns is vital for managing ip networks. an important problem is to provide network managers with information about changes in traffic, informing them about "what's new." specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. we introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational.we present novel algorithms for finding the most significant deltoids in high-speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. in experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. this is the first work to provide solutions capable of working over the data with one pass, at network traffic speeds.
a reservation-based multicast (rbm) routing protocol for mobile networks: overview of initial route construction. we propose a combined multicast routing and resource reservation protocol, termed reservation-based multicast (rbm), that performs routing in a fashion similar to protocol independent multicast (pim), but which is intended for mobile operation and routes hierarchically-encoded data streams based on user-specified fidelity requirements, real-time delivery thresholds and prevailing network bandwidth constraints. the protocol retains the fully distributed operation, scalability and receiver-initiated orientation of pim; but, unlike pim, the protocol is tightly coupled to an underlying, distributed, unicast routing protocol thereby facilitating operation in a dynamic topology. this paper focuses on the initial route construction phase, assumed to occur during a static "snapshot" of the dynamic topology, and therefore outlines an approach to reservation-based multicast routing for fixed networks as well, e.g. the internet.
modeling superposition of on-off correlated traffic sources in multimedia applications. in this paper a multimedia source is modeled as an arrival process defined as the superposition of heterogeneous correlated arrival processes, each of which models one monomedia source. to this purpose each monomedia source is modeled as an on-off process where the transition rates are functions of the states of the other monomedia sources. auto- and cross-correlation functions are derived for each monomedia source. the analytical model is used to develop results for single media performance in a multimedia multiplexer structure.
the network effects of prefetching. abstract prefetching has been shown to be an effective technique for reducing user perceived latency in distributed systems. in this paper we show that even when prefetching adds no extra traffic to the network, it can have serious negative performance effects. straightforward approaches to prefetching increase the burstiness of individual sources, leading to increased average queue sizes in network switches. however, we also show that applications can avoid the undesirable queueing effects of prefetching. in fact, we show that applications employing prefetching can significantly improve network performance, to a level much better than that obtained without any prefetching at all. this is because prefetching offers increased opportunities for traffic shaping that are not available in the absence of prefetching. using a simple transport rate control mechanism, a prefetching application can modify its behavior from a distinctly on/off entity to one whose data transfer rate changes less abruptly, while still delivering all data in advance of the user''s actual requests.
a queueing system with two arrival streams and reserved servers with application to cellular telephone. the authors consider a service system in which n servers render service to two classes of prioritized traffic, which arrive to the system according to independent poisson processes. newly arriving call requests are granted server access on a first-come-first-served (fcfs) basis as long as there are fewer than g servers occupied. if fewer than g servers are free at the arrival time of a lower priority customer, the higher priority call requests are granted immediate service unless all servers are busy, in which case the call is dropped. this model has been used to study the handoff problem in a cellular telephone system, but the analytic approach taken was very complicated. the authors present a simple, novel, alternative approach to solving for the equilibrium probabilities for the number of lower priority calls in the queue and other quantities of interest. they describe two additional alternative approaches based on neuts' matrix analytic approach for checking results, and point out that while the results of all these approaches agree with each other, they differ from previously published results. because these three approaches are essentially independent, it is conjectured that there are problems with the earlier numerical results. further work has revealed that this is the case
design of real-time admission control algorithms with priority support. a multimedia atm network is shared by media channels with different performance requirements and traffic characteristics. to make efficient use of network resources, the quality of service provided to the users should be as close as possible to their requirements. a scheme with two levels of cell loss priority within each channel is proposed. priorities are assigned and enforced by the network locally at each switch along the path of a connection. the assignment, which can be different for the same connection at two different switches, is also dynamic; it is updated every time a connection is set up or one is terminated. algorithms used by the network to decide the fraction of cells of each stream assigned to each cell loss priority level, along with a simple mechanism to enforce the desired priority assignment and a real-time admission control algorithm, with decision time of very few milliseconds even for thousands of heterogeneous sources are presented.
multicast feedback suppression using representatives. for a reliable, feedback dependent multicast transport protocol to scale, it must avoid the feedback implosion problem, particularly if the protocol targets arbitrarily large multicast groups communicating over lossy networks. most existing suppression based feedback control mechanisms address the implosion problem using timers based on round-trip time (rtt) estimates between each receiver and the source. the algorithm presented has three major benefits: it does not need to compute the rtt from all receivers to the source, does not require knowledge of group membership, and provides prompt feedback. a small set of representative receivers and probabilistic suppression are used to limit feedback. we believe that this approach will perform well in real networks. simulations show that for various multicast group sizes, a few representatives can keep the amount of feedback low while not degrading feedback timeliness.
performance analysis of deflection routing multichannel-metropolitan area networks. the authors evaluate the performance of two different network architectures, implementing multichannel metropolitan area networks (m-mans). deflection routing, no internal storage, and a high connectivity degree are the main characteristics of regular networks built by interconnecting small-size multichannel nodes. analytical models have been developed for network architectures with a connectivity degree equal to four: the bidirectional manhattan street network (bmsn) and the shuffle net (sn). the authors evaluate the performance under uniform traffic distribution and also under the realistic assumption that the user's attachments to network nodes are equipped with input and output buffers. the performances under investigation are throughput, average delay, and packet loss. the availability of an analytical model makes it possible to investigate the performance of networks with a large number of nodes. the strong and weak points of the two m-man architectures are pointed out in the discussion of the results
design of the apic: a high performance atm host-network interface chip. we present the design of a high performance atm host-network interface for multimedia workstations and servers. at washington university, as part of an arpa-sponsored gigabit local atm testbed, we are building a prototype of this interface that can support a sustained aggregate bidirectional data rate of 2.4 gbps. the centerpiece of our interface design is a custom chip called the apic (atm port interconnect controller). multiple such chips can be interconnected to yield a desk-area network (dan) which would serve as a high speed i/o interconnect for the host computer. this paper details the internal design of the apic chip, and outlines some of its key features. noteworthy among these are: connection caching, transmit pacing, cell batching, remote control, and support for aal-0, aal-5, multipoint, and loopback connections. we have chosen to defer to a later paper the details pertaining to several other features which provide support for zero-copy, improved interrupt handling, direct control of the chip from user-space, and efficient buffering and demultiplexing.
the apic approach to high performance network interface design: protected dma and other techniques. we are building a high performance 1.2 gb/s atm network interface chip called the apic (atm port interconnect controller). in addition to borrowing useful ideas from a number of research and commercial prototypes, the apic design embraces several innovative features, and integrates all of these pieces into a coherent whole. some of the novel ideas incorporated in the apic design include: protected dma and protected i/o, which allow applications to queue data for transmission or reception directly from user-space, effectively bypassing the kernel. this argues for moving the entire protocol stack including the interface device driver into user-space, thereby yielding better latency and throughput performance than kernel-resident implementations. pool dma when used with packet splitting, is a technique that can be used to build true zero-copy kernel-resident protocol stack implementations, using a page-remapping technique. finally, orchestrated interrupts and interrupt demultiplexing are mechanisms used to reduce the frequency of interrupts issued by the apic. although many of these ideas have been developed in the context of an atm network interface, we believe they are also applicable in other contexts. in particular, protected dma and i/o are promising techniques for improving the performance of several different types of i/o devices.
on multicast trees: structure and size estimation. this work presents a thorough investigation of the structure of multicast trees cut from the internet and power-law topologies. based on both generated topologies and real internet data, we characterize the structure of such trees and show that they obey the rank-degree power law; that most high degree tree nodes are concentrated in a low diameter neighborhood; and that the sub-tree size also obeys a power law.our most surprising empirical finding suggests that there is a linear ratio between the number of high degree network nodes, namely nodes whose tree degree is higher than some constant, and the number of leaf nodes in the multicast tree (clients). we also derive this ratio analytically. based on this finding, we develop the fast algorithm, that estimates the number of clients, and show that it converges faster than one round trip delay from the root to a randomly selected client.
modified tree structure for location management in mobile environments. suggests a new data structure for location management in mobile networks. the data structure is based on the tree location database structure. the authors suggest replacing the root and some of the higher levels of the tree with another structure that balances the average load of search requests. for this modification they use a set-ary butterfly network, which is a generalization of the well-known k-ary butterfly. they also suggest modifying the lowest level of the tree in order to reflect neighboring geographical regions more accurately and to support simple location data management. the modification of the lowest level also supports simple handoffs. the update of the proposed location database ensures correct location data following any number of transient faults that corrupt the location database information and thus is self-stabilizing.
an efficient priority-based dynamic channel allocation strategy for mobile cellular networks. priority-based dynamic carrier allocation strategies can be classified into three categories: static-priority, dynamic-priority, and hybrid-priority strategies. strategies based on static priorities do not consider the local carrier reuse conditions, while dynamic-priority strategies do take these conditions into consideration. intuitively, one would expect dynamic-priority strategies to perform better than static- and hybrid-priority strategies, but in the literature it is the other way around --- existing dynamic-priority strategies are outperformed by some static- and hybrid-priority strategies.in this paper, we propose a dynamic-priority strategy that significantly improves over all existing strategies. under various traffic conditions, our simulation results indicated that the proposed strategy could reduce call blocking/failure rate by a margin ranging from 15% to 95%.
multiobjective flow control in telecommunication networks. pareto optimality is studied in the context of multiclass telecommunications networks with constraints on the maximum allowable user delays. the performance objective of each individual class is the maximization of throughput under a delay constraint. users share the network on a processor sharing basis. the multiobjective problem that arises is solved via a transformation that leads to a multicriterion linear program. the solution method is outlined by a thorough study of a simple example. pareto optimal solutions are compared on the basis of fairness given to different configurations and traffic characteristics
impact of interferences on connectivity in ad hoc networks. we study the impact of interferences on the connectivity of large-scale ad hoc networks, using percolation theory. we assume that a bi-directional connection can be set up between two nodes if the signal to noise ratio at the receiver is larger than some threshold. the noise is the sum of the contribution of interferences from all other nodes, weighted by a coefficient γ and of a background noise.we find that there is a critical value of γ above which the network is made of disconnected clusters of nodes. we also prove that if γ is nonzero but small enough, there exist node spatial densities for which the network contains a large (theoretically infinite) cluster of nodes, enabling distant nodes to communicate in multiple hops. since small values of γ cannot be achieved without efficient cdma codes, we investigate the use of a very simple tdma scheme, where nodes can emit only every nth time slot. we show that it achieves connectivity similar to the previous system with a parameter γ/n.
error control aspects of high speed networks. error control problems arising in the broadband isdn environment are analyzed. the first problem relates to end-to-end integrity. the second problem is related to synchronization. the third problem is the performance of the cell-based cyclic redundancy check (crc) in the presence of a self-synchronous scrambler to avoid attacks by malicious users. however, the scrambler creates error multiplication whereby a single error on the physical link is translated into two errors in the cell exactly 43 bits apart. in this context, it is proved that the cell-based crc is capable of correcting correlated double errors produced by the self-asynchronous scrambler. the last problem studied is parallel implementation of crc coders and decoders
trajectory sampling with unreliable reporting. we define and evaluate methods to perform robust network monitoring using trajectory sampling in the presence of report loss. the first challenge is to reconstruct an unambiguous set of packet trajectories from the reports on sampled packets received at a collector. in this paper we extend the reporting paradigm of trajectory sampling to enable the elimination of ambiguous groups of reports, but without introducing bias into any characterization of traffic based on the surviving reports. even after the elimination, a proportion of trajectories are incomplete due to report loss. a second challenge is to adapt measurement based applications (including network engineering, path tracing, and passive performance measurement) to incomplete trajectories. to achieve this, we propose a method to join multiple incomplete trajectories for inference, and analyze its performance. we also show how applications can distinguish between packet and report loss at the statistical level.