waashk/dblp huggingface dataset:
layered multicast recovery. we study the problem of localizing repair packets when packets are lost. when repair packets are multicasted, a highly lossy receiver may swamp the entire multicast ``group'''' with duplicate repair packets thereby wasting bandwidth; thus, the protocols need repair locality. we present a multicast layering scheme where the sender proactively distributes fec repair packets among multiple multicast groups. receivers can selectively tune in to a subset of these multicast groups to obtain number of packets close to the number they require. we develop an efficient algorithm that dynamically determines the optimal distribution of fec repair packets to a given (small constant) number of multicast groups. the running time of this algorithm is independent of the number of receivers in the multicast session, and is hence highly scalable. however, the optimal algorithm requires the knowledge of the fec repair requirements of all the receivers in the multicast group, and hence is subject to the implosion problem. to handle the implosion problem, we develop a heuristic algorithm that achieves repair locality very similar to that of the optimal algorithm, but does not require as much global knowledge. our multicast layering scheme can be integrated into many known reliable multicast protocols to enhance their scalability. for concreteness, we focus on singly scoped and hierarchically scoped srm as well as tree-based protocols and present combined protocols incorporating our solutions into each of them. our simulation experiments suggest that our solutions can substantially enhance the scalability of these reliable multicast protocols.
design of logical topologies for wavelength-routed all-optical networks. this paper considers the problem of designing a logical topology over a wavelength-routed all-optical network physical topology. the physical topology consists of the nodes and fiber links in the network. on an all-optical network physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics. the set of lightpaths along with the nodes constitutes the logical topology. for a given network physical topology and traffic pattern (relative traffic distribution among the source-destination pairs), our objective is to design the logical topology and the routing algorithm on that topology so as to maximize the network throughput while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology). we will see that ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays. on the other hand, in all our examples, imposing it results in a minimal reduction in throughput. while the number of wavelengths required to imbed the resulting logical topology on the physical all-optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small. we formulate the combined logical topology design and routing problem described above (ignoring the constraint on the number of available wavelengths) as a mixed integer programming problem which we then solve for a number of cases of a 6-node network. since this programming problem is computationally intractable for larger networks, we split it into two subproblems: logical topology design, which is computationally hard and will probably require heuristic algorithms, and routing, which can be solved by a linear program. we then compare the performance of two heuristic topology design algorithms (that do take wavelength assignment constraints into account) against that of randomly generated topologies.
minimizing the number of optical amplifiers needed to support a multi-wavelength optical lan/man. optical networks based on passive star couplers and employing wavelength-division multiplexing (wdm) have been proposed for deployment in local and metropolitan areas. amplifiers are required in such networks to compensate for the power losses due to splitting and attenuation. however, an optical amplifier has constraints on the maximum gain and the maximum output power it can supply; thus optical amplifier placement becomes a challenging problem. the general problem of minimizing the total amplifier count, subject to the device constraints, is a mixed-integer non-linear problem. previous studies have attacked the amplifier-placement problem by adding the ``artificial'' constraint that all wavelengths, which are present at a particular point in a fiber, be at the same power level. in this paper, we present a method to solve the minimum-amplifier-placement problem while avoiding the equally-powered-wavelength constraint. we demonstrate that, by allowing signals to operate at different power levels, our method can reduce the number of amplifiers required in several small to medium-sized networks.
improving reliable multicast using active parity encoding services (apes). traditional reliable multicast protocols for the internet require large amounts of bandwidth to support reliable delivery of data to numerous receivers. in this paper, we propose and evaluate novel protocols that combine active repair service (a.k.a. local recovery) and parity encoding (a.k.a. forward error correction or fec) techniques. we show that compared to other repair service protocols, our protocols require less buffer inside the network, and maintain the low bandwidth requirements of previously proposed repair service / fec combination protocols. our protocols also reduce the amount of fec processing at repair servers, moving more of this processing to the end-hosts. last, we examine repair service / fec combination protocols in an environment where loss rates are different across domains within the network. we find that in such environments, repair services are more effective than fec at reducing bandwidth utilization. furthermore, adding fec to a repair services protocol not only reduces buffer requirements at repair servers, but also reduces bandwidth utilization in domains with high loss, or in domains with large populations of receivers.
the effect of bottleneck service rate variations on the performance of the abr flow control. one of the main features of abr services is the employment of a rate-based flow control mechanism. feedback from the network switches to the end systems gives users the information necessary to adjust their transmission rates appropriately according to the current network load. this type of control has been investigated to some extent, assuming a constant transmission capacity on a bottleneck link.in this paper we develop a discrete-time analysis to study the effect of bottleneck service rate variations on the performance of the abr flow control mechanism. looking at real systems, such variations occur on the one hand due to the establishment and release of atm connections and on the other hand due to the varying bandwidth demand of vbr connections. to model the rate variations, the bottleneck service rate is assumed to follow a general probability density function.
the converging flows problem: an analytical study. when multiple systems are interconnected through a high-speed backbone network and communicate without resource reservation, under certain conditions a severe overload can appear at the destination system. this problem, called the converging flows problem, can be alleviated by use of a feedback control mechanism that coordinates the emission of the sources. the authors present a dynamic resource management mechanism that both controls the losses at the congested node and attempts to optimize resource utilization. in fact it steers the entire system into a desirable operating regime. they study analytically the behavior of the system under such a control and show that it can be reduced with a few approximations to a well-known physical system. this allows to infer optimal values for the parameters of the command algorithm, and the authors show that these values have a natural physical meaning to the system.
performance of congestion control mechanisms in wormhole routing networks. in order to minimize latency in high-speed interconnection networks, the wormhole routing technique can be employed. with this technique, a switch transmits an incoming message as soon as it receives it, without waiting for the entire message. the problem then is that a message stretches over several links and locks network resources, thus making a contention situation possible. two principal congestion control mechanisms can be considered, backpressure flow control and deflection routing. the performance of these mechanisms depends both on the traffic characteristics and on the network topology. in order to compare them, we study analytically the behavior of a wormhole routing network model with random input traffic under both policies. we estimate the probability of collision between messages and express the average message transit delay as a function of the offered load. simulation provides a good confirmation for the analytical results. this study gives us an understanding of the behavior of the system under different resource management policies.
a linear control approach to explicit rate feedback in atm networks. rate-based feedback congestion control has been proposed as a form of traffic management for available bit rate traffic in atm networks. this paper discusses applying linear control theory to these algorithms. a congestion control scheme for simple networks is designed and analyzed using the tools of classical control theory. this allows insight into the trade-offs in such schemes and suggests approaches to larger networks.
paging cost minimization under delay constraints. efficient paging procedures help minimize the amount of bandwidth expended in locating a mobile unit. given a probability distribution on user location, the optimal paging strategy which minimized the expected number of locations polled e[l] is to query each location sequentially in order of decreasing probability. however, since sequential search over many locations may impose unacceptable polling delay, d, optimal paging subject to delay constraints is considered. substantial reductions in e[l] can be had even after moderate constraints are imposed on acceptable d (i.e., d/spl les/3) since all methods of mobility management eventually reduce to considering a time-varying probability distribution on user location, this work should be applicable to a wide range of problems in the area. most notably those with additive cost structures.
multicast routing with end-to-end delay and delay variation constraints. we study the problem of constructing multicast tree to meet the quality of service requirements of real-time, interactive applications operating in high-speed packet-switched environments. in particular, we assume that multicast communication depends on (a) bounded delay along the paths from the source to each destination, and (b) bounded variation among the delays along these paths. we first establish that the problem of determining such a constrained tree is np-complete. we then derive heuristics that demonstrate good average case behavior in terms of the maximum inter-destination delay variation of the final tree. in addition, our heuristics achieve their best performance under conditions typical of multicast scenarios in high-speed networks. we also show that it is possible to dynamically reorganize the initial tree in response to changes in the destination set, in a way that is minimally disruptive to the multicast session.
topology identification for traffic and configuration management in dynamic networks. the authors address the problem of identifying the topology of a network from data collected at a designated node (possibly one of the network nodes). the data considered are descriptions of the local neighborhood about each node, which specify the identities of the node and of its neighbors. these data are neither required to be correct nor complete. the authors propose a model that describes and relates the network topology and the data. they define costs associated with this model, and reduce the identification problem to a combinational optimization problem with and an objective function based on these costs. a pseudo-polynomial-time algorithm is derived, which yields a local minimum of the objective function. the local minimum appears to be a reasonable solution, as shown by a range of examples
automatic alarm correlation for fault identification. in communication networks, a large number of alarms exist to signal any abnormal behavior of the network. as network faults typically result in a number of alarms, correlating these different alarms and identifying their source is a major problem in fault management. the alarm correlation problem is of major practical significance. alarms that have not been correlated may not only lead to significant misdirected efforts, based on insufficient information, but may cause multiple corrective actions (possibly contradictory) as each alert is handled independently. the paper proposes a general framework to solve the alarm correlation problem. the authors introduce a new model for faults and alarms based on probabilistic finite state machines. they propose two algorithms. the first one acquires the fault models starting from possibly incomplete and incorrect date. the second one correlates alarms in the presence of multiple faults and noisy information. both algorithms have polynomial time complexity, use an extension of the viterbi algorithm to deal with the corrupted data, and can be implemented in hardware. as an example, they are applied to analyse faults using data generated by the ans (advanced network and services, inc.)/nsf t3 network.
delay analysis for forward signaling channels in wireless cellular network. we consider connection-oriented wireless cellular networks. such second generation systems are circuit-switched digital networks which employ dedicated radio channels for the transmission of signaling information. a forward signaling channel is a common signaling channel assigned to carry the multiplexed stream of paging and channel-allocation packets from a base station to the mobile stations. similarly, for atm wireless networks, paging and virtual-circuit-allocation packets are multiplexed across the forward signaling channels as part of the virtual-circuit set-up phase. the delay levels experienced by paging and channel-allocation packets are critical factors in determining the efficient utilization of the limited radio channel capacity. a multiplexing scheme operating in a &ldquo;slotted mode&rdquo; can lead to reduced power consumption at the handsets, but may in turn induce an increase in packet delays. in this paper, focusing on forward signaling channels, we present schemes for multiplexing paging and channel-allocation packets across these channels, based on channelization plans, access priority assignments and paging group arrangements. for such multiplexing schemes, we develop analytical methods for the calculation of the delay characteristics exhibited by paging and channel-allocation packets. the resulting models and formulas provide for the design and analysis of forward signaling channels for wireless network systems.
an all-optical wavelength-division meshed-ring packet-switching network. introduces an all-optical wavelength-division packet-switching meshed-ring local/metropolitan area communication network. this architecture, known as smartnet (scalable multi-channel adaptable ring terabit network), allows the proposed network to offer a significant increase in the throughput capacity realized by any local/metropolitan area shared-medium network. the smartnet architecture is atm capable and fits naturally with, and takes best advantage of, the kinds of high speed optoelectronic and optical components that can actually be constructed. for certain meshed-ring regular physical topologies, an upper bound on the network's throughput efficiency is derived. specific network configurations are demonstrated which achieve a throughput efficiency level which is close to 90% of this bound. such network structures exhibit a throughput capacity level which is 80% higher than that realized by traditional (non-meshed) ring networks.
resource reservation in advance in heterogeneous networks with partial atm infrastructures. resource reservation in advance (rera) enables scheduling and allocation of resources at an early stage in time. this way, the availability of resources can actually be guaranteed for the point in time when the resources are needed. as opposed to that, current reservation protocols such as rsvp perform an "immediate" reservation without advance scheduling. they can therefore suffer shortage of resources with subsequent rejection of applications.this paper describes our new approach for providing resource reservation in advance in atm networks. as a foundation, we first present experiences of ipng and rsvp over atm. based on this work, we then discuss major design issues of an appropriate rera solution. important aspects are the signaling model for rera, the admission control strategy, the duration of connections, and various other time-related parameters. we also discuss our ongoing implementation of rera as an extension of rsvp and outline directions for future research in this area.
measuring the performance of parallel message-based process architectures. message-based process architectures are widely regarded as an effective method for structuring parallel protocol processing on shared memory multi-processor platforms. a message-based process architecture binds one or more processing elements with data messages and control messages received from applications and network interfaces. in this architecture, parallelism is achieved by simultaneously escorting multiple messages on separate processing elements through a stack of protocol tasks. the paper reports performance results from empirical comparisons of a connection-oriented tcp/ip protocol stack implemented using two different parallel message-based process architectures. these performance experiments measure the throughput, context switching, and synchronization exhibited by the two process architectures on a shared memory multi-processor platform. the experimental results demonstrate the extent to which the selection of a parallel process architecture affects protocol stack performance.
a performance evaluation of connectionless overlay networks for atm. introducing the asynchronous transfer mode (atm) causes a backwards compatibility problem, because atm is connection-oriented whereas most of today's lans are connectionless. interconnection can be achieved by the use of connectionless servers (cls). these servers together with a number of preestablished virtual circuits form a connectionless overlay network on top of atm. in this paper we evaluate overlay networks that differ in number, location and interconnection of clss by computation of mean cell delay and link load.
a study on the inaccessibility characteristics of iso 8802/4 token-bus lans. continuity of service and bounded and known message delivery latency are requirements of a number of applications, which are imperfectly fulfilled by standard lans. most previous studies have addressed this issue by computing worst-case access/transmission delays only for normal lan operation. however, lans are subject to failures, namely partitions. since most applications can live with temporary glitches in lan operation, an alternative approach is to quantify all these glitches or temporary partitions, called inaccessibilities, and to derive a worst-case figure, to be added to the worst-case transmission delay in the absence of faults. in these conditions, reliable real-time operation is possible on nonreplicated lans. an exhaustive study of the inaccessibility characteristics of the iso 8802/4 token-bus lan is described
power control and time division: the cdma versus tdma question. for wireless networks, time division multiple access (tdma) offers certain well-known advantages over methods such as spread spectrum code division (cdma). foremost among them is the guarantee that other users will not interfere during a node's dedicated time slots. for this desirable isolation, the cost is synchronization. viewing arbitrary time intervals as potential tdma time slots, we ask whether it is possible to obtain some of the benefit of time division without incurring the synchronization cost. in particular, we address the question of whether a tdma-like state can be induced on asynchronous channels in such a way as to reduce interference and energy consumption. through analysis and simulation we find conditions under which it is desirable to use time division. we then show how autonomous power management may be used as a mechanism to induce a form of time division. in this context a backlog-sensitive power management system is presented.
reliable multi-user tree setup with local identifiers. a protocol for setting up a tree connection for the purpose of multicast communication over a high-speed packet switched network is presented. the tree connection is based on the use of local identifiers, which are swapped at every intermediate node of the tree. local identifiers are simple to manage, provide fast access to the routing tables, and are very efficient in terms of the size of the resulting routing space. the authors consider a high-speed network in which the local label swapping on data messages is performed in hardware by the switching subsystem, while the connection set-up is done in software by the switch control subsystem. a reliable protocol for setting up the tree connection is presented, and its correctness is formally proved. the protocol ensures the integrity of the tree and when failures occur, it is gracefully degraded into a smaller tree
efficient qos routing. we consider the problem of routing in a network where quality of service constraints are placed on network traffic. we provide two optimal algorithms that are based on determining the discontinuities of functions related to the optimization at hand. the proposed algorithms have pseudopolynomial worst case running time and for a wide variety of tested networks they have fairly satisfactory running times. they perform significantly better than the algorithm based on the direct application of the dynamic programming equations and can also be used in conjunction with known polynomial-time approximation algorithms to provide good average case behavior, in addition to guaranteeing polymonial worst-case running time.