waashk/dblp huggingface dataset:
spanning tree method for link state aggregation in large communication networks. we consider a communication network in which dynamic routing is used for establishing connections that support information transfer between end-users. link state information is exchanged and maintained up-to-date among network nodes for path computation and network resource allocation. when the population of users is large, the amount of link state information can be overwhelming. a common solution is to use a hierarchical structure. in this paper, we present a method for aggregating link state information in a hierarchical network. we assume that each link state parameter associated with a link is symmetrical in both directions of the link. the key idea for the method is to first reduce the original subnetwork topology to a full-mesh representation that consists of a logical link for each pair of border nodes in the subnetwork, and then encode the link state information associated with the full-mesh representation with an appropriate spanning tree.
blocking in a completely shared resource environment with state dependent resource and residency requirements. the generalized erlang blocking model has been used to analyze multiplexing, message storage, and communication network performance. the author modifies this model to permit blocked requests to retry, with reduced resource requirements and arbitrary mean residency requirements. because the modification of the generalized erlang model destroys the product-form structure and greatly increases the size of the state space, and exact solution is out of the question. the present approach modifies a well-known one-dimensional recursion developed for the generalized erlang model in an intuitively satisfying manner, and results in an approximation scheme that is both efficient and quite accurate. this study arose in the context of high-speed networks in which high bandwidth but non-real-time messages may, upon being blocked, request service with smaller bandwidth and larger residency time, as long as the bandwidth-residency time product is the same as originally requested
dynamic global packet routing in wireless networks. we consider schemes for reuse-efficient packet access in wireless data networks. we show that computing the maximum ergodic packet arrival rate is np-hard. we give an upper bound on the maximum ergodic throughput in terms of the eigenvalues of matrices related to the path-gain matrix. we present simple, practical heuristic algorithms which exhibit good throughput and packet delay and report on results of preliminary simulations. more sophisticated algorithms that yield optimal throughput are also presented. a recent result of mckeown, anantharam and walrand on scheduling of input-queued switches is obtained as a byproduct.
generalized longest queue first: an adaptive scheduling discipline for atm networks. in this paper, we propose a generalized longest queue first (glqf) service discipline for atm networks. we classify sources so that sources in one class have the same cell loss probability requirement. assume that there are n classes of traffic. under this discipline, buffer i is assigned a positive number wi for the weight of buffer i. the scheduler transmits a cell from the buffer that has the maximal weighted queue length. the advantage of this discipline is that it can adapt to temporary overload quickly. we approximate the queue length distribution by decomposing the system into n single server queues with probabilistic service discipline. our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments and the coupling technique. for high utilization, we present a heavy traffic limit theorem.
two-way tcp traffic over atm: effects and analysis. we examine the performance of bidirectional tcp/ip connections over asynchronous transfer mode (atm) networks using the available bit rate (abr) service. the problem of ``ack-compression'' re-appears, although the queues are primarily at the end-systems. we further the understanding of the problem by quantitatively analyzing the periodic bursty behavior of the source ip queue. we are able to predict the peak values for the queue and arrive at a simple robust predictor for the degraded throughput, applicable for relatively general situations.the degradation in throughput due to bidirectional traffic can be significant. for example, even in the simple case of symmetrical connections with adequate window sizes, the throughput of each connection is only 66.67% of that under one-way traffic. we validate our analysis using simulation, where the atm network uses the explicit rate option. we show that the analysis predicts the behavior of the queue and the throughput degradation. we observe the need to separate the flow of acknowledgments and data for the bidirectional tcp connection and for inter-leaving their processing at the end-systems to overcome the problem of ack compression.
explicit window adaptation: a method to enhance tcp performance. we study the performance of tcp in an internetwork consisting of both rate-controlled and non-rate-controlled segments. a common example of such an environment occurs when the end systems are part of ip datagram networks interconnected by a rate-controlled segment, such as an atm network using the abr service. in the absence of congestive losses in either segment, tcp keeps increasing its window to its maximum size. mismatch between the tcp window and the bandwidth-delay product of the network will result in accumulation of large queues and possibly buffer overflows in the devices at the edges of the rate-controlled segment, causing degraded throughput and unfairness. we develop an explicit feedback scheme, called explicit window adaptation based on modifying the receiver''s advertised window in tcp acknowledgments returning to the source. the window size indicated to tcp is a function of the free buffer in the edge device. results from simulations with a wide range of traffic scenarios show that this explicit window adaptation scheme can control the buffer occupancy efficiently at the edge device, and results in significant improvements in packet loss rate, fairness, and throughput over a packet discard policy such as drop-from-front or random early detection.
analysis of delay performance of atm signaling link. the paper presents an analytic model to explore the delay performance of sscop (service specific connection oriented protocol), which is a signaling protocol for establishing and removing b-isdn connections in a switched virtual circuit (svc) atm network. a comparison with simulation shows that the analytic model works very well in spite of many complexities of the protocol. such a model is invaluable for choosing appropriate protocol parameters, setting delay requirements, and for studying error monitoring algorithms for atm signaling links.
channel sharing scheme for packet-switched cellular networks. in this paper, we study an approach for sharing channels to improve network utilization in packet-switched cellular networks. our scheme exploits unused resources in neighboring cells without the need for global coordination. we formulate a minimax approach to optimizing the allocation of channels in this sharing scheme. we develop a measurement-based distributed algorithm to achieve this objective and study its convergence. we illustrate, via simulation results, that the distributed channel sharing scheme performs significantly better than the fixed channel scheme over a wide variety of traffic conditions.
a performance study of selective cell discarding using the end-of-packet indicator in aal type 5. the atm adaptation layer type 5 (aal5) is a new adaptation layer protocol for the atm layer of broadband integrated services digital networks. among several features, it is unique in the sense that it includes an end-of-packet (eop) indicator in the header of the atm cell (the atm-layer-user-to-atm-layer-user (auu) parameter in the payload type (pt) field). it was previously suggested that the use of this indicator may be used to provide a means by which buffer occupancy can be reduced by dropping cells from already incomplete packets (armitage, 1993). the objective of this paper is to study the performance of this layer and the effectiveness of the eop indicator. the performance measures of interest are the probability of packet loss and the mean packet delay. an approximate analytical model is constructed in which the blocking of a tagged source is kept track of in an exact manner. the rest of the sources are modeled approximately. the accuracy of the model is enhanced through an iterative approach. a simulation model is also constructed to assess the accuracy of the approximate model.
implementation of self-healing function in atm networks based on virtual path concept. this paper proposes an implementation scheme for the self-healing function in atm networks and assesses its performance. first, our proposed atm self-healing scheme is described. this scheme realizes more rapid restoration of failed virtual paths than other self-healing algorithms, supports the node failure case, and minimizes the spare resources required. next, an implementation scheme is proposed. we propose that the self-healing function be implemented as a software process, and that oam cells are utilized for fast message transmission. next, results of a prototype system that we implemented on an atm cross-connect system are discussed. the fundamental characteristics of restoration performance are measured using an experimental network. based on these results, an ne processing system analysis and computer simulation for estimating the characteristics as applied to a real-scale network are discussed. finally, a management scheme for self-healing is proposed based on the tmn concept.
queueing analysis of atm tandem queues with correlated arrivals. considers tandem queues with correlated arrivals and joining interference, which model a portion of a virtual circuit at the access node in an atm network. the authors focus the main analysis on a two-node tandem network, which they model as a discrete-time queueing system. they derive a functional equation relating the joint generating function of this system between two consecutive slots. the functional equation is then transformed into a suitable form, which enables the derivation of the steady-state joint generating function of the contents of the queues. from this, any moment of the queue length at each node can be extracted. they also give explicit expressions for the average time delay at each node as well as for the total average delay in the network. they illustrate the solution technique by some numerical examples.
adaptive load sharing for network processors. a novel scheme for processing packets in a router is presented that provides load sharing among multiple network processors distributed within the router. it is complemented by a feedback control mechanism designed to prevent processor overload. incoming traffic is scheduled to multiple processors based on a deterministic mapping. the mapping formula is derived from the robust hash routing (also known as the highest random weight--hrw) scheme, introduced in k. w. ross, ieee network, 11(6), 1997, and d. g. thaler et al., ieee trans. networking, 6(1), 1998. no state information on individual flow mapping has to be stored, but for each packet, a mapping function is computed over an identifier vector, a predefined set of fields in the packet. an adaptive extension to the hrw scheme is provided to cope with biased traffic patterns. we prove that our adaptation possesses the minimal disruption property with respect to the mapping and exploit that property to minimize the probability of flow reordering. simulation results indicate that the scheme achieves significant improvements in processor utilization. a higher number of router interfaces can thus be supported with the same amount of processing power.
smart retransmission: performance with overload and random losses. feedback flow control, in conjunction with limited buffering in the network, inevitably leads to packet loss. effective congestion control requires not only effective flow control but also a good retransmission strategy. we present a new retransmission strategy called smart that combines the best features of the traditional go-back-n and selective-retransmit strategies.we show, first, that go-back-n retransmission with static window flow control leads to congestion collapse when the nominal load exceeds the link capacity. second, we can avert congestion collapse by replacing go-back-n with smart retransmission, even with static window flow control. third, smart retransmission, when combined with packet-pair rate-based flow control, performs extremely well, both when losses are due to buffer overflows and when losses are random.
distributing layered encoded video through caches. the efficient distribution of stored information has become a major concern in the internet which has increasingly become a vehicle for the transport of stored video. because of the highly heterogeneous access to the internet, researchers and engineers have argued for layered encoded video. in this paper, we investigate delivering layered encoded video using caches. based on the stochastic knapsack theory, we develop a model for the layered video caching problem. we propose heuristics to determine which videos and which layers in the videos should be cached in order to maximize the revenue from the streaming service. we evaluate the performance of our heuristics through extensive numerical experiments. we find that, for typical scenarios, the revenue increases nearly logarithmically with the cache size and linearly with the link bandwidth that connects the cache to the origin servers. we also consider service models with request queuing and negotiations about the delivered stream quality and find that both extensions provide only small revenue increases.
on guaranteed smooth scheduling for input-queued switches. input-queued switches are used extensively in the design of high-speed routers. as switch speeds and sizes increase, the design of the switch scheduler becomes a primary challenge, because the time interval for the matching computations needed for determining switch configurations becomes very small. possible alternatives in scheduler design include increasing the scheduling interval by using envelopes [19], and using a frame-based scheduler that guarantees fixed rates between input-output pairs. however, both these alternatives have significant jitter drawbacks: the jitter increases with the envelope size in the first alternative, and previously-known methods do not guarantee tight jitter bounds in the second.in this paper, we propose a hybrid approach to switch scheduling. traffic with tight jitter constraints is first scheduled using a frame-based scheduler that achieves low jitter bounds. jitter-insensitive traffic is later scheduled using an envelope-based scheduler. the main contribution of this paper is a scheduler design for generating low-jitter schedules. the scheduler uses a rate matrix decomposition designed for low jitter and different from the minimum-bandwidth birkhoff-von neumann (bv) decomposition. in addition to generating low-jitter schedules, this decomposition in the worst case yields fewer switch configuration matrices (o(n)) than the bv decomposition (o(n2)), and so requires far less high-speed switch memory. we develop an efficient algorithm for decomposing the rate matrix and for scheduling the permutation matrices. we prove that our low-jitter algorithm has an o(logn) factor bound on its bandwidth consumption in comparison to the minimum-bandwidth bv decomposition. experimentally, we find that the bandwidth increase in practice is much lower than the theoretical bound. we also prove several related performance bounds for our scheduler. finally, we propose a practical algorithm for bandwidth-guaranteed algorithm, and show how our findings could even be extended to systems with large tuning time.
harmonic buffer management policy for shared memory switches. in this paper we consider shared-memory switches. we introduce a novel general nonpreemptive buffer management scheme, which considers the queues ordered by their size. we propose a new scheduling policy, based on our general scheme, which we call the harmonic policy. we analyze the performance of the harmonic policy by means of competitive analysis and demonstrate that its throughput competitive ratio is at most ln(n) + 2, where n is the number of output ports. we also present a lower bound of ω(log n/log log n) on the performance of any online deterministic policy. our simulations also show that the harmonic policy achieves high throughput and easily adapts to changing load conditions.
performance evaluation of packet data services over cellular voice networks. in this paper we develop a markov chain modeling framework for throughput/delay analysis of data services over cellular voice networks, using dynamic channel stealing method. some effective approximation techniques are also proposed and verified for simplification of modeling analysis. our study identifies the average voice call holding time as the dominant factor to affect data delay performance. especially in heavy load conditions, namely when the number of free voice channels becomes momentarily less, the data users will experience large network access delay in the range of several minutes or longer on average. we also examine the data performance improvement by using priority data access scheme and speech silence detection technique.
traffic characterization and switch utilization using a deterministic bounding interval dependent traffic model. compressed digital video is one of the most important types of traffic in future integrated services networks. it is difficult to support this class of traffic since, on one hand, compressed video is bursty, while on the other hand, it requires performance guarantees from the network. the common belief is that we are unlikely to achieve a high network utilization while providing performance guarantees to such bursty sources. the authors introduce a new deterministic bounding interval-dependent (d-bind) traffic model, together with tight analysis techniques, to explore the possibility of providing deterministic performance guarantees to vbr traffic while still achieving a reasonable network utilization. the d-bind model consists of a family of rate-interval pairs where the rate is a bounding rate over the interval length. the model captures the intuitive property that over longer interval lengths, a source may be bounded by a rate lower than its peak rate and closer to its long-term overage rate. while the d-bind model is a general deterministic model that can be used to characterize a wide variety of sources, the authors focus on mpeg-compressed video. using two 10 minute traces, they demonstrate the effectiveness of the new model and show that, contrary to common belief, reasonable network utilization can be achieved for compressed video, even when deterministic guarantees are provided.
a control theoretic approach to the design of closed loop rate based flow control for high speed atm networks. in this paper we present a control theoretic approach to the design of closed loop rate based flow control in high speed networks. the proposed control uses a dual proportional derivative controller, where the control parameters can be designed to ensure the stability of the control loop in a control theoretic sense, over a wide range of traffic patterns and propagation delays. we show how the control mechanism can be used to design a controller to support abr service based on feedback of explicit rates. we demonstrate the excellent transient and steady state performance of the controller through a number of examples.
multicasting for multimedia applications. the authors investigate multicast routing for high-bandwidth delay-sensitive applications in a point-to-point network as an optimization problem. they associate an edge cost and an edge delay with each edge in the network. the problem is to construct a tree spanning the destination nodes, such that it has the least cost, and so that the delay on the path from the source to each destination is bounded. since the problem is computationally intractable, the authors present an efficient approximation algorithm. experimental results through simulations show that the performance of the heuristic is near optimal
efficient analysis of polling systems. a large variety of computer communications systems, in particular the token ring network, are modeled and analyzed as polling systems. the authors present the descendant set approach as a general efficient algorithm for deriving all moments of packet delay (in particular, mean delay) in these systems. the method can apply to a very large variety of model variations including: the exhaustive, gated, and fractional service policies; the cyclic visit order; arbitrary periodic visit orders, (polling tables); random polling orders; and customer routing. for most variations the method significantly outperforms the algorithms commonly used
the designer's perspective to noncooperative networks. a noncooperative network is considered, in which each user routes its flow in a way that optimizes its individual performance objective. nash equilibria characterize the operating points of the network. the network designer aims to allocate link capacities, so that the resulting nash equilibria are efficient, according to some system-wide performance criterion. in a noncooperative setting, the solution of such design problems is, in general, complex and at times counterintuitive, since adding link capacity might lead to degradation of user performance. for systems of parallel links, it is shown that such paradoxes do not occur and that the capacity allocation problem has a simple and intuitive optimal solution, that coincides with the solution in the single-user case. extensions to general network topologies are also derived.
on wavelength translation in all-optical networks. in this paper we study the benefits of wavelength translation in all-optical networks providing clear channel circuit-switching among users. we first establish approximate analytical models for a static-routing circuit-switched network with an arbitrary topology, both with and without wavelength translation. we then study performance of the non-blocking centralized switch, the mesh-torus network and the ring network, using the analytical models and simulation results. it is shown that the analytical models match the simulation results very well in the case of the centralized switch and the mesh network. the results of our study also show that the benefits of wavelength translation are marginal for the centralized switch and the ring network. on the other hand, the results show that wavelength translation can significantly improve performance of a large mesh network.
approximate analysis of the end-to-end delay in atm networks. a very general approach for an approximate analysis of end-to-end delay jitter in asynchronous transfer mode (atm) networks for bursty input traffic is presented. since the cell loss requirements within atm networks are very restrictive, interest is in the tail of the complementary probability distribution function of the end-to-end delay to estimate the cell loss probability at the reassembly buffer. an analytical approach for an isolated network node as well as for a whole reference connection is presented. the approximation results are in good agreement with simulation results and indicate that the end-to-end delay jitter is in the range of the maximum transfer delay of one queuing node, if the bursty input traffic is controlled by adequate traffic control mechanisms