waashk/dblp huggingface dataset:
on-line routing and wavelength assignment for dynamic traffic in wdm ring and torus networks. we develop on-line routing and wavelength assignment (rwa) algorithms for wdm bidirectional ring and torus networks with n nodes. the algorithms dynamically support all k-allowable traffic matrices, where k denotes an arbitrary integer vector [k1, k2,..., kn], and node i, 1 ≤ i ≤ n, can transmit at most ki wavelengths and receive at most ki wavelengths. both algorithms support the changing traffic in a rearrangeably nonblocking fashion. our first algorithm, for a bidirectional ring, uses ⌈(σi=1n ki)/3⌉ wavelengths in each fiber and requires at most three lightpath rearrangements per new session request regardless of the number of nodes n and the amount of traffic k. when all the ki's are equal to k, the algorithm uses ⌈kn/3⌉ wavelengths, which is known to be the minimum for any off-line rearrangeably nonblocking algorithm. our second algorithm, for a torus topology, is an extension of a known off-line algorithm for the special case with all the ki's equal to k. for an r × c torus network with r ≥ c nodes, our on-line algorithm uses ⌈kr/2⌉ wavelengths in each fiber, which is the same as in the off-line algorithm, and is at most two times a lower bound obtained by assuming full wavelength conversion at all nodes. in addition, the on-line algorithm requires at most c - 1 lightpath rearrangements per new session request regardless of the amount of traffic k. finally, each rwa update requires solving a bipartite matching problem whose time complexity is only o(r), which is much smaller than the time complexity o(kcr2) of the bipartite matching problem for an off-line algorithm.
a new model for scheduling packet radio networks. packet radio networks are modeled as arbitrary graphs by most researchers. in this paper we show that an arbitrary graph is an inaccurate model of the radio networks. this is true because there exists a large class of graphs which will not model the radio networks. radio networks can be modeled accurately by a restricted class of graphs called the planar point graphs. since the radio networks can accurately be modeled only by a restricted class of graphs, the np-completeness results for scheduling using an arbitrary graph as the model, do not correctly reflect the complexity of the problem. in this paper we study the broadcast scheduling problem using the restricted class as the model. we show that the problem remains np-complete even in this restricted domain. we give an o(n log n) algorithm when all the transceivers are located on a line.
optimal multicast smoothing of streaming video over an internetwork. a number of applications such as internet video broadcasts, corporate telecasts, distance learning etc. require transmission of streaming video to multiple simultaneous users across an internetwork. the high bandwidth requirements coupled with the multi-timescale burstiness of compressed video make it a challenging problem to provision network resources for transmitting streaming multimedia. for such applications to become affordable and ubiquitous, it is necessary to develop scalable techniques which can efficiently deliver streaming video to multiple heterogeneous clients across a heterogeneous internetwork. in this paper, we propose using multicasting of smoothed video and differential caching of the video at intermediate nodes in the distribution tree, as techniques for reducing the network bandwidth requirements of such dissemination. we formulate the multicast smoothing problem, and develop an algorithm for computing the set of optimally smoothed transmission schedules for the tree (such that the transmission schedule along each link in the tree has the lowest peak rate and rate variability for any feasible transmission schedule for that link) given a buffer allocation to the different nodes in the tree. we also develop an algorithm to compute the minimum total buffer allocation to the entire tree and the corresponding allocation to each node, such that feasible transmission is possible to all the clients, when the tree has heterogeneous rate constraints. mpeg-2 trace-driven performance evaluations indicate that there are substantial benefits from multicast smoothing and differential caching. for example, our optimal multicast smoothing can reduce the total transmission bandwidth requirements in the distribution tree by more than a factor of 3 as compared to multicasting the unsmoothed stream.
an approach to pricing, optimal allocation and quality of service provisioning in high-speed packet networks. proposes a new methodology based on economic models to provide quality of service (qos) guarantees to competing traffic classes (classes of sessions) in packet networks. the authors consider an economic model of a packet network where resources are priced. traffic classes compete for network resources and they purchase them to satisfy their qos needs. the authors provide a new definition for qos provisioning based on economic models (pareto efficiency). they obtain the set of optimal resource allocations (pareto optimal) which provide qos guarantees to competing traffic classes. they show the impact on equilibrium prices and optimal allocations due to traffic load and variability, and qos requirements. they propose packet scheduling and admission policies to provide qos guarantees to traffic classes based on available qos and prices in the network.
a shared buffer architecture for interactive vod servers. video-on-demand (vod) servers need to be efficiently designed in order to support a large number of users viewing the same or different videos at different rates. while considering a disk-array based vod server, use of a shared buffer at the server end may be more economical than the sole use of dedicated buffers at each user's end. in this paper, we propose a simple buffer sharing architecture that may be used when disk-array based video servers are used. our aim is to support the maximum number of users for a given number of video server disks while employing a simple scheme requiring less buffer space. the number of video segment retrievals that can occur within a certain time (the service round) is maximum when the scan disk scheduling algorithm is used. consequently, we shall assume use of the scan algorithm for disk retrieval. the vod server has a buffer manager that directs retrieved segments to appropriate buffer locations depending on their release and deadlines. the release and deadlines of segments are such that buffer requirement at the user's set-top box is minimized to two video segments while avoiding video starvation and buffer overflow at the user's end. we propose a novel scheme for the operation of the shared buffer that aims at increasing buffer utilization and decreasing cell loss due to buffer overflow. an atm based broadband network is assumed and all segments are stored in buffers as fixed length atm cells.
a model for virtual tree bandwidth allocation in atm networks. the technique of virtual paths is used in atm networks to perform bandwidth allocation for virtual circuits and to simplify setting up of virtual circuits in response to connection requests. the author describe a new technique called virtual trees that can be used for bandwidth allocation in atm networks. a virtual tree corresponds to pre-allocated bandwidth along a set of links in the network that form a tree rooted at a source node and leading to various destinations. the use of virtual trees provides more flexibility to a source node in setting up a virtual circuit and results in smaller rejection probabilities for connection requests. virtual trees retain all the advantages of virtual paths but have a better performance potential. the authors present an optimization model for bandwidth allocation for virtual tree configurations and present the results of a simulation study comparing the performance of virtual trees with that of virtual paths.
multipoint communication by hierarchically encoded data. a novel multipoint communication paradigm, in which each destination receives a subset of the source's signal that corresponds to that destination's terminal and access bandwidth constraints, is presented. the approach to realizing this paradigm is based on integration of layered coding of the source's signal, routing based on bandwidth demand, optimization of signal parameters, and layered error control. the author gives an overview of several hierarchical signal coding techniques; presents methods for finding maximum bandwidth available to destination, establishing maximum-bandwidth routes; and optimally assigns bandwidth to the signal layers to maximize overall reception quality. error control procedures whereby the network, source, and destinations cooperate to maintain layered-based data integrity, using erasure recovery coding and prioritized packet detection are also presented
a distributed algorithm for delay-constrained unicast routing. in this paper, we study the np-hard delay-constrained least-cost path problem, and propose a simple, distributed heuristic solution: the delay-constrained unicast routing (dcur) algorithm. dcur requires limited network state information to be kept at each node: a cost vector and a delay vector. we prove dcur's correctness by showing that it is always capable of constructing a loop-free delay-constrained path within finite time, if such a path exists. the worst case message complexity of dcur is o(|v|^3) messages, where |v| is the number of nodes. however, simulation results show that, on the average, dcur requires much fewer messages. therefore, dcur scales well to large networks. we also use simulation to compare dcur to the optimal algorithm, and to the least-delay path algorithm. our results show that dcur's path costs are within 10% from those of the optimal solution.
preemption-based admission control in multimedia multiparty communications. in multimedia, multiparty communications a typical participant receives and often generates multiple real-time streams. network resources are dedicated to each stream and are dynamically allocated and released in response to changing users demands throughout the session. admission control procedures, which prioritize users' requests for stream delivery, and decide which resources to allocate, are considered. existing admission control schemes base their decisions on resources that are unused at the time of the request, and reject a request (or queue it) if there are insufficient unused resources. the paper presents a novel approach in which admission is based not only on the unused resources but also on the resources occupied by the streams that are currently received by the requestor. if sufficient unused resources to deliver a requested stream are not available, other streams that are delivered to the requestor are preempted and the resources they occupy are reallocated to satisfy the new request. the manner by which candidate streams for preemption are identified and resources are reallocated depends on the relative importance of the streams to the recipient and the topology of the paths leading to it. the effect of the routing used by the network on the topology of the paths leading to a multi-stream receiver is discussed and protocols for preemption-based reallocation are presented.
performance issues in crma networks for integrated broadband communications. the capabilities of the cyclic reservation multiple access (crma) protocol for supporting mixed video and data traffic was evaluated by computer simulation. the results show that in order to obtain good performance and fairness between all the mixed stations, they should have similar requirements in terms of the number of slots that are requested at each reservation cycle. it is therefore important to reduce the variability by aggregating more slots for stations with short packets, and by transmitting long frames in successive cycles for long packets. the optimal selection of the low and high bound on the number of slots can significantly improve the performance of the crma network under mixed traffic conditions
on bandwidth and storage tradeoffs in multimedia distribution networks. multimedia distribution on demand will impose extremely severe bandwidth requirements on the distribution network and will require the use of very high capacity video servers. in the context of archival programs playout (typical video-on-demand applications), the information source can potentially be stored at any level in the distribution network. part of the information may even be duplicated. of course, there is a tradeoff between the bandwidth required to transport the programs to the users and the storage server capabilities of the overall deployment. the paper presents an analytical study of this tradeoff considering different mechanisms aimed at reducing the overall bandwidth and/or storage server costs. a model of the distribution network is established. a cost function is proposed to capture the different parameters and allow comparison of the possible strategies. results provide good insight into the problem, and are used to discuss the proper placement of storage in a distribution network.
economics of network pricing with multiple isps. in this paper, we examine how transit and customer prices and quality of service are set in a network consisting of multiple isps. some isps may face an identical set of circumstances in terms of potential customer pool and running costs. we examine the existence of equilibrium strategies in this situation and show how positive profit can be achieved using threat strategies with multiple qualities of service. it is shown that if the number of isps competing for the same customers is large then it can lead to price wars. isps that are not co-located may not directly compete for users, but are nevertheless involved in a non-cooperative game of setting access and transit prices for each other. they are linked economically through a sequence of providers forming a hierarchy, and we study their interaction by considering a multi-stage game. we also consider the economics of private exchange points and show that their viability depends on fundamental limits on the demand and cost.
unreliable sensor grids: coverage, connectivity and diameter. we consider an unreliable wireless sensor grid network with n nodes placed in a square of unit area. we are interested in the coverage of the region and the connectivity of the network. we first show that the necessary and sufficient conditions for the random grid network to cover the unit square region as well as ensure that the active nodes are connected are of the form p(n)r^2(n)~log(n)/n, where r(n) is the transmission radius of each node and p(n) is the probability that a node is ''active'' (not failed). this result indicates that, when n is large, even if each node is highly unreliable and the transmission power is small, we can still maintain connectivity with coverage. we also show that the diameter of the random grid (i.e., the maximum number of hops required to travel from any active node to another) is of the order n/log(n). finally, we derive a sufficient condition for connectivity of the active nodes (without necessarily having coverage). if the node success probability p(n) is small enough, we show that connectivity does not imply coverage.
scalabel timers for soft state protocols. soft state protocols use periodic refresh messages to keep network state alive while adapting to changing network conditions; this has raised concerns regarding the scalability of protocols that use the soft-state approach. in existing soft state protocols, the values of the timers that control the sending of these messages, and the timers for aging out state, are chosen by matching empirical observations with desired recovery and response times. these fixed timer-values fail because they use time as a metric for bandwidth; they adapt neither to (1) the wide range of link speeds that exist in most wide-area internets, nor to (2) fluctuations in the amount of network state over time.we propose and evaluate a new approach in which timer-values adapt dynamically to the volume of control traffic and available bandwidth on the link. the essential mechanisms required to realize this scalable timers approach are: (1) dynamic adjustment of the senders' refresh rate so that the bandwidth allocated for control traffic is not exceeded, and (2) estimation of the senders' refresh rate at the receiver in order to determine when state can be timed-out and deleted. the refresh messages are sent in a round robin manner not exceeding the bandwidth allocated to control traffic, and taking into account message priorities.we evaluate two receiver estimation methods for dynamically adjusting network state timeout values: (1) counting of the rounds and (2) exponential weighted moving average.
a proof for lack of starvation in dqdb with and without slot reuse. dqdb is the ieee 802.6 mac standard protocol for metropolitan area networks. it is designed for the slotted, dual bus configuration. a simple way to improve the performance of dqdb is to perform slot reuse and many methods have been suggested in the past to efficiently incorporate slot reuse with dqdb. however, some of them can lead to starvation. the authors improve one of these previous suggestions and the main contribution of the paper is that for the first time they also provide a proof that the improved scheme ensures lack of starvation. they also specify this proof for the important case of dqdb without slot reuse.
scheduling data transfers in preemptive hierarchical switching systems with applications to packet radio networks. a communication switching system is considered where nodes communicate through transmitters and receivers that have the same bandwidth. communication constraints are imposed so that the number of active transmitters or receivers on designated subsets of nodes is bounded by prespecified values. the constraints are assumed to have a hierarchical structure. an algorithm is given that produces minimal length schedules of data transfers through the system if transmission preemption is allowed. a variation of the switching system when nodes communicate through transceivers is also considered, and accompanying scheduling algorithms are presented. applications to transmission scheduling in packet radio networks are discussed
big-bang simulation for embedding network distances in euclidean space. embedding of a graph metric in euclidean space efficiently and accurately is an important problem in general with applications in topology aggregation, closest mirror selection, and application level routing. we propose a new graph embedding scheme called big-bang simulation (bbs), which simulates an explosion of particles under a force field derived from embedding error. bbs is shown to be significantly more accurate compared to all other embedding methods, including gnp. we report an extensive simulation study of bbs compared with several known embedding schemes and show its advantage for distance estimation (as in the idmaps project), mirror selection, and topology aggregation.
the ordered core based tree protocol. this paper presents a new protocol, the ordered core based tree (ocbt) protocol, which remedies several shortcomings of the core based tree (cbt) multicast protocol. we show that the cbt protocol can form loops during periods of routing instability, and that it can consistently fail to build a connected multicast tree, even when the underlying routing is stable. the ocbt protocol provably eliminates these deficiencies and reduces the latency of tree repair following a link or core failure. ocbt also improves scalability by allowing flexible placement of the cores that serve as points of connection to a multicast tree. simulation results show that the amount of control traffic in ocbt is comparable to that in cbt.
real-time cell loss ratio estimation and its applications to atm traffic controls. the asymptotics of cell-loss ratio (clr) in the regime of large buffers are characterized by two parameters, the asymptotic constant and asymptotic decay rate. both parameters can be expanded in powers of one minus the link utilization (heavy traffic expansion), thus, once the coefficients in this expansion are obtained, the clr can be very easily estimated from the measured link utilization by using clr asymptotics. this paper proposes an algorithm for estimating these coefficients in, real time. for this purpose, the notion of state-space representation for a single-server queue is introduced: the elements of the state vector are the coeficients in the expansion of the asymptotic constant and asymptotic decay rate. bayesian regression analysis is applied to estimate the state vector based on the buffer measurement. our approach does not require any models describing the statistics of the traffic other than the asymptotic behavior of the clr in the regime of large buffers. in addition, it allows us to estimate the effective bandwidth of the aggregated process easily, so it is applicable to a wide range of atm traffic control methods, such as connection admission control and vp bandwidth control. we describe how this method of clr estimation will be ap- plied to connection admission control and vp bandwidth control by using results from simulation experiments.
performance analysis of mean internodal distance of connective semi-random networks. one of important properties of a multihop network is the mean internodal distance for evaluating transmission delay. the connective semi-random network achieves a smaller mean internodal distance than other networks. however, the results have only been obtained by computer simulation and no theoretical analysis has been performed. in this paper, we theoretically analyze the mean internodal distance of a connective semi-random network. moreover, we also theoretically analyze a restricted connective semi-random network whose network connective probability is larger than that of a conventional connective semi-random network. it is shown that the theoretical analyzed results agree well with the simulated results in a conventional model and our model with small restriction. the influence of restriction on the mean internodal distance becomes small as the number of outgoing links per node becomes large.
sensing the state of voice sources to improve multiplexer performance. the control of source-coded traffic at a multiplexer has been a topic of extensive research. traditional approaches typically use feedback information on the buffer level in designing the control policy. while important, buffer levels capture only part of the information about the overall system state. by setting up this problem as a markov decision process, the authors show that using information on the state (activity) of the sources, in addition to the buffer level, can result in significant improvements over traditional approaches. they demonstrate this for a multiplexer fed by /spl mu/-law encoded voice sources. some of the scenarios studied exhibit a reduction in distortion exceeding 35%. in general, the improvement is heavily dependent on the correlation statistics of the sources. emulations validate the analysis. the form and characteristics of the optimal control policies are also discussed.
a considerate priority queueing system with guaranteed policy fairness. a discrete-time queuing system supporting two classes of customers (packets of information) with different priorities is analyzed. unlike the head-of-the-line priority policy, the priority policy considered provides for limited service to the low-priority class, even in the presence of high-priority customers (considerate system). at the same time, it guarantees that no low-priority customer will be served before a previously arrived high-priority one (guaranteed policy fairness). the proposed policy can be seen as a compromise between the head-of-the-line priority policy and the classical gated/limited service priority policy. a general methodology is developed for the analysis of this policy