waashk/dblp huggingface dataset:
analysis of integrated services tdm with correlated traffic. the problem of multiplexing time-critical (tc) and time-non-critical (tnc) packetized information in an integrated services digital network (isdn) is considered. an appropriate time division multiplexing (tdm) scheme is adopted to accommodate the strict delay requirements for the tc traffic. the resulting system is different from those previously considered in at least two aspects. first, the tnc traffic is assumed to exhibit correlation between consecutive slots. second, the tc traffic is not necessarily accommodated in a contiguous subframe, but it may be spread over the whole frame according to any pattern. the nongated service policy is adopted for the service of the tnc traffic, unlike most of the past work. a very flexible approach is developed for the exact analysis of the proposed tdm scheme. numerical results are derived for the case of tc traffic generated by voice sources
new call block versus handoff blocking in cellular networks. in cellular networks, blocking occurs when a base station has no free channel to allocate to a mobile user. one distinguishes between two kinds of blocking, the first is called new call blocking and refers to blocking of new calls, the second is called handoff blocking and refers to blocking of ongoing calls due to the mobility of the users. in this paper, we first provide explicit analytic expressions for the two kinds of blocking probabilities in two asymptotic regimes, i.e., for very slow mobile users and for very fast mobile users, and show the fundamental differences between these blocking probabilities. next, an approximation is introduced in order to capture the system behavior for moderate mobility. the approximation is based on the idea of isolating a set of cells and having a simplifying assumption regarding the handoff traffic into this set of cells, while keeping the exact behavior of the traffic between cells in the set. it is shown that a group of 3 cells is enough to capture the difference between the blocking probabilities of handoff call attempts and new call attempts.
multiservice call blocking approximations for virtual path based atm networks with cbr and vbr traffic. the exact calculation of call blocking probabilities for multiservice atm networks with alternate or adaptive routing for virtual channels (vc) is hardly possible. therefore the paper presents and investigates the equivalent single path model as an approximation to omit the vc routing algorithm in the calculation. the model can be applied to atm networks with several direct virtual path connections between each node pair. further different methods to calculate the multiservice call blocking probabilities are reviewed and compared. a new approximate method is presented for networks, where the trunk reservation fairness mechanism is applied. this method is accurate, fast and may also be used for noninteger capacities and bandwidth requirements, which is important for statistical multiplexing of variable bitrate traffic.
hardware based error and flow control in the axon gigabit host-network interface. the primary goal of the axon architecture is to support a high-performance data path delivering high network bandwidth directly to applications. the axon network interface is described from the perspective of its simulation, and in particular and implementation of error and flow control in hardware. background is provided on the simulation package that has been used to explore these mechanisms, and a brief overview is given of the axon architecture is implemented by the simulator. the error control mechanism, the hardware design, and the functional and performance simulation results are outlined. the rate control scheme is described, along with its implementation and simulation
providing bandwidth guarantees in an input-buffered crossbar switch. introduces and analyzes a method for providing bandwidth reservations in an input-buffered non-blocking crossbar switch. the scheme, which the authors call weighted probabilistic iterative matching (wpim), is an improvement over probabilistic iterative matching and allows flexible allocation of bandwidth among the switch inputs sharing a common output link in a simple manner. weighted probabilistic iterative matching allocates the output bandwidth among the inputs based on reservations made during the connection setup phase, and can guarantee that traffic from each input receives its promised share of the bandwidth of the output link. in addition, the algorithm provides isolation between two flows arriving on distinct input links and directed at a common output link; misbehaving flows at one of the inputs do not affect the bandwidth guarantees or delays of traffic from other inputs. results from simulations show that the scheme is able to maintain probabilistic bandwidth and delay guarantees in the presence of misbehaving traffic. the authors also derive an analytical upper bound for the average delay under the scheme and validate it by simulation.
latency-rate servers: a general model for analysis of traffic scheduling algorithms. in this paper, we develop a general model, called latency-rate servers ($\cal lr$-servers), for the analysis of traffic scheduling algorithms in broadband packet networks. the behavior of an $\cal lr$ scheduler is determined by two parameters --- the latency and the allocated rate. we show that several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of $\cal lr$-servers. we derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of ${\cal lr}$-servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a leaky bucket. thus, the theory of $\cal lr$-servers enables computation of tight upper-bounds on end-to-end delay and buffer requirements in a network of servers in which the servers on a path may not all use the same scheduling algorithm. we also define a self-contained approach to evaluate the fairness of $\cal lr$-servers and use it to compare the fairness of many well-known scheduling algorithms.
a performance model for wavelength conversion with non-poisson traffic. this paper makes the first known attempt to study wavelength-routing networks and the effects of wavelength conversion under dynamic non-poisson traffic. an approximation that characterizes any non-poisson traffic by its first two moments is utilized. the arrival occupancy distribution of busy wavelengths for this approximate process is derived and is used to analyze the effects of wavelength conversion. the model predicts that traffic peakedness plays an important role in determining the blocking performance, and also that wavelength conversion gain is insensitive to traffic peakedness over a large range.
buffer sizing at a host in an atm network. the authors develop a queuing model of a buffer that collects cells for reassembly into packets for a protocol layer above the asynchronous transfer mode (atm) layer. whenever the buffer fills with all packets incomplete, a packet must be sacrificed to make room for others. the queuing model estimates the equilibrium fraction of packets sacrificed. applications to sizing the buffer for a prescribed loss probability are given
characterizing the internet hierarchy from multiple vantage points. the delivery of ip traffic through the internet depends on the complex interactions between thousands of autonomous systems (ases) that exchange routing information using the border gateway protocol (bgp). this paper investigates the topological structure of the internet in terms of customer-provider and peer-peer relationships between ases, as manifested in bgp routing policies. we describe a technique for inferring as relationships by exploiting partial views of the as graph available from different vantage points. next we apply the technique to a collection of ten bgp routing tables to infer the relationships between neighboring ases. based on these results, we analyze the hierarchical structure of the internet and propose a five-level classification of ases. our analysis differs from previous characterization studies by focusing on the commercial relationships between ases rather than simply the connectivity between the nodes.
a lower bound for multicast key distribution. with the rapidly growing importance of multicast in the internet, several schemes for scalable key distribution have been proposed. these schemes require the broadcast of @q(logn) encrypted messages to update the group key when the nth user joins or leaves the group. in this paper, we establish a matching lower bound (independently, and concurrently, richard yang and simon lam discovered a similar bound with slightly different properties and proofs. an earlier version of our paper appeared in infocom 2001 while their result appears in [r. yang, s. lam, a secure group key management communication lower bound, technical report tr-00-24, department of computer sciences, ut austin, july 2000, revised september 2000].), thus showing that @q(logn) encrypted messages are necessary for a general class of key distribution schemes and under different assumptions on user capabilities. while key distribution schemes can exercise some tradeoff between the costs of adding or deleting a user, our main result shows that for any scheme there is a sequence of 2n insertion and deletions whose total cost is @w(nlogn). thus, any key distribution scheme has a worst-case cost of @w(logn) either for adding or for deleting a user.
algebra and algorithms for qos path computation and hop-by-hop routing in the internet. prompted by the advent of quality-of-service routing in the internet, we investigate the properties that path weight functions must have so that hop-by-hop routing is possible and optimal paths can be computed with a generalized dijkstra's algorithm. for this purpose, we define an algebra of weights which contains a binary operation, for the composition of link weights into path weights, and an order relation. isotonicity is the key property of the algebra. it states that the order relation between the weights of any two paths is preserved if both of them are either prefixed or appended by a common, third, path.we show that isotonicity is both necessary and sufficient for a generalized dijkstra's algorithm to yield optimal paths. likewise, isotonicity is also both necessary and sufficient for hop-by-hop routing. however, without strict isotonicity, hop-by-hop routing based on optimal paths may produce routing loops. they are prevented if every node computes what we call lexicographic-optimal paths. these paths can be computed with an enhanced dijkstra's algorithm that has the same complexity as the standard one. our findings are extended to multipath routing as well.as special cases of the general approach, we conclude that shortest-widest paths can neither be computed with a generalized dijkstra's algorithm nor can packets be routed hop-by-hop over those paths. in addition, loop-free hop-by-hop routing over widest and widest-shortest paths requires each node to compute lexicographic-optimal paths, in general.
gateway based approach for conducting multiparty multimedia sessions over heterogeneous signaling domains. emerging networking technologies are being introduced with their own management protocols for routing, resource reservation and signaling. this diversity restricts the interoperability among qos-aware multimedia applications written for different networks. we present an approach for managing multiparty, multimedia sessions in a heterogeneous internetwork spanning multiple signaling domains. participants utilize the native signaling on their respective domains and interact with participants on other domains through signaling gateways that bridge the domains and provide translation of signaling procedures and qos semantics. data streams are transmitted using a hierarchical representation, which allows participants to independently adjust the reception quality of each stream according to their resources and interests. we present a particular design and implementation details for connecting atm and ip signaling domains and conclude with its extension to an arbitrary number of interconnected domains.
locating network monitors: complexity, heuristics, and coverage. there is an increasing interest in passive monitoring of ip flows at multiple locations within an ip network. the objective of such a distributed monitoring system is to sample packets belonging to a large fraction of ip flows in a cost-effective manner by carefully placing monitors and controlling their sampling rates. in this paper, we consider the problem of where to place monitors within the network and how to control their sampling. to address the tradeoff between monitoring cost and monitoring coverage, we propose and study minimum cost and maximum coverage problems under various budget constraints and in the presence of routing changes caused by link failures. we show that all of the problem formulations are np-hard. we propose greedy heuristics, and show that the heuristics provide solutions quite close to the optimal solutions through experiments using synthetic and real network topologies. in addition, our experiments show that a small number of monitors often suffices to monitor most of the traffic in an entire ip network.
secret sharing in graph-based prohibited structures. a secret sharing scheme for the prohibited structure is a method of sharing a master key among a finite set of participants in such a way that only certain pre-specified subsets of participants cannot recover the master key. a secret sharing scheme is called perfect if any subset of participants who cannot recover the master key obtains no information regarding the master key. in this paper, we propose an efficient construction of perfect secret sharing schemes for graph-based prohibited structures where a vertex denotes a participant and an edge does a pair of participants who cannot recover the master key. the information rate of our scheme is 2/n, where n is the number of participants.
spectral decomposition approach for transient analysis of multi-server discrete-time queues. previous work by the authors (see proceedings conf. on information sciences and systems, baltimore, usa, 1990) where the spectral decomposition method was used for the transient analysis of a single-server queue is generalized. for the arrival process a general discrete-time markovian batch arrival process is assumed, where the batch size distribution of the arrivals in successive slots is governed by a n-state discrete-time markov chain. it is shown that once the n eigenvalues of the probability generating matrix of the arrival process are obtained, the complete solution in the transform domain may be given. using the complex analysis technique and cauchy's integral formula, an efficient numerical method is presented for the calculation of a few performance measures. the numerical method is generalized to the situations where the superpositions of a number of independent arrival sources are fed to the queue. it is shown that the numerical complexity are fed to the queue. it is shown that the numerical complexity of obtaining the transient solution in this case can be substantially reduced by using an approach based on the kronecker product
all-optical lan interconnection with a wavelength selective router. this paper formulates the wavelength assignment issues an interconnecting optical broadcast-star local area networks (lans) through a wavelength routing bridge. static and dynamic approaches to partitioning of wavelengths for local and global traffic are compared using analysis and simulations. it is found that static wavelength assignment, the easiest algorithm to implement, is significantly outperformed by dynamic algorithms. several dynamic assignment algorithms are developed, and architectural issues in interconnecting optical networks are discussed. the dependence of the call blocking performance on system parameters, such as the traffic rate, the local and global traffic statistics, and the number of available wavelengths is examined in detail. a simple, yet accurate approximation is also developed to predict the blocking performance with an arbitrary number of lans.
leap forward virtual clock: a new fair queueing scheme with guaranteed delays and throughput fairness. we describe an efficient fair queuing scheme, leap forward virtual clock, that provides end-to-end delay bounds similar to wfq, along with throughput fairness. our scheme can be implemented with a worst-case time o(log log n) per packet (inclusive of sorting costs), which improves upon all previously known schemes that guarantee delay and throughput fairness similar to wfq. interestingly, both the classical virtual clock and the self-clocked fair queuing schemes can be thought of as special cases of our scheme, by setting the leap forward parameter appropriately.
congestion avoidance in atm networks. the authors propose a new policy to prevent congestion phenomena in asynchronous transfer mode (atm) networks. in particular, using a synthesis approach, they define and calculate the bandwidth which is assigned to every acceptable source from the atm network. this bandwidth, which varies between the peak and the average bandwidth demands of the particular source, is called effective or virtual, and is mainly characterized from the burstiness of the source. in constant bit rate sources the effective bandwidth is equal to the peak rate. based on the concept of effective bandwidth, a connection acceptance algorithm that leads to a very high utilization of network resources is formulated
token ring reliability models. a study of the reliability of token rings designed according to the ieee 802.5 standard is described. the reliability model is based on information in the standards, plus implementation details, and is more realistic than previous models. although the analysis is approximate, it includes all factors thought to be important in determining reliability, since an approximate analysis which included all such factors was felt to be more useful than an exact analysis which ignored important factors. the precise reliability measure analyzed is availability of a connection from a specified source to a specified destination. although the use of an active communications medium instead of a passive bus may decrease reliability of the token ring, the architecture gives great flexibility in bypassing or otherwise recovering from faults. for large networks this adds considerably to the reliability. if many devices are inactive, however, this advantage can be eliminated by even a small probability that inactive devices are not successfully bypassed
achieving near-optimal traffic engineering solutions for current ospf/is-is networks. traffic engineering aims to distribute traffic so as to "optimize" some performance criterion. this optimal distribution of traffic depends on both the routing protocol and the forwarding mechanisms in use in the network. in ip networks running the ospf or is-is protocols, routing is over shortest paths, and forwarding mechanisms distribute traffic "uniformly" over equal cost shortest paths. these constraints often make achieving an optimal distribution of traffic impossible. in this paper, we propose and evaluate an approach that can realize near optimal traffic distribution without changes to routing protocols and forwarding mechanisms. in addition, we explore the tradeoff that exists between performance and the configuration overhead that our solution requires. the paper's contributions are in formulating and evaluating an approach to traffic engineering in ip networks that achieves near-optimal performance while preserving the existing infrastructure.
qos provisioning and tracking fluid policies in input queueing switches. the concept of tracking fluid policies by packetized policies is extended to input queueing switches. it is considered that the speedup of the switch is one. one of the interesting applications of the tracking policy in tdma satellite switches is elaborated. for the special case of 2 &times; 2 switches, it is shown that a tracking nonanticipative policy always exists. it is found that, in general, nonanticipative policies do not exist for switches with more than two input and output ports. for the general case of n &times; n switches, a heuristic tracking policy is provided. the heuristic algorithm is based on two notions: port tracking and critical links. these notions can be employed in the derivation of other heuristic tracking policies as well. simulation results show the usefulness of the heuristic algorithm and the two basic concepts it relies on.
blocking in all-optical networks. we present an analytical technique of very low complexity, using the inclusion-exclusion principle of combinatorics, for the performance evaluation of all-optical, wavelength-division multiplexed networks with no wavelength conversion. the technique is a generalized reduced-load approximation scheme which is applicable to arbitrary topologies and traffic patterns. one of the main issues in computing blocking probabilities in all-optical networks is the significant link load correlation introduced by the wavelength continuity constraint. one of the models we propose takes this into account and gives good results even under conditions with high link load correlation. through numerous experiments we show that our models can be used to obtain fast and accurate estimates of blocking probabilities in all-optical networks and scale well with the path length and capacity of the network. we also extend one of our models to take into account alternate routing, ina the form of fixed alternate routing and least loaded routing.
application of network calculus to general topologies using turn-prohibition. network calculus is known to apply in general only to feedforward routing networks, i.e., networks where routes do not create cycles of interdependent packet flows. in this paper, we address the problem of using network calculus in networks of arbitrary topology. for this purpose, we introduce a novel graph-theoretic algorithm, called turn-prohibition (tp), that breaks all the cycles in a network and, thus, prevents any interdependence between flows. we prove that the tp-algorithm prohibits the use of at most 1/3 of the total number turns in a network, for any network topology. using analysis and simulation, we show that the tp-algorithm significantly outperforms other approaches for breaking cycles, such as the spanning tree and up/down routing algorithms, in terms of network utilization and delay bounds. our simulation results also show that the network utilization achieved with the tp-algorithm is within a factor of two of the maximum theoretical network utilization, for networks of up to 50 nodes of degree four. thus, in many practical cases, the restriction of network calculus to feedforward routing networks may not represent a too significant limitation.
mulilevel network management by means of system identification. the paper proposes a new approach to the management of large-scale communication networks. to manage large-scale communication networks effectively, it is essential to get a bird's-eye view of them when they are in their normal conditions. when an indication of faulty state is detected, the focus of the management is narrowed down to the faulty network elements. this management scheme is called multilevel network management. the paper proposes that system identification be used in multilevel network management. the system identification is used to measure transmission delays between two arbitrarily selected nodes in the networks, and multilevel network management is achieved by selecting those two nodes appropriately in accordance with the levels to be managed.