waashk/dblp huggingface dataset:
collision avoidance and resolution multiple access with transmission groups. the carma-ntg protocol is presented and analyzed. carma-ntg dynamically divides the channel into cycles of variable length; each cycle consists of a contention period and a group-transmission period. during the contention period, a station with one or more packets to send competes for the right to be added to the group of stations allowed to transmit data without collisions; this is done using a collision resolution splitting algorithm based on a request-to-send/clear-to-send (rts/cts) message exchange with non-persistent carrier sensing. carma-ntg ensures that one station is added to the group transmission period if one or more stations send requests to be added in the previous contention period. the group-transmission period is a variable-length train of packets, which are transmitted by stations that have been added to the group by successfully completing an rts/cts message exchange in previous contention periods. as long as a station maintains its position in the group, it is able to transmit data packets without collision. an upper bound is derived for the average costs of obtaining the first success in the splitting algorithm. this bound is then applied to the computation of the average channel utilization in a fully connected network with a large number of stations. these results indicate that collision resolution is a powerful mechanism in combination with floor acquisition and group allocation multiple access.
distributed routing with labeled distances. the author presents, verifies, and analyzes a new routing algorithm called the labeled distance-vector routing algorithm (ldr), that is loop-free at every instant, eliminates the counting-to-infinity problem of the distributed bellman-ford (dbf) algorithm, operates with arbitrary link and node delays, and provides shortest paths a finite time after the occurrence of an arbitrary sequence of topological changes. in contrast to previous successful approaches to loop-free routing, ldr maintains dbf's row-independence property and does not require internodal coordination spanning multiple loops. the new algorithm is shown to be loop-free and to converge in a finite time after an arbitrary sequence of topological changes. its performance is compared with the performance of other distributed routing algorithms
a loop-free path-finding algorithm: specification, verification and complexity. the loop-free path-finding algorithm (lpa) is presented. lpa specifies the second-to-last hop and distance to each destination to ensure termination; in addition, it uses an inter-neighbor synchronization mechanism to eliminate temporary loops. a detailed proof of lpa's correctness is presented and its complexity is evaluated. lpa's average performance is compared by simulation with the performance of algorithms representative of the state of the art in distributed routing, namely an ideal link-state (ils) algorithm and a loop free algorithm that is based on internodal coordination spanning multiple hops (dual). the simulation results show that lpa is a more scalable alternative than dual and ils in terms of the average number of steps, messages, and operations needed for each algorithm to converge after a topology change. lpa is shown to achieve loop freedom at every instant without much additional overhead over that incurred by prior algorithms based on second-to-last hop and distance information.
a comparison of bandwidth smoothing techniques for the transmission of prerecorded compressed video. the transfer of prerecorded, compressed video requires multimedia services to support large fluctuations in band width requirements on multiple time scales. bandwidth smoothing techniques can reduce the burstiness of a variable-bit-rate stream by prefetching data at a series of fixed rates, simplifying the allocation of resources in video servers and the communication network. given a fixed client-side prefetch buffer, several bandwidth smoothing algorithms have been introduced that are provably optimal under certain constraints. this paper presents a collection of metrics for comparing these smoothing algorithms and evaluating their cost-performance trade-offs. due to the scarcity of available trace data, we have constructed a video capture testbed and generated a collection of twenty full-length, motion-jpeg encoded video clips. using these video traces and a range of client buffer sizes, we investi gate the interplay between the performance metrics through simulation experiments. the results highlight the unique strengths and weaknesses of each algorithm.
an overload cycle analysis of generalized bandwidth balancing for dqdb. a novel state-space approach is used to characterize the overload cycle behavior of a generalized bandwidth balancing (bwb) scheme for the distributed queue dual bus (dqdb) multiple access procedure. the author exploits the fact that each node and the bus can be modeled by a finite state machine and will have cycles in the state diagram. the cycles of interest are referred to as overload cycles and result when one or more nodes are simultaneously trying to access the bus as quickly as possible. the author determines the overload cycle invariants imposed by bwb and generalizes bwb to be any integral relationship between used and skipped empty segments. it is shown that the ordinary access-based priorities cannot work, without some additional cycle invariants, in a system employing bandwidth balancing since it is impossible to preclude service to an upstream low priority mode and generalized bwb is suggested as an alternative method for obtaining rate-based priority grades of service
v-net: a framework for a versatile network architecture to support real-time communication performance guarantees. the paper proposes a new network architecture, called the versatile network architecture (v-net), which provides a framework for flexible support of communication requirements in real-time networks. applications communicate over the v-net by using simplex end-to-end network connections which support specific real-time and reliability characteristics tailored to meet the application's specified requirements. v-net differs from other proposed architectures in that it does not assume one specific packet scheduling algorithm or a specific traffic policing mechanism. instead, the v-net has been designed to support a variety of packet scheduling algorithms and traffic policing mechanisms. this flexibility is an important design consideration as a real-time network architecture must accommodate existing and future multimedia applications.
usage of vsat for tcp/ip based lan interconnection. an analysis of the possibilities of usage of vsat networks for the interconnection of tcp/ip based lans is performed. in the first part of the paper, a general feasibility overview of tcp/ip through satellite is presented, stressing on the inconveniences and technical problems of arrangement. in the second part, a comparative study between low rate (up to 19.2 kbps) vsat networks and other low capacity data networks (such as x.25) is carried out. the study is based upon measurements performed by telefonica i+d on the hughes isbn vsat system operated by telefonica de espana.
rate-function scheduling. rate-function scheduling (rfs) is a new deadline-based packet-scheduling service discipline that supports quality-of-service guarantees for applications with real-time communication requirements. rfs is distinguished from other service disciplines in that it achieves all of the following goals: analytically-derived performance bounds, performance isolation among sessions, flexible and efficient allocation of bandwidth, implementation simplicity, work-conserving operation, and bandwidth-fair operation (defined in the paper). through the specification of rate functions, sessions can control their bandwidth usage and their upper bounds on delay. for a class of rate functions, which we show is sufficient for providing sessions with delay bounds, rfs is as simple to implement and to calculate service bounds such as zhang's virtualclock service discipline. we also show that the non-preemptive earliest deadline first policy is a simple degeneration of rfs.
on-line routing for permanent virtural circuits. the paper considers the problem of routing a set of permanent virtual circuit requests over a backbone network. several factors make this routing problem complicated. routing decisions must be made on-line without any knowledge of future request sets. furthermore, frequent rerouting to correct inefficiencies that can result from the on-line routing decisions is not possible since rerouting creates a service disruption for the customer. finally, the forward and reverse bandwidth of a virtual circuit must be routed over the same single path. using an extensive set of simulations, the paper evaluates several different strategies for on-line permanent virtual circuit routing. the authors find that a strategy based on results in competitive analysis and ideas from combinatorial optimization consistently provides the best performance. the problem of admission control is closely related to the problem of routing. the paper also provides a theoretical lower bound that suggests that non-greedy admission control is a fundamental component of an efficient on-line permanent virtual circuit routing algorithm.
virtual-topology adaptation for wdm mesh networks under dynamic traffic. we present a new approach to the virtual-topology reconfiguration problem for a wavelength-division-multiplexing-based optical wide-area mesh network under dynamic traffic demand. by utilizing the measured internet backbone traffic characteristics, we propose an adaptation mechanism to follow the changes in traffic without a priori knowledge of the future traffic pattern. our work differs from most previous studies on this subject which redesign the virtual topology according to an expected (or known) traffic pattern, and then modify the connectivity to reach the target topology. the key idea of our approach is to adapt the underlying optical connectivity by measuring the actual traffic load on lightpaths continuously (periodically based on a measurement period) and reacting promptly to the load imbalances caused by fluctuations on the traffic, by either adding or deleting one or more lightpath at a time. when a load imbalance is encountered, it is corrected either by tearing down a lightpath that is lightly loaded or by setting up a new lightpath when congestion occurs. we introduce high and low watermark parameters on lightpath loads to detect any over- or underutilized lightpath, and to trigger an adaptation step. we formulate an optimization problem which determines whether or not to add or delete lightpaths at the end of a measurement period, one lightpath at a time, as well as which lightpath to add or delete. this optimization problem turns out to be a mixed-integer linear program. simulation experiments employing the adaptation algorithm on realistic network scenarios reveal interesting effects of the various system parameters (high and low watermarks, length of the measurement period, etc.). specifically, we find that this method adapts very well to the changes in the offered traffic.
lexicographically optimal balanced networks. we consider the problem of allocating bandwidth between two endpoints of a backbone network so that no parts of the network are unnecessarily loaded. we formulate the problem as lexicographic optimization and develop algorithms for its solution. the solution consists of: 1) identifying a cut in the network where the optimal load can be determined on all the links of the cut and 2) considering the same problem for each of the subnetworks to which the cut is dividing the original network.
exact and efficient analysis of schedulability in fixed-packet networks: a generic approach. a general model for trafic flows on packet-switched, virtual-circuit based, fixed-packet networks is intro- duced, and an exact schedulability test is obtained for systems of such flows. rules are derived that make the evaluation of this schedulability test feasible and eficient under certain circumstances. the practical relevance of this approach is demonstrated by applying it to a number of standard trafic models.
network algorithms and protocol for multimedia servers. in this paper, we present a network service specifically designed for multimedia servers. by coupling a histogram-based traffic characterization with an admission control algorithm, it enables the network to provide heterogeneous statistical qos guarantees to clients. to meet these guarantees, we propose an overload control algorithm and protocol that exploits the regularity and predictability in traffic to provide heterogeneous qos while completely eliminating packet losses in the network. specifically, it: (1) detects congestion in the network prior to its occurrence, (2) allocates bandwidth to competing sources based on their qos guarantees, and (3) transmits feedback packets to the sources indicating the rate allocations. by ensuring that the feedback is received by the sources sufficiently prior to overload occurrence, the protocol enables the sources to employ application specific procedures to adjust their transmission rates so as to conform to the rate allocations, thereby eliminating any packet losses in the network. the key contribution of our protocol lies in combining open-loop and feedback-based control to: (1) provide heterogeneous qos to clients in networking environments consisting of switches that may not have any scheduling support; and (2) migrate the functionality of discarding packets, in the event of congestion, to the sources which understand the semantics of the data. the protocol is efficient, makes very few assumptions about the underlying network, is realizable on current switching hardware (supporting fcfs scheduling), and is completely integrated with the architecture of a multimedia server.
a reliable, adaptive network protocol for video transport. in this paper, we present an adaptive network layer protocol that: (1) minimizes buffer requirement in the network while guaranteeing that packets of vbr encoded video flows will not be lost, and (2) minimizes end-to-end delay and jitter of frames. to achieve the former objective, we utilize receiver-oriented adaptive credit-based flow control algorithm, and derive necessary and sufficient number of buffers that should be reserved for ensuring its reliability. to minimize the end-to-end delay and jitter for vbr encoded video streams, we: (1) present bandwidth estimation techniques which exploit the structure of the video traffic, and (2) define a new fairness criteria for buffer allocation (which is motivated by the delay requirements of video applications) and then present a fair buffer allocation algorithm. to mask the effects of delay jitter on playback continuity, we present a simple technique for adapting the playback point at client sites. we experimentally evaluate this protocol for a wide range of parameters and many network configuration and demonstrate its adaptability. we also compare the performance of the protocol with numerous other schemes and demonstrate its suitability for video transport.
fault tolerant pon topologies. the authors propose a redundant, tree structured passive optical network (pon) configuration which can withstand all single and most double link failures. the redundant configuration results from the superposition of two physically separate, diverse-routed trees. this redundancy is transparent to the user. it does not require switching elements or special controls inside the network. it permits easy identification of the fault by the network control center. the fault tolerance properties of the proposed solution are evaluated. power budget, fiber installation cost, and metropolitan coverage issues are investigated
vbr video over atm: reducing network resource requirements through endsystem traffic shaping. transmission of variable-bitrate (vbr) video over atm is a challenge because it combines the requirement for on-time data delivery with a bursty traffic characteristic. we focus on the role of atm endsystems in the transmission of vbr video and examine how traffic shaping in the sender reduces the burstiness of the video stream and therefore the network resource requirements, both for video encoded in real-time and stored video. shapers based on multiple leaky buckets are popular because they are particularly simple to implement. we present basic results on their buffer requirements and provide new, tighter bounds for their output traffic, enabling efficient resource allocation as well as a significant reduction in the number of leaky buckets required. we extend the basic shaping mechanism to provide efficient shaping for stored video. finally we compare empirically the performance of multiple leaky bucket shaping with an optimal algorithm for mpeg-1 encoded video and find under realistic conditions near-optimal performance with very few leaky buckets.
protocols for an optical star interconnect for high speed mesh networks. optical networks can provide higher throughputs while high speed electronic networks possess the intelligence for network control and management. we present a two level high speed network architecture that combines the throughput advantage of optical networks and the intelligence of electronic processing. one level is a high speed mesh lan which uses wormhole routing, source routing and hop-by-hop flow control mechanisms with mesh routers (asynchronous pipelined crossbar switches) to provide a high speed electronic network. the second level is an optical star network interconnecting high speed mesh networks distributed across metropolitan area distances. we obtain analytical expressions for the average message (worm) delays for the gtdm (group time division multiplexing) multi-access protocol (which includes as special cases tdm and das) for single-hop packet switching in the optical network of such an architecture. we use a two state discrete time markov chain to model the arrival of messages to the optical network. results for both uniform traffic and non-uniform traffic are presented. finally, a modified dynamic allocation scheme is presented for single-hop packet switching which handles the message as a unit rather than sending a message as several fixed sized packets.
lan/man interconnection to atm: a simulation study. the authors compare three strategies, namely, reservation, on-the-fly, and hybrid, for the support of connectionless internet traffic on asynchronous transfer mode (atm). the comparison is based on a simulation experiment in which a mix of virtual paths (some carrying connectionless traffic, some carrying connection-oriented traffic) are multiplexed on a 150 mb/s trunk, called the bottleneck trunk. results based on a variety of measures (cell and burst loss rates, cell delay, and burst delay) show that the on-the-fly approach, which aggressively exploits unused bandwidth, is superior to the reservation scheme, which is handicapped by the renegotiation overhead and the conservative usage of bandwidth. the hybrid scheme exhibits a performance behavior between the other two. this is a bit disappointing, considering the fact that the hybrid scheme is expected to be consistently better than both schemes. still the hybrid scheme offers some interesting features (e.g. lower delays for the background traffic) which should be further explored by a more extensive examination of the working parameters
analysis of alternating-priority queueing models with (cross) correlated switchover times. this paper analyzes a single server queueing system in which service is alternated between two queues and the server requires a (finite) switchover time to switch from one queue to the other. the distinction from classical results is that the sequence of switchover times from each of the queues need not be i.i.d. nor independent from each other; each sequence is merely required to form a stationary ergodic sequence. with the help of stochastic recursive equations explicit expressions are derived for a number of performance measures, most notably for the average delay of a customer and the average queue lengths under different service disciplines. with these expressions a comparison is made between the service disciplines and the influence of correlation is studied. finally, through a number of examples it is shown that the correlation can significantly increase the mean delay and the average queue lengths indicating that the correlation between switchover times should not be ignored. this has important implications for communication systems in which a common communication channel is shared amongst various users and where the time between consecutive data transfers is correlated (for example in ad-hoc networks). in addition to this a number of notational mistakes in well-known existing literature are pointed out.
dynamic maintenance of the virtual path layout. discusses methods for adjusting the layout of virtual paths in an atm network, to the dynamics of changes in the usage of the network by its end-users. the authors first present a centralized algorithm for finding a better layout for the current traffic pattern, and for applying the change in the network, and discuss its drawbacks. they then present a distributed algorithm that emulates the centralized algorithm with a much lower overhead, and enhanced durability to faults. they prove that both algorithms produce identical layouts, thus showing the superiority of the latter algorithm. both algorithms base the changes in the network on a new rerouting protocol, which does not cause any losses in data, nor changes in the fifo order of cells.
seam: scalable and efficient atm multicast. this paper proposes a multipoint-to-multipoint multicast architecture for atm networks. the necessity for such an architecture stems from the scalability requirements, both in terms of state to be maintained in the network and in terms of the group population dynamics, of a wide range of networking applications. we argue that approaches of using multicast servers or meshes of point-to-multipoint virtual circuits (vcs) may be inadequate solutions to this problem. we propose a true multipoint-to-multipoint architecture called seam, which uses a single vc for a multicast group consisting of multiple senders and receivers. we achieve this without changes to atm's aal5. seam relies on an additional switching feature we call cut-through forwarding, which enables the mapping of several incoming vcs into outgoing vcs. we believe that seam is both an important and necessary step in the evolution of atm. it will enable applications relying on group multicast to benefit directly from atm's quality of service support and scalable bandwidth and the resulting performance advantages. also, it considerably simplifies the problem of supporting ip multicast over large atm networks.
queueing analysis of a distributed explicit rate allocation algorithm for abr services. approximate queueing analysis of a distributed explicit rate allocation algorithm for the flow control of available bit rate (abr) service, which captures the effect of bandwidth-delay, is described. attention is focused on bounding the worst case transient queueing behaviour in a strictly-abr environment with persistent start-up sources. at each switch, rm cells are enqueued using a buffer separate from the data cells, and are served with a higher priority than data cells. both single and multiple node network cases are treated for connections with differing delays. the approximate analysis shows relatively good agreement with simulation results for single node networks, but gives looser estimates for the multiple node case.