waashk/dblp huggingface dataset:
restricted dynamic steiner trees for scalable multicast in datagram networks. the paper addresses the issue of minimizing the number of nodes involved in the routing over a multicast tree and in the maintenance of such a tree in a datagram network. it presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. the main concepts behind this scheme is to view each multicast tree as a collection of unicast paths, and to locate only the multicast source and destination nodes on the junctions of their multicast tree. the paper shows that despite of this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all the nodes along the data path of a tree to participate in the routing over the tree and in the maintenance of the tree.
performance evaluations of a metaring mac protocol integrating video and data traffics in an interconnected environment. the metaring is a medium access control (mac) protocol for lans and mans operating at a speed of 1 gbit/sec and above. the metaring mac protocol offers its users synchronous and asynchronous types of services and can operate under two basic access control modes: buffer insertion for variable size packets, and slotted for fixed length cells. the latter mode of operation is considered in this paper. in the first part of the paper an analysis of the asynchronous type of service is performed. the analysis has been carried out on a network configuration (hereafter called scenario) which, other than being realistic, is particularly critical with respect to slot reuse. it consists of a group of equally spaced nodes sending asynchronous traffic to a gateway interconnecting the metaring with other communication subnetworks. results obtained show that the metaring is unfair and that the unfairness depends, in particular, upon the offered load, besides the k and l protocol parameter values. in the second part of the paper we focus on the study of the traffic integration capability provided by the metaring mac protocol. the results provide a strong indication that the metaring mac protocol is suitable for vbr video and data traffic integrations.
an application of superpositions of two-state markovian sources to the modelling of self-similar behaviour. we present a modelling framework and a fitting method for modelling second order self-similar behaviour with the markovian arrival process (map). the fitting method is based on fitting to the auto-correlation function of counts for a second order self-similar process. it is shown that with this fitting algorithm it is possible closely to match the auto-correlation function of counts for a second order self-similar process over 3-5 time-scales with 8-16 state maps with a very simple structure i.e. a superposition of 3 respectively 4 interrupted poisson processes (ipp) and a poisson process. the fitting method seems to work well over the entire range of the hurst parameter.
optimal routing in communication networks with delay variations. the authors address the problem of optimal routing in packet switched networks. optimality is discussed in terms of end-to-end delay. the variance of delay as well as its mean value are taken into account. achieving optimal routing is necessary for multimedia networks to fully support real-time services. a network is modeled as a weighted graph with its link weights representing link delays. it is assumed that the delay statistics conform to a normal distribution. in the course of analysis, it is shown that this type of routing optimization problem can be formulated as a process of searching for a specific point in a coordinate system defined by the mean and variance of the end-to-end delay. an efficient algorithm is presented for finding the optimal point in this coordinate system
competitive queue policies for differentiated services. we consider the setting of a network providing differentiated services. as is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet or a low priority packet. outgoing links in the network are serviced by a single fifo queue.our model gives a benefit of α ≥ 1 to each high priority packet and a benefit of 1 to each low priority packet. a queue policy controls which of the arriving packets are dropped and which enter the queue. once a packet enters the queue it is eventually sent. the aim of a queue policy is to maximize the sum of the benefits of all the packets it sends.we analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. we derive both upper and lower bounds for the policies we consider. we believe that competitive analysis gives important insight to the performance of these queuing policies.
finite and infinite qbd chains: a simple and unifying algorithmic approach. in this paper, we present a novel algorithmic approach, the hybrid matrix geometric/invariant subspace method, for finding the stationary probability distribution of the finite qbd process which arises in performance analysis of computer and communication systems. assuming that the qbd state space is defined in two dimensions with m phases and k+1 levels, the solution vector for level k, \pi_k, 0 \leq k \leq k is shown to be in a modified matrix geometric form \pi_k = v_1 r_1^k + v_2 r_2^{k-k} where r_1 and r_2 are certain solutions to two nonlinear matrix equations and v_1 and v_2 are vectors to be determined using the boundary conditions. we show that the matrix geometric factors r_1 and r_2 can simultaneously be obtained independently of k via finding the sign function of a real matrix by an iterative algorithm with quadratic convergence rates. the time complexity of obtaining the coefficient vectors v_1 and v_2 is shown to be o(m^3 \log_2 k) which indicates that the contribution of the number of levels on the overall algorithm is minimal. besides the numerical efficiency, the proposed method is numerically stable and in the limiting case of k \rightarrow \infty, it is shown to yield the well-known matrix geometric solution \pi_k = \pi_0 r_1^k for the infinite qbd chain.
achieving stability in networks of input-queued switches. recent research has generated many interesting results on scheduling input-queued switches. however, most of this work focuses on a single switch in isolation. in this paper, we study the problem of scheduling a network of input-queued switches. we consider the longest-queue-first and longest-port-first scheduling policies that are stable for a single switch, and show that they can be unstable even for a fixed traffic pattern in a simple network of eight input-queued switches. moreover, this result holds regardless of how the traffic sharing the same port-pair is scheduled at each switch. on the positive side, we present a policy, longest-in-network, that is stable in networks of input-queued switches. this result holds even if the traffic pattern is allowed to change over time.
a new hierarchical routing protocol for dynamic multihop wireless networks. the routing techniques used in conventional packet radio networks are not suitable for dynamic multihop wireless networks because of their unique architecture. in this paper, a new hierarchical multihop routing algorithm is introduced which balances the cost of location-update and path-finding operations by partitioning the terminals and mobile base stations to produce a virtual topology. based on the virtual topology, each network entity stores a fraction of the network topology information and maintains the routing efficiency. finally, the performance of the hierarchical multihop routing algorithm is investigated through simulations.
minimizing end-to-end delay in high-speed networks with a simple coordinated schedule. we study the problem of providing end-to-end delay guarantees in connection-oriented networks. in this environment, multiple-hop sessions coexist and interfere with one another.parekh and gallager showed that the weighted fair queueing (wfq) scheduling discipline provides a worst-case delay guarantee comparable to (1/ρi) × ki for a session with rate ρi and ki hops. such delays can occur since a session-i packet can wait for time 1/ρi at every hop.we describe a randomized work-conserving scheme that guarantees, with high probability, an additive delay bound of approximately 1/ρi + ki. this bound is smaller than the multiplicative bound (1/ρi) × ki of wfq, especially when the hop count ki is large. we call our scheme coordinated-earliest-deadline-first (cedf) since it uses an earliest-deadline-first approach in which simple coordination is applied to the deadlines for consecutive hops of a session. the key to the bound is that once a packet has passed through its first server, it can pass through all its subsequent servers quickly.we conduct simulations to compare the delays actually produced by the two scheduling disciplines. in many cases, these actual delays are comparable to their analytical worst-case bounds, implying that cedf outperforms wfq.
on simple algorithms for dynamic load balancing. the paper focuses on the dynamic resource allocation problem. in communication networks such as wireless or circuit switching networks, resources correspond to base stations or links, and the load corresponds to the calls in the network. the principle of load balancing is examined for dynamic resource allocation. the question of interest is the performance of simple allocation strategies which can be implemented online. either finite capacity constraints on resources or mobility of users can be incorporated into the setup. the load balancing problem is formulated as an optimal control problem, and variants of a simple "least loaded routing" policy are shown to be asymptotically optimal for large call arrival rates.
design of a survivable wdm photonic network. i we consider schemes for protecting a network using a wavelength division multiplexing (wdm) infrastructure against component or link failures. first, we explain how protection can be achieved by hardware redundancy. then, we consider that with wdm networks, the failure of a single link or component may cause the simultaneous failure of several optical channels, potentially making impossible the restoration by rerouting in higher layers (sdh, atm, ip). to address this, we introduce the concept of design protection, which aims at making such failure propagations impossible. we present the disjoint alternate path (dap) algorithm which places optical channels in order to maximise design protection. we show the result on the example of the arpa-2 network.
the fat banyan atm switch. a strategy for fully utilizing switch resources, namely the buffers and links in a banyan network is proposed. a new switch model called the fat-banyan switch is introduced with the objective of achieving high performance at minimal cost. the fat-banyan switch model is a unifying model for the design and analysis of dilated banyan switches. the dilated banyan network forms a special case of the fat-banyan model. by keeping the number of input and output links of a switching element to be variable, the fat-banyan switch achieves a lower order of complexity than the dilated banyan. further the fat-banyan switch is superior to the buffered-banyan switch in terms of reduced delay and higher throughput. the performance of the fat-banyan under independent uniform traffic pattern is analyzed.
efficient broadcast using selective flooding. broadcast protocols are closely linked with point-to-point shortest routing in computer networks, and for broadcasting certain identified information, such as topological changes across the network. multi-address messages entail high overheads. reliable and efficient broadcasts are required to properly utilize the network bandwidth and ensure that users update the identified important information. it is assumed that local topological information in terms of connectivity is available at the nodes. this relative relationship is used predictively to reduce redundant transmissions in the broadcast of messages across the network; a simulation study shows the reduction to be significant. furthermore, for regular topologies, the redundancy in transmission can be shown to be zero. in conjunction with appropriate selectivity of information to the broadcast, an efficient and reliable broadcast is obtained. this work is relevant to networks with frequently changing topology in packet radio, cellular telephone, and strategic networks
optimal scheduling of soft handoffs in ds/cdma communication systems. considers the problem of optimal scheduling of soft handoffs as applicable to ds/cdma based cellular networks. the authors have formulated the phenomenon of soft handoffs as a reward/cost stochastic optimization problem wherein the reward is a function of some measurable characteristics of the received signal, and cost can be associated with different factors such as multiple simultaneous active connections, connection set-up and termination overheads. using dynamic programming, a maximum net reward policy that specifies the optimal base stations the mobile should be associated with during each time slot, is determined. the authors also extend their results to the case when there are more than two base stations. furthermore, the decisions are taken in a decentralized online manner. simulation results show that the proposed algorithms offer considerable improvement over the policy proposed in the is-95 standard.
performance improvement of fast packet switching by ldoll queueing. low delay or low loss (ldoll) queuing policies for asynchronous transfer model (atm) fast packet switching allow either retrieval priority or storage priority to be given to the atm cells of traffic streams with different performance requirements. the improvements in performance that can be achieved by using one bit in the atm cell header to make the binary ldoll distinction are analyzed. in the analysis, simulation of the level, where the cell transmission rate of a source may vary between zero and the peak rate and computation at the level, where queuing of individual cells is considered, are combined. it is shown that ldoll queuing, compared with fifo queuing in atm switches, can reduce cell loss probability by many orders of magnitude for low loss traffic. low delay traffic incurs a slightly higher cell loss which is compensated with a reduced cell delay mean and variance
routing strategies for fast networks. modern fast packet switching networks are being forced to rethink the routing schemes that are used in more traditional networks. the reexamination is necessitated because in these fast networks switches on the message's route can afford to make only minimal and simple operations. for example, examining a table of a size proportional to the network size is out of the question. in this paper we examine routing strategies for such networks based on flooding and predefined routes. our concern is to get both efficient routing and an even (balanced) use of network resources. we present efficient algorithms for assigning weights to edges in a controlled flooding scheme but show that the flooding scheme is not likely to yield a balanced use of the resources. we then present efficient algorithms for choosing routes along: 1) bfs trees and 2) shortest paths. we show that in both cases a balanced use of network resources can be guaranteed.
the effects of tuning time in bandwidth-limited optical broadcast networks. we consider the effects of tuning delay in optical broadcast networks. we show that for off-line scheduling these effects are small even if the tuning time is as large as the packet duration. in particular, we consider scheduling of random traffic with tunable transmitters and fixed-tuned receivers. we provide a lower bound to the completion time of any off-line schedule with an arbitrary number of wavelengths. we then describe a near-optimal schedule which is based on the principle of having idle transmitters tune to wavelengths just-in-time to start their transmissions. stability and capacity issues in the transmission of real-time traffic are considered. we show that the scheduling problem admits a single stable equilibrium point, and point out how the traffic capacity of a broadcast network can be reached. we also consider the implications in connection-oriented networks.
interaction of tcp flows as billiards. the aim of this paper is to analyze the performance of a large number of long-lived tcp controlled flows sharing many routers (or links), from the knowledge of the network parameters (capacity, buffer size, topology) and of the characteristics of each tcp flow (rtt, route etc.) when taking synchronization into account. it is shown that in the small buffer case, the dynamics of such a network can be described in terms of iterate of random piecewise affine maps, or geometrically as a billiards in the euclidean space with as many dimensions as the number of flow classes and as many reflection facets as there are routers. this class of billiards exhibits both periodic and nonperiodic asymptotic oscillations, the characteristics of which are extremely sensitive to the parameters of the network. it is also shown that for large populations and in the presence of synchronization, aggregated throughputs exhibit fluctuations that are due to the network as a whole, that follow some complex fractal patterns, and that come on top of other and more classical flow or packet level fluctuations. the consequences on tcp's fairness are exemplified on a few typical cases of small dimension.
adaptive real-time group multicast. this paper shows how to provide an adaptive real-time group multicast (many-to-many) communication service. such a service can be used by applications, like audio/video tele-conferencing, that require low loss, and bounded delay and jitter. in order to meet deterministic quality of service (qos) requirements of a real-time group multicast, some communication resources are reserved. in this work we show (i) how bandwidth is reserved for each group, and (ii) how an active user in a multicast group can dynamically share, in an efficient and fair manner, the bandwidth allocated to its group.quality of service support for a real-time multicast group is based on time driven priority. in this scheme the time is divided into time frames of fixed duration and all the time frames are aligned by using a global time reference which can be obtained from gps (global positioning system). bandwidth is allocated to a multicast group as a whole, rather than individually to each user. the allocation is done by reserving time intervals within time frames in some periodic fashion.this sort of allocation raises two problems that are studied in this paper: (1) scheduling: how time intervals are reserved to each multicast group, and (2) adaptive sharing: how the participants dynamically share the time intervals that have been reserved for their multicast group. the proposed approach is based on embedding multiple virtual rings, one for each multicast group. by using the virtual rings it is simple to route messages to all the participants, while minimizing the bound on the buffer sizes and queuing delays.
radio link admission algorithms for wireless networks with power control and active link quality protection. presents a distributed power control scheme, which maintains the signal/interference ratios (sirs) of operational (active) links above their required thresholds at all times (link quality protection), while new users are being admitted; furthermore, when new users cannot be successfully admitted, existing ones do not suffer fluctuations of their sirs below their required thresholds values. the authors also present two admission/rejection control algorithms, which exercise voluntary drop-out of links inadmissible to the network so as to reduce interference and possibly facilitate the admission of other links.
heuristic algorithms for constructing near-optimal structures of linear multihop lightwave networks. the goal of the study described is to exploit the capabilities of emerging lightwave technology and the fact that the ieee 802.6 man is a linear network, to construct near optimal linear multihop lightwave networks. heuristic algorithms are proposed for constructing photonic implementations of near optimal distributed queue dual bus (dqdb) structures. two sets of heuristic optimization algorithms are formulated. the first set is concerned with minimizing the maximum flow in any link in the network, while the second set of heuristics is aimed at minimizing the network-wide mean packet delay. important properties of these algorithms are analyzed and their performance is demonstrated with several representative numerical examples
a procedure to evaluate the mean transport time in multibuffer deflection-routing networks with nonuniform traffic. the use of independence assumptions has made it possible to derive an approximate model of deflection-routing networks that have multibuffer stations and two-connected topologies. a procedure is presented for estimating the mean transport time (and throughput) of these networks, even when the offered traffic is nonuniform. the proposed procedure is efficient and yields very accurate results, as comparisons with simulations have confirmed. the model is quite general and can be applied to deflection-routing networks that deflect packets according to destination-based priorities. the authors have modeled only a few of the several options for designing a deflection-routing network. in particular, they have modeled a network with no user input buffers, a specific admission-routed policy, and destination-based priorities
quad tree: a cost-effective fault-tolerant multistage interconnection network. a new class of irregular fault-tolerant multistage interconnection networks named quad tree (qt) networks is proposed and analyzed. the network can achieve significant tolerance to faults and good performance with relatively low costs and a simple control scheme. the construction procedure of the qt network is described. algorithms for allocation of path length and routing along with the routing procedure are proposed. the fault-tolerance aspect is described, and the cost-effectiveness of the qt network is discussed
mobile users: to uptdate or not to update? tracking strategies for mobile users in wireless networks are studied. in order to save the cost of using the wireless links mobile users should not update their location whenever they cross boundaries of adjacent cells. this paper focuses on three natural strategies in which the mobile users make the decisions when and where to update: the time-based strategy, the number of movements-based strategy, and the distance-based strategy. we consider both memoryless movement patterns and movements with markovian memory along a topology of cells arranged as a ring. we analyze the performance of each one of the three strategies under such movements, and show the performance differences between the strategies.