waashk/dblp huggingface dataset:
atomic resource sharing in noncooperative networks. in noncooperative networks, resources are shared among selfish users, which optimize their individual performance measure. we consider the generic and practically important case of atomic resource sharing, in which traffic bifurcation is not implemented, hence each user allocates its whole traffic to one of the network resources. we analyze topologies of parallel resources within a game-theoretic framework and establish several fundamental properties. we prove the existence of and convergence to a nash equilibrium. for a broad class of residual capacity performance functions, an upper bound on the number of iterations till convergence is derived. an algorithm is presented for testing the uniqueness of the equilibrium. sufficient conditions for achieving a feasible equilibrium are obtained. we consider extensions to general network topologies. in particular, we show that, for a class of throughput-oriented cost functions, existence of and convergence to a nash equilibrium is guaranteed in all topologies. with these structural results at hand, we establish the foundations of a design and management methodology, that enables to operate such networks efficiently, in spite of the lack of cooperation among users and the restrictions imposed by atomic resource sharing.
stability in atm networks. in this paper, we address the issues of stability in atm networks. a network is stable if and only if all the packets have a bounded delay. we first consider atm networks with fcfs scheduling policy. we then study networks with priority driven scheduling policy. for each network, we develop criteria for testing the stability of an atm network and methods of deriving delay bounds in a stable network. in previous work, the cruz-gallager-parekh ring has been a ``benchmark" architecture to study the stability problem. for example, gallager and parekh claimed that the ring with size no more than four switches is stable when the total utilization of the links is less than 100%. we validated this result. furthermore, we find that a ring with large number of switches is stable if the total utilization of the links is less than or equal to 73\%.
asynchronous multimedia multihop wireless networks. personal communications and mobile computing will require a wireless network infrastructure which is fast deployable, possibly multihop, and capable of multimedia service support. the first infracture of this type was the packet radio network (prnet), developed in the 70's to address the battlefield and disaster recovery communication requirements. prnet was totally asynchronous and was based on a completely distributed architecture. it handled datagram traffic reasonably well, but did not offer efficient multimedia support. recently, under the wamis and glomo arpa programs several mobile, multimedia, multihop (m/sup 3/) wireless network architectures have been developed, which assume some form of synchronous, time division infrastructure. the synchronous time frame leads to efficient multimedia support implementations. however, it introduces more complexity and is less robust in the face of mobility and channel fading. in this paper; we examine the impact of synchronization on wireless m/sup 3/ network performance. first, we introduce maca/pr, an asynchronous network based on the collision avoidance mac scheme employed in the ieee 802.11 standard. there, we evaluate and compare several wireless packet networks ranging from the total asynchronous prnet to the synchronized cluster tdma network. we examine the tradeoffs between time synchronization and performance in various traffic and mobility environments.
channel carrying: a novel handoff scheme for mobile cellular networks. we present a new scheme that addresses the call handoff problem in mobile cellular networks. efficiently solving the handoff problem is important for guaranteeing quality of service (qos) to already admitted calls in the network. our scheme is based on a new concept called channel carrying: when a mobile user moves from one cell to another, under certain mobility conditions, the user is allowed to carry its current channel. we propose a new channel assignment scheme to ensure that this movement of channels will not lead to any extra co-channel interference or channel locking. in our scheme, the mobility of the channels relies entirely on localized information, and no global coordination is required. therefore, the scheme is simple and easy to implement. we further develop a hybrid channel carrying scheme that allows us to maximize the performance under various constraints. we provide numerical results comparing our scheme with the traditional channel reservation techniques. we find that our scheme outperforms the reservation scheme over a broad range of traffic parameters.
a service with bounded degradation in quality-of-service networks. many network applications that require quality-of-service (qos) support, such as transmission of digital voice and video, tolerate a certain level of service degradation. in this study, a novel network service, referred to as service with bounded degradation (bd service), is presented that can take advantage of the delay tolerance of applications. different from previous proposals for similar services, the bd service can guarantee hard lower bounds of the service degradation. this is achieved by strictly limiting the amount of traffic that is subject to service degradation. to implement a bd service, network traffic is partitioned into components with different delay requirements. policing of the traffic components is achieved by multi-level leaky buckets. a novel scheduler, referred to as edd-bd (earliest deadline due-bounded degradation) scheduler, performs switching of packets. properties of the edd-bd scheduler are presented and analyzed.
statistical per-flow service bounds in a network with aggregate provisioning. scalability concerns of qos implementations have stipulated service architectures where qos is not provisioned separately to each flow, but instead to aggregates of flows. this paper determines stochastic bounds for the service experienced by a single flow when resources are managed for aggregates of flows and when the scheduling algorithms used in the network are not known. using a recently developed statistical network calculus, per-flow bounds can be calculated for backlog, delay, and the burstiness of output traffic.
a general packet replication scheme for mutlicasting in interconnection networks. multicasting in broadband packet switches and metropolitan networks can be achieved by first replicating the packets and then routing them to their destinations. this paper studies a very simple but general replication scheme that can be applied to arbitrary interconnection-network topologies. the replication process of a packet adapts itself according to the network topology and the traffic condition. hot spots of replication activities are diffused by this scheme which automatically moves part of the replication efforts to less active network regions. the scheme can potentially be used in networks (e.g., the manhattan-street network) in which multicasting were thought to be inherently difficult. fundamental issues and critical problem areas are laid out, and solutions addressing them are proposed. the performance of the replication algorithm and its implementation (logic diagram level) in the shuffle-exchange copy network are investigated in detail. it is found that the performance of the algorithm improves with the increase of network dimensions.
analysis of an atm buffer with self-similar ("fractal") input traffic. as atm high-speed, cell-relay networks will most likely first make their impact as backbones interconnecting enterprise networks consisting of ethernet and other lans, their proper design and control is crucial. recent studies of high quality, high resolution traffic measurements in bellcore ethernets have revealed that this aggregate ethernet traffic is self-similar ("fractal") in nature, quite different in "burstiness" features from traffic considered and studied up to now. this paper presents an analytical study of an atm buffer driven with self-similar traffic. the probability of buffer occupancy is obtained. it is shown that this probability decreases with the buffer size not exponentially, as in traditionally markovian traffic models, but algebraically.
performance and complexity of multicast cross-path atm switches. a newly proposed large-scale atm switch called cross-path switch has been shown to be capable of handling unicast and multirate traffic efficiently. in this paper, we will study two replication approaches to enhance the switch to support multicast switching. the first approach replicates multicast cells at both input and output stages, while the second one replicates cells at the input stage only. a feasible configuration for each scheme is considered and the effect of multicast traffic on the switch performance in terms of throughput and cell loss probability is studied. we observed that, to achieve the same throughput and loss requirement, the second architecture may require fewer switching elements than the first one.
key to the success of asynchronous transfer mode: an application programming interface. asynchronous transfer mode (atm) networks are scalable via a wide variety of physical link speeds and can be run in both local and wide area. bandwidth reservation and quality of service guarantees make atm attractive to deliver multimedia information in real-time. existing protocol suites can be extended. however, they do not give access to those characteristics. therefore, applications demand an atm application programming interface (api) to take advantage of those features. this paper covers a special syntax mapping of the atm api services on top of x/open transport interface (xti) which is able to give applications access directly to the special quality and trafic services of an atm network. a particular realization of the api on xti environment is proposed and implemented on the macos networking platform. it provides a flexible and modular design of the atm networking. finally, the paper concludes with one atm-aware application (video on demand) which requires real-time streaming data.
an optimization based approach for qos routing in high-bandwidth networks. in this paper, we propose an optimization-based approach for quality of service (qos) routing in high-bandwidth networks. we view a network that employs qos routing as an entity that distributively optimizes some global utility function. by solving the optimization problem, the network is driven to an efficient operating point. in earlier work, it has been shown that when the capacity of the network is large, this optimization takes on a simple form, and once the solution to this optimization problem is found, simple proportional qos routing schemes will suffice. however, this optimization problem requires global information. we develop a distributed and adaptive algorithm that can efficiently solve the optimization online. compared with existing qos routing schemes, the proposed optimization-based approach has the following advantages: 1) the computation and communication overhead can be greatly reduced without sacrificing performance; 2) the operating characteristics of the network can be analytically studied; and 3) the desired operating point can be tuned by choosing appropriate utility functions.
pcup: pipelined cyclic upstream protocol over hybrid fiber coax. in order to span nii (national information infrastructure) into the homes, the community cable tv networks have to be re-engineered to support two-way interactive services. in this work, we propose pcup (pipelined cyclic upstream protocol) as the upstream mac (medium access control) protocol for hfc (hybrid fiber coax) community access network. pcup is designed with the intention of pipelining the upstream channel. this is achieved by proper station positioning, which measures the station propagation offset from the headend, and transmission scheduling, which assigns each station the transmission starting time and duration in a cycle. by taking into account the propagation offsets and the transmission times, transmitted cells can appear back-to-back, i.e. pipelined, at the headend. since only the active stations are scheduled to transmit in a cycle, a membership control mechanism, which runs a contention-based tree walk algorithm, is executed periodically to allow the stations to join or leave.
flexible storage placement of digital video media. in addition to the large data size requirement and real-time constraint in continuous media, future video applications such as video editing demands the flexible storage placement and the random access capability on the video-frame level. to offer efficient buffering schemes and flexible storage placement for supporting random access, we present two buffering schemes: the two-buffer scheme and the k-buffer compensation scheme. the two-buffer scheme requires only all the frames in a block to be stored consecutively while providing random access between blocks. however, this intuitive buffering scheme potentially requires a large block size and buffer space. the k-buffer compensation scheme is proposed to resolve this large buffer space requirement by using more than two buffers and requiring a minimal number of blocks randomly placed in each cylinder. experimental measurement results reveal the significant improvements on the buffer-size reduction and placement flexibility by using the k-buffer compensation scheme.
a study of networks simulation efficiency: fluid simulation vs. packet-level simulation. network performance evaluation through traditional packet-level simulation is becoming increasingly difficult as today''s networks grow in scale along many dimensions. as a consequence, fluid simulation has been proposed to cope with the size and complexity of such systems. this study focuses on analyzing and comparing the relative efficiencies of fluid simulation and packet-level simulation for several network scenarios. we use the ``simulation event'''' rate to measure the computational effort of the simulators and show that this measure is both adequate and accurate. for some scenarios, we derive analytical results for the simulation event rate and identify the major factors that contribute to the simulation event rate. among these factors, the ``ripple effect'''' is very important since it can significantly increase the fluid simulation event rate. for a tandem queueing system, we identify the boundary condition to establish regions where one simulation paradigm is more efficient than the other. flow aggregation is considered as a technique to reduce the impact of the ``ripple effect'''' in fluid simulation. we also show that wfq scheduling discipline can limit the ``ripple effect'''', making fluid simulation particularly well suited for wfq models. our results show that tradeoffs between parameters of a network model determines the most efficient simulation approach.
approximating optimal spare capacity allocation by successive survivable routing. the design of survivable mesh based communication networks has received considerable attention in recent years. one task is to route backup paths and allocate spare capacity in the network to guarantee seamless communications services survivable to a set of failure scenarios. this is a complex multi-constraint optimization problem, called the spare capacity allocation (sca) problem. this paper unravels the sca problem structure using a matrix-based model, and develops a fast and efficient approximation algorithm, termed successive survivable routing (ssr). first, per-flow spare capacity sharing is captured by a spare provision matrix (spm) method. the spm matrix has a dimension the number of failure scenarios by the number of links. it is used by each demand to route the backup path and share spare capacity with other backup paths. next, based on a special link metric calculated from spm, ssr iteratively routes/updates backup paths in order to minimize the cost of total spare capacity. a backup path can be further updated as long as it is not carrying any traffic. furthermore, the spm method and ssr algorithm are generalized from protecting all single link failures to any arbitrary link failures such as those generated by shared risk link groups or all single node failures. numerical results comparing several sca algorithms show that ssr has the best trade-off between solution optimality and computation speed.
optimal partition of qos requirements on unicast paths and multicast trees. we investigate the problem of optimal resource allocation for end-to-end qos requirements on unicast paths and multicast trees. specifically, we consider a framework in which resource allocation is based on local qos requirements at each network link, and associated with each link is a cost function that increases with the severity of the qos requirement. accordingly, the problem that we address is how to partition an end-to-end qos requirement into local requirements, such that the overall cost is minimized. we establish efficient (polynomial) solutions for both unicast and multicast connections. these results provide the required foundations for the corresponding qos routing schemes, which identify either paths or trees that lead to minimal overall cost. in addition, we show that our framework provides better tools for coping with other fundamental multicast problems, such as dynamic tree maintenance.
an algorithm to compute collusion paths. in earlier work we have formulated a collusion problem that determines whether it is possible for a set of colluders to collectively discover a target set of information, starting from their initial knowledge, and have presented a complete solution for a special case of the problem. in this paper we present an algorithm that solves the general case. given a collusion problem the algorithm determines whether it has a solution, and if it does, computes one. a solution to the collusion problem is a method with which the colluders can uncover the hidden information. communications protocols that employ cryptographic techniques are increasingly used to protect privacy as well as to communicate. a cryptographic protocol defines a process by which information is transferred among some users while hidden from others. the algorithm presented here can be used to determine whether a subset of protocol users can discover, during or after the protocol's execution, the information that is designed to be hidden from them.
document marking and identification using both line and word shifting. continues a study of document marking to deter illicit dissemination. an experiment performed reveals that the distortion on the photocopy of a document is very different in the vertical and horizontal directions. this leads to the strategy that marks a text line both vertically using line shifting and horizontally using word shifting. a line that is marked is always accompanied by two unmarked control lines one above and one below. they are used to measure distortions in the vertical and horizontal directions in order to decide whether line or word shift should be detected. line shifts are detected using a centroid method that bases its decision on the relative distance of line centroids. word shifts are detected using a correlation method that treats a profile as a waveform and decides whether it originated from a waveform whose middle block has been shifted left or right. the maximum likelihood detectors for both methods are given.
smds measurements and modeling to predict performance. the authors describe a performance study of a trial switched multimegabit data service (smds) link (intended for inter-lan connection) from the perspective of customers evaluating the feasibility of the link for some target applications. the goals were to take all measurements on the customer premises and to develop a methodology general enough to be used by customers to evaluate the link. the authors measured a lightly loaded system and developed a model of the smds connection suitable for evaluating applications via analysis or simulation. they document their methodology and present the smds connection delay values as well as a likely breakdown of the constituents of that delay. they used these data to create a simulation model and to simulate a simple application. in the trial configuration, where geographical distances were small, smds network delay was one of the notable components of end-to-end delay in the smds connection. however, for most packets, throughput is limited by the t1 capacity for transmitting smds cells, not by the smds network capacity
unified power control, error correction coding and scheduling for a cdma downlink system. transmitting multimedia data over a cdma channel presents a new set of challenges. sometimes, data demands will exceed the system capacity, in which case the system must make the most efficient use of its limited resources. the resources we consider are: fixed bandwidth available for each user and the transmit power budget for each cell. in this paper, we present our approach for unifying power control, variable forward error correction (vfec), and scheduling for a downlink system by allocating the system resources. our objective is to maximize the overall system satisfaction, which we call &ldquo;system utility&rdquo;. this objective is achieved by applying a distributed algorithm which divides the overall optimization problem into a hierarchy of three levels (system, cell and user). at each level, the system performs independent and parallel optimizations; the critical information is then passed to the higher level for further optimization. finally, an iterative and distributed algorithm is applied at the system level to achieve the overall system optimization.
adaptive hodling policies for ip over atm networks. next generation wide area networks will be connection-oriented, with data-link layer connectivity being provided by asynchronous transfer mode (atm). for the huge existing investment in current ip networks such as the internet to remain useful, one must devise mechanisms to carry ip traffic over atm networks. a fundamental issue is to devise holding policies for virtual circuits carrying datagrams. the authors consider two pricing schemes, the first is a likely pricing scheme of future atm networks, while the second is based on characteristics of current networks. for each pricing scheme, the authors devise a simple holding policy that adapts to the characteristics of the ip traffic. the authors simulate their policies on actual network traffic and find that they perform significantly better than previous policies.
an empirical model of http network traffic. the workload of the global internet is dominated by the hypertext transfer protocol (http), an application protocol used by world wide web clients and servers. simulation studies of ip networks will require a model of the traffic patterns of the world wide web, in order to investigate the effects of this increasingly popular application. we have developed an empirical model of network traffic produced by http. instead of relying on server or client logs, our approach is based on packet traces of http conversations. through traffic analysis, we have determined statistics and distributions for higher-level quantities such as the size of http files, the number of files per "web page", and user browsing behavior. these quantities form a model can then be used by simulations to mimic world wide web network applications.