Browsing by Author "Tripathi, Satish K."
Now showing 1 - 15 of 15
Results Per Page
Sort Options
Item Carry-Over Round Robin: A Simple Cell Scheduling Mechaniasm for ATM Networks(1998-10-15) Saha, Debanjan; Mukherjee, Sarit; Tripathi, Satish K.We propose a simple cell scheduling mechanism for ATM networks. The proposed mechanism, named Carry-Over Round Robin (CORR), is an extension of weighted round robin scheduling. We show that albeit its simplicity, CORR achieves tight bounds on end-to-end delay and near perfect fairness. Using a variety of video traffic traces we show that CORR often outperforms some of the more complex scheduling disciplines such as Packet-by-Packet Generalized Processor Sharing (PGPS). (Also cross-referenced as UMIACS-TR-96-45)Item Estimating End-to-End Cell Delay Variation in ATM Networks(1998-10-15) Korpeoglu, Ibrahim; Tripathi, Satish K.; Chen, XiaoqiangCell delay variation (CDV) is one of the quality of service parameters that can be negotiated between applications and an ATM network. The network should check during connection setup, as part of call admission control, whether it can satisfy the requested CDV of an application. For this comparison, the network should estimate the end-to-end CDV that it can support, by using local information about cell delays and delay variations in switches. An accurate estimation of the end-to-end CDV is important for decreasing call-blocking probability and increasing network utilization. In this article, we will first describe, evaluate, and identify the short-comings of three proposed methods for end-to-end CDV estimation. Then we will present a new method based on Chernoff bound and compare it to the other methods. The Chernoff method is promising since it has good accuracy and applicability under current signalling support for ATM networks. (Also cross-referenced as UMIACS-TR-97-27)Item ETempo: A Clock Synchronization Algorithm for Hierarchical LANs - Implementation and Measurements.(1986) Tripathi, Satish K.; Chang, Shu-jen H.; ISRThe Tempo clock synchronization algorithm is extended for hierarchical LANs. An implementation of the new algorithm, ETempo, is presented. Because of the unavailability of a two- level hierarchical LAN, it is emulated using a single LAN. The simulation procedures and other design issues are discussed. Behavior of ETempo is measured for a variety of parametric values.Item Exploiting the Temporal Structure of MPEG Video for the Reduction of Bandwidth Requirements(1998-10-15) Krunz, Marwan; Tripathi, Satish K.We propose a new bandwidth allocation scheme for VBR video traffic in ATM networks. The scheme is tailored to MPEG-coded video sources that require stringent and deterministic quality-of-service guarantees. By exploiting the temporal structure of MPEG sources, we show that our scheme results in an effective bandwidth which, in most cases, is less than the source peak rate. The reduction in the bandwidth requirement is achieved without sacrificing any perceived QoS. Efficient procedures are provided for the computation of the effective bandwidth under heterogeneous MPEG sources. The effective bandwidth strongly depends on the arrangement of the multiplexed streams which is a measure of the degree of synchronization between the GOP patterns of different streams. Assuming that all possible arrangements are equi-probable, we derive an expression for the asymptotic tail distribution of the effective bandwidth. From the tail distribution, we compute several performance measures for the call blocking probability when the allocation is made based on the effective bandwidth. In the case of homogeneous sources, we give a closed-form expression for the `best' arrangement that results in the `optimal' effective bandwidth. Numerical examples based on real MPEG traces are used to demonstrate the advantages of our scheme. (Also cross-referenced as UMIACS-TR-96-29)Item Impact of Synchronization on the Allocation of Bandwidth for Multiplexed MPEG Streams(1998-10-15) Krunz, Marwan; Tripathi, Satish K.In an MPEG encoder, three types of frames (I, P. and B) are periodically generated according to a pre-specified compression pattern. As a result, an MPEG sequence is periodic in its compression pattern, and this periodicity can be used to reduce the bandwidth requirements of multiplexed MPEG streams. By exploiting the deterministic and periodic nature of the compression pattern, we show that it is possible to provide stringent deterministic guarantees (no cell losses and no queueing delay) to MPEG connections without the need to allocate the peak rates of individual sources. Instead, a stream is allocated its effective bandwidth, which is the aggregate peak rate of the multiplexed streams divided by the number of streams. The aggregate peak rate depends on the arrangement of the multiplexed streams which is a measure of the degree of synchronization among the compression patterns of different streams. It is found that in most cases, the effective bandwidth is smaller than the source peak rate. For a given arrangement, we provide a procedure to compute the effective bandwidth. We also give an expression for the 'best' arrangement that results in the 'optimal' effective bandwidth. Examples of real MPEG sequences are used to show the bandwidth gains that can be achieved through proper scheduling of the starting times of MPEG connections. (Also cross-referenced as UMIACS-TR-95-120)Item Improving NFS Performance over Wireless Links(1998-10-15) Dube, Rohit; Rais, Cynthia D.; Tripathi, Satish K.NFS is a widely used remote file access protocol that has been tuned to perform well on traditional LANs which exhibit low error rates. Users migrating to mobile-hosts would like to continue to use NFS for remote file accesses. However, low bandwidth and high error-rates degrade performance on mobile-hosts using wireless links thus hindering the use of NFS. In this paper, we present two mechanisms to improve NFS performance over wireless links : an aggressive NFS client and link-level retransmissions. Our experiments show that these mechanisms improve throughput by up to 200%, which brings the performance to within 5% of that obtained in zero error conditions. (Also cross-referenced as UMIACS-TR-95-126)Item Measuring NFS Performance in Wireless Networks(1998-10-15) Rais, Cynthia D.; Tripathi, Satish K.Technological trends suggest that soon communication networks will consist of a high speed wired backbone with numerous wireless Local Area Networks. Mobile computing and wireless subnetworks are increasingly in demand. Mobile routing solutions provide wireless LANs with seamless connectivity to backbone wired systems. However, these solutions do not provide acceptable performance. Wireless networks have distinct transmission characteristics which present challenges to achieving efficient performance. Performance over wireless links is limited by high error rates, mobility, and low bandwidth. We have studied the performance of TCP and NFS over a wireless network. The prevalence of these protocols means that mobile hosts will frequently use them when communicating with stationary hosts. Measurements have been collected to determine the response of these protocols in the presence of various error patterns. These measurements show that NFS and TCP performance suffer extreme degradation due to these wireless link characteristics. Unexpectedly, NFS performance is not better than an TCP FTP file transfer. NFS performance over wireless links is limited by large packet sizes, long retransmission timeouts, and slow response to losses. Our goal is to understand the effects of wireless communication on these protocols and improve performance without requiring changes to the current network Infrastructure. (Also cross-referenced as UMIACS-TR-95-125)Item Modeling Bit Rate Variations in MPEG Sources(1998-10-15) Krunz, Marwan; Tripathi, Satish K.In this paper, we propose a traffic model for the characterization of VBR MPEG-coded video streams. This model provides the means to generate synthetic MPEG streams that can be used in performance studies of ATM networks. The model is appropriately fitted to three long empirical video sequences taken from different movies. We use multiple components to model bit rate variations in an MPEG stream. These components have different time scales. Long-term variations in the bit rate are captured at the scene level. Within a scene, the sizes of I frames tend to slightly fluctuate around some average. Hence, we measure the activity of the scene by the average size of I frames in that scene. This average varies from one scene to another, and its randomness is reasonably approximated by a lognormal distribution. For a given scene, the fluctuations of the sizes of I frames about- their mean are modeled as an AR(2) time series. Finally, we show that the sizes of P and B frames can be appropriately fitted by lognormal distributions, with corresponding parameters. Using the compression pattern, the complete frame size sequence is formed by intermixing three subsequences, each of which describes the frame size sequence for a particular frame type. The validity of the model is demonstrated by the similarity between a synthetic stream and an actual trace, in terms of the correlation structure, the marginal distribution, the sample paths, and more importantly, the queueing performance. (Also cross-referenced as UMIACS-TR-95-120)Item Multiprocessor Priority Ceiling Based Protocols(1998-10-15) Chen, Chia-Mei; Tripathi, Satish K.We study resource synchronization in multiprocessor hard real-time systems. Specifically, we propose a multiprocessor resource control protocol which allows a job to simultaneously lock multiple global resources, removing a restriction from previous protocols. Allowing nested critical sections may permit a finer granularity of synchronization, increasing parallelism and throughput. All the protocols discussed belong to the class of priority inheritance protocols and rely in some fashion on priority ceilings for global semaphores. We consider both static and dynamic priorities, building upon the multiprocessor priority ceiling protocol (MPCP) proposed by Rajkumar et al. and the dynamic priority ceiling protocol (DPCP) proposed by Chen and Lin. The extended protocols prevent deadlock and transitive blocking. We derive bounds for worse case blocking time, and describe sufficient conditions to guarantee that m sets of periodic tasks can be scheduled on an rn multiprocessor system. Performance comparisons of these protocols with MPCP shows that the proposed protocols increase schedulability. (Also cross-referenced as UMIACS-TR-94-42)Item Multirate Scheduling of VBR Video Traffic in ATM Networks(1998-10-15) Saha, Debanjan; Mukherjee, Sarit; Tripathi, Satish K.(Also cross-referenced as UMIACS-TR-96-44)Item Network Layer Mobility: an Architecture and Survey(1998-10-15) Bhagwat, Pravin; Tripathi, Satish K.; Perkins, CharlesIn this paper we explore various network layer concepts that pertain to the design of mobile networking systems. We show that mobility is essentially an {\em address translation} problem and is best resolved at the network layer. We have identified the fundamental services that must be supported at the network layer to carry out the task of address translation. Using these service primitives as building blocks, we propose a network layer architecture which enables smooth integration of mobile end systems within the existing Internet. The architecture is modularized into well-defined logical components. In this paper our objective is not to propose {\em a specific scheme} for supporting mobility, rather it is to highlight and analyze the essential aspects of supporting mobile end-systems, as well as to better understand the trade-off between various design alternatives. (Also cross-referenced as UMIACS-TR-95-117)Item Parallel and Distributed Simulation of Discrete Event Systems(1998-10-15) Ferscha, Alois; Tripathi, Satish K.The achievements attained in accelerating the simulation of the dynamics of complex discrete event systems using parallel or distributed multiprocessing environments are comprehensively presented. While parallel discrete event simulation (DES) governs the evolution of the system over simulated time in an iterative SIMD way, distributed DES tries to spatially decompose the event structure underlying the system, and executes event occurrences in spatial subregions by logical processes (LPs) usually assigned to different (physical) processing elements. Synchronization protocols are necessary in this approach to avoid timing inconsistencies and to guarantee the preservation of event causalities across LPs. Included in the survey are discussions on the sources and levels of parallelism, synchronous vs. asynchronous simulation and principles of LP simulation. In the context of conservative LP simulation (Chandy/Misra/Bryant) deadlock avoidance and deadlock detection/recovery strategies, Conservative Time Windows and the Carrier Nullmessage protocol are presented. Related to optimistic LP simulation (Time Warp), Optimistic Time Windows, memory management, GVT computation, probabilistic optimism control and adaptive schemes are investigated. (Also cross-referenced as UMIACS-TR-94-100)Item Reducing Router-Crossings in a Mobile Intranet(1998-10-15) Dube, Rohit; Korpeoglu, Ibrahim; Tripathi, Satish K.Current general purpose mobility solutions like Mobile-IP involve multiple router-crossings even when the mobile host moves within an intranet from one subnet of a router to another. An environment consisting of a large number of mobile hosts would congest the router causing hosts to experience high latency and jitter. This paper presents a mechanism to eliminate multiple router-crossings in a mobile intranet, which reduces the load on the routers and the hand-off and data latency at the mobile hosts. (Also cross-referenced as UMIACS-TR-97-01)Item Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks(1998-10-15) Dube, Rohit; Rais, Cynthia D.; Wang, Kuang-Yeh; Tripathi, Satish K.Unlike static networks, ad-hoc networks have no spatial hierarchy and suffer from frequent link failures which prevent mobile hosts from using traditional routing schemes. Under these conditions, mobile hosts must find routes to destinations without the use of designated routers and also must dynamically adapt the routes to the current link conditions. This paper proposes a distributed adaptive routing protocol for finding and maintaining stable routes based on signal strength and location stability in an ad-hoc network and presents an architecture for its implementation. (Also cross-referenced as UMIACS-TR-96-34)Item Writing an Efficient Device Driver for a Multimedia Teleconferencing System(1998-10-15) Sarris, Alexander; Tripathi, Satish K.Modern high speed networks, such as ATM, can provide the bandwidth and the QoS guarantees to demanding real-time multimedia applications. However, overall performance of a networked multimedia application will greatly depend on the in-host data movement. Analyzing the characteristics and requirements of those applications, we came to several conclusions about the operation of the multimedia devices' drivers. We applied these conclusions in the design and implementation of a device driver for a multimedia teleconferencing system, based on IBM RS/6000 servers, running the AIX 3.2 operating system. Tracing the complete in-host data path, we found that though our device driver minimized the movement of data between the teleconferencing card and user main memory, the UDP/IP stack proved to be a cause of delay in the movement of data between user main memory and the network interface. (Also cross-referenced as UMIACS-TR-96-18)