waashk/dblp huggingface dataset:
broadcast disks with polynomial cost functions. in broadcast disks systems, information is broadcasted in a shared medium. when a client needs an item from the disk, it waits until that item is broadcasted. broadcast disks systems are particularly attractive in settings where the potential customers have a highly-asymmetric communication capabilities, i.e., receiving is significantly cheaper than transmitting. this is the case with satellite networks, mobile hosts in wireless networks, and teletext system.the fundamental algorithmic problem for such systems is to determine the broadcast schedule based on the demand probability of items, and the cost incurred to the system by clients waiting. the goal is to minimize the mean access cost of a random client. typically, it was assumed that the access cost is proportional to the waiting time. in this paper, we ask what are the best broadcast schedules for access costs which are arbitrary polynomials in the waiting time. these may serve as reasonable representations of reality in many cases, where the "patience" of a client is not necessarily proportional to its waiting time.we present an asymptotically optimal algorithm for a fractional model, where the bandwidth may be divided to allow for fractional concurrent broadcasting. this algorithm, besides being justified in its own right, also serves as a lower bound against which we test known discrete algorithms. we show that the greedy algorithm has the best performance in most cases. then we show that the performance of other algorithms deteriorate exponentially with the degree of the cost polynomial and approaches the fractional solution for sub-linear cost. finally, we study the quality of approximating the greedy schedule by a finite schedule.
models of blocking probability in all-optical networks with and without wavelength changers. we introduce a traffic model for circuit switched all-optical networks (aons) which we then use to calculate the blocking probability along a path for networks with and without wavelength changers. we investigate the effects of path length, switch size, and interference length (the expected number of hops shared by two sessions which share at least one hop) on blocking probability and the ability of wavelength changers to improve performance. our model correctly predicts unobvious qualitative behavior demonstrated in simulations by other authors.
performance analysis of the atm shuffleout switching architecture under non-uniform traffic patterns. the authors describe a model for the performance evaluation of the shuffleout asynchronous transfer mode (atm) switch under arbitrary nonuniform traffic patterns. shuffleout is a blocking multistage structure using shortest path routing with deflection, in which output queues are connected to all the stages. the analytical model developed computes the load on each interstage link by tracing all the paths that a packet can follow to reach the addressed switch outlet, that is, by taking into account all the deflections from its shortest path it can receive. such a model allows the computation not only of the average load per stage but also its distribution over the different links belonging to the interstage pattern. thus fairness in packet switching by shuffleout is provided by the model
fast incremental updates for pipelined forwarding engines. pipelined asic architectures are increasingly being used in forwarding engines for high-speed ip routers. we explore optimization issues in the design of memory-efficient data structures that support fast incremental updates in such forwarding engines. our solution aims to balance the memory utilization across the multiple pipeline stages. we also propose a series of optimizations that minimize the disruption to the forwarding process caused by route updates. these optimizations reduce the update overheads by over a factor of two for a variety of different core routing tables and update traces.
degree-constrained multicasting in point-to-point networks. establishing a multicast tree in a point-to-point network of switch nodes, such as a wide-area atm network, is often modeled as the np-complete steiner problem in networks. in this paper, we study algorithms for finding efficient multicast trees in the presence of constraints on the copying ability of the individual switch nodes in the network. we refer to this problem as the degree-constrained multicast tree problem and model it as the degree-constrained steiner problem in networks. steiner heuristics for the degree-constrained case are proposed and their simulation results for sparse, point-to-point networks are presented. the results are compared with respect to their quality of solution, cost (running time), and the number of test cases for which no solution could be found. the results of our research indicate that efficient multicast trees can be found in large, sparse networks with small multicast groups even with limited multicast capability in the individual switches. some of the steiner heuristics tested yielded degree-constrained multicast trees within 5% of the best heuristic solution found in most of the cases. even when the fanout of each switch node was restricted to 2, the heuristics we used were able to generate efficient multicast trees in almost all our test networks. surprisingly few test networks were unsolvable. in those cases where no solution was found by a heuristic, backtracking solved many of the remaining cases. among the heuristics we used, degree-constrained versions of simple path-distance heuristics such as sph and sph-r provided the best tradeoffs between quality of solution and cost.
aries: a rearrangeable inexpensive edge-based on-line steiner algorithm. in this paper, we propose and evaluate aries, a heuristic for updating multicast trees dynamically in large point-to-point networks. the algorithm is based on monitoring the accumulated damage to the multicast tree within local regions of the tree as nodes are added and deleted, and triggering a rearrangement when the number of changes within a connected subtree crosses a set threshold. we derive an analytical upper-bound on the competitiveness of the algorithm. we also present simulation results to compare the average-case performance of the algorithm with two other known algorithms for the dynamic multicast problem, greedy and eba (edge-bounded algorithm). our results show that aries provides the best balance among competitiveness, computational effort, and changes in the multicast tree after each update.
an anchor chain scheme for ip mobility management. this work presents a simple mobility scheme for ip-based networks, termed the "anchor chain" scheme. the scheme combines pointer forwarding and caching methods. every mobile host (mh) is associated with a chain of anchors that connects it to its home agent. each anchor defines the location of the mh at a certain degree of accuracy. the accuracy is increased along the chain until the attachment point of the mh is reached. we develop distributed procedures for updating the anchor chain (binding operation) with mh movements and for delivering messages to a mh (delivery operation). in terms of worst case performance, the total cost of the binding operations is o(move log move), where move is the total geographic distance that the mh has traveled since its activation. the total length of the mh's pointer path is linear with the distance between the mh and its home network, and the delivery cost is near optimal. in addition, the anchor chain of a mh is determined dynamically with no need for preliminary definitions of static anchors or regions. our simulation results show that the anchor chain scheme also yields lower average overheads for both the binding and the delivery operations than other methods that are described in the literature, including the current home approach. we believe that the proposed scheme is scalable, fairly easy to implement and there fore attractive for supporting mhs.
efficient handoff rerouting algorithms: a competitive on-line algorithmic approach. this paper considers the design of handoff rerouting algorithms for reducing the overall session cost in personal communication systems (pcs). most modern communication systems that are used as an infrastructure for pcs networks are based on connection-based technologies. in these systems, the session cost is composed of two components. the setup cost represents the cost associated with the handoff operations, and the hold cost determines the expense related to the use of network resources held by the connection. this work introduces for the first time, rerouting algorithms for general graphs which are cost effective in terms of their worst-case analysis. the algorithms are analyzed using a competitive analysis approach, and it is proved that the competitive ratio of the proposed algorithms is a small constant of which the precise value depends on the ratio between the setup costs and the hold costs of the links. we also prove a lower bound of 2 on the competitive ratio of any online algorithm, which means that the proposed algorithms are close in terms of worst case behavior to the best possible rerouting algorithm. in addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.
robust monitoring of link delays and faults in ip networks. in this paper, we develop failure-resilient techniques for monitoring link delays and faults in a service provider or enterprise ip network. our two-phased approach attempts to minimize both the monitoring infrastructure costs as well as the additional traffic due to probe messages. in the first phase, we compute the locations of a minimal set of monitoring stations such that all network links are covered, even in the presence of several link failures. subsequently, in the second phase, we compute a minimal set of probe messages that are transmitted by the stations to measure link delays and isolate network faults. we show that both the station selection problem as well as the probe assignment problem are np-hard. we then propose greedy approximation algorithms that achieve a logarithmic approximation factor for the station selection problem and a constant factor for the probe assignment problem. these approximation ratios are provably very close to the best possible bounds for any algorithm.
delay jitter bounds and packet scale rate guarantee for expedited forwarding. we consider the definition of the expedited forwarding per-hop behavior (ef phb) as given in rfc 2598 and its impact on worst case end-to-end delay jitter. on the one hand, the definition in rfc 2598 can be used to predict extremely low end-to-end delay jitter, independent of the network scale. on the other hand, we find that the worst case delay jitter can be made arbitrarily large, while each flow traverses at most a specified number of hops, if we allow networks to become arbitrarily large; this is in contradiction with the previous statement. we analyze where the contradiction originates and find the explanation. it resides in the fact that the definition in rfc 2598 is not easily implementable in schedulers we know of, mainly because it is not formal enough, and also because it does not contain an error term. we propose a new definition for the ef phb, called "packet scale rate guarantee" (psrg) that preserves the spirit of rfc 2598 while allowing a number of reasonable implementations and has very useful properties for per-node and end-to-end network engineering. we show that this definition implies a rate-latency service curve property. we also show that it is equivalent, in some sense, to the stronger concept of "adaptive service guarantee." then we propose some proven bounds on delay jitter for networks implementing this new definition, both in cases without loss and with loss.
code assignment for hidden terminal interference avoidance in multihop packet radio networks. hidden terminal interference is caused by the simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. the authors investigate the problem of assigning orthogonal codes to stations to eliminate the hidden terminal interference and minimize the number of codes used. it is shown that this problem is computationally intractable, even for very restricted but very realistic network topologies. optimal algorithms for code assignment in special networks, as well as both centralized and distributed suboptimal heuristic algorithms for general topologies, are presented. the results of extensive simulations to derive the average performance of the proposed heuristics on realistic network topologies are presented
inference and labeling of metric-induced network topologies. the development and deployment of distributed network-aware applications and services require the ability to compile and maintain a model of the underlying network resources with respect to one or more characteristic properties of interest. to be manageable, such models must be compact; and to be general-purpose, should enable a representation of properties along temporal, spatial, and measurement resolution dimensions. in this paper, we propose mint¿a general framework for the construction of such metric-induced models using end-to-end measurements. we present the basic theoretical underpinnings of mint for a broad class of performance metrics, and describe periscope, a linux embodiment of mint constructions. we instantiate mint and periscope for a specific metric of interest¿namely, packet loss rates¿and present results of simulations and internet measurements that confirm the effectiveness and robustness of our constructions over a wide range of network conditions.
tcp boston: a fragmentation-tolerant tcp protocol for atm networks. the popularity of tcp/ip coupled with the premise of high speed communication using asynchronous transfer mode (atm) technology have prompted the network research community to propose a number of techniques to adapt tcp/ip to atm network environments. atm offers available bit rate (abr) and unspecified bit rate (ubr) services for best-effort traffic, such as conventional file transfer. however, recent studies have shown that tcp/ip, when implemented using abr or ubr, leads to serious performance degradations, especially when the utilization of network resources (such as switch buffers) is high. proposed techniques---switch-level enhancements, for example---that attempt to patch up tcp/ip over atms have had limited success in alleviating this problem. the major reason for tcp/ip's poor performance over atms has been consistently attributed to packet fragmentation, which is the result of atm's 53-byte cell-oriented switching architecture.in this paper, we present a new transport protocol, tcp boston, that turns atm's 53-byte cell-oriented switching architecture into an advantage for tcp/ip. at the core of tcp boston is the adaptive information dispersal algorithm (aida), an efficient encoding technique that allows for dynamic redundancy control. aida makes tcp/ip's performance less sensitive to cell losses, thus ensuring a graceful degradation of tcp/ip's performance when faced with congested resources. in this paper, we introduce aida and overview the main features of tcp boston. we present detailed simulation results that show the superiority of our protocol when compared to other adaptations of tcp/ip over atms. in particular, we show that tcp boston improves tcp/ip's performance over atms for both network-centric metrics (e.g., effective throughput) and application-centric metrics (e.g., response time).
application-layer anycasting. server replication is a key approach for maintaining user-perceived quality of service within a geographically wide-spread network. the anycasting communication paradigm is designed to support server replication by allowing applications to easily select and communicate with the ``best" server, according to some performance or policy criteria, in a group of content-equivalent servers. we examine the definition and support of the anycasting paradigm at the application layer, providing a service that maps anycast domain names into one or more ip addresses using anycast resolvers. in addition to being independent from network-layer support, our definition includes the notion of filters, functions that are applied to groups of addresses to affect the selection process. we consider both metric-based filters (e.g., server response time) and policy-based filters; we further allow filtering both at the anycast resolver and local to the anycast client. a key input to the filtering process is metric information describing the relative performance of replicated servers. we examine the use of various techniques for maintaining this information at anycast resolvers.
distributed channel allocation for pcn with bursty traffic. considers the design of efficient channel allocation algorithms in personal communication networks where the cells have varying traffic loads. a common communication channel is to be dynamically shared between the cells. the authors propose a distributed inter-cell channel allocation policy that is easy to implement through the use of simple signalling between neighboring cells. for cells arranged in a line they show that the proposed policy achieves maximum throughput. the same is true when the cells are arranged in a circle and the channel can be reused in every other cell. for larger reuse distances and planar hexagonal arrays, the policy may not always achieve maximal throughput. for these cases the authors provide regions of achievable cell throughputs under the proposed policy and show that they are tight in certain cases.
efficient rate-controlled bulk data transfer using multiple multicast groups. controlling the rate of bulk data multicast to a large number of receivers is difficult, due to the heterogeneity among the end systems' capabilities and their available network bandwidth. if the data transfer rate is too high, some receivers will lose data, and retransmissions will be required. if the data transfer rate is too slow, an inordinate amount of time will be required to transfer the data. in this paper, we examine an approach toward rate-controlled multicast of bulk data in which the sender uses multiple multicast groups to transmit data at different rates to different subgroups of receivers. we present simple algorithms for determining the transmission rate associated with each multicast channel, based on static resource constraints, e.g., network bandwidth bottlenecks. transmission rates are chosen so as to minimize the average time needed to transfer data to all receivers. analysis and simulation are used to show that our policies for rate selection perform well for large and diverse receiver groups and make efficient use of network bandwidth. moreover, we find that only a small number of multicast groups are needed to reap most of the possible performance benefits.
non stationary request distribution in video on demand networks. several works have recently appeared in the literature on the design, performance and dimensioning of networks supporting video on demand and multimedia services. it has been shown that performance is strongly dependent on the model adopted to describe the user's behaviour in terms of requests for programs. in this paper we provide a detailed investigation of a non stationary model for the user's request distribution. numerical results are provided for a network scenario proposed in the literature to investigate the error achieved when the non stationary distribution is approximated with a stationary exponential one.
fiber-optic bus-oriented single-hop interconnections among multi-transceiver stations. the single-path selective-broadcast interconnection (sbi) is a static, passive interconnection among a set of stations, each equipped with multiple c transmitters and receivers. it uses c 2 buses, each interconnecting a subset of the stations, and provides a single common bus to any two stations. the author explores those merits of this sbi which are related directly to its implementation in fiber optics. when compared with c buses, each interconnecting all stations, the sbi is shown to offer substantial advantages in power budget and the maximum number of stations that can be interconnected without repeaters or amplifiers. it is also attractive in terms of the required passive fiber optic components such as fiber segments and star couplers. for a fixed power budget and direct detection, the capacity of this sbi is shown to be highest among bus-oriented single-hop interconnections for both a uniform traffic pattern and the worst-case unknown skew
computing approximate blocking probabilities for a class of all-optical networks. studies a class of all-optical networks using wavelength division multiplexing and wavelength routing in which a connection between a pair of nodes in the network is assigned a path and a wavelength on that path. moreover, on the links of that path no other connection can share the assigned wavelength. using a generalized reduced load approximation scheme the authors calculate the blocking probabilities for the optical network model for two routing schemes: fixed routing and least loaded routing.
routing and wavelength assignment methods in single-hop all-optical networks with blocking. we consider single-hop all-optical networks in which wavelength-routed connections (lightpaths) between source-destination pairs are dynamically established and torn down in response to a random pattern of arriving connection requests and connection holding times. a connection request may be blocked if no wavelength is available on a suitable path from source to destination. for these networks we consider several methods for routing and wavelength assignment which combine in various ways three main principles: wavelength reservation, protecting threshold and alternate routes. the methods are evaluated and compared in two case studies. in this type of network the traffic over lightpaths consisting of multiple links is susceptible to high blocking probabilities, which can interfere with the quality of service requirements. it is shown that some of the routing and wavelength assignment methods studied have the potential to overcome this difficulty.
call admissibility for multirate traffic in wireless atm networks. for multirate wireless atm traffic, the first part of the call admission process is to determine whether to admit calls as long as bandwidth is available or to deny admission to a call of a particular class even if there is enough bandwidth available, in the hope of admitting calls of some other class later. a second part of the process is to determine if the quality of service requested by the call can be met. a scenario in which the first part is particularly important is when the blocking probability requirements for different classes is different. in this paper, we consider four policies to determine the circumstances under which calls of different types are {\it admissible}. for each of these policies, we show how to compute the blocking probabilities. for three of these policies, the blocking probabilities can be found by using results from product form networks. for the fourth, we provide an approximation which works extremely well in practice. we also formulate a non-linear programming problem which attempts to determine the parameters of the admissibility policies in such a way to maximize the call arrival rates while keeping the blocking probabilities under specified bounds. we provide an algorithm for solving the non-linear programming problem and use this as a basis for comparing the policies. we show that under some circumstances, it is possible to improve the system throughput by as much as 35\% by a suitable use of the admissibility policies. this improvement in throughput is particularly important in wireless atm networks, supporting high rate multimedia traffic because of the inherent limitations in bandwidth availability.