Routing with multiple QoS requirements for supporting multimedia applications

Distributed multimedia applications usually require multiple QoS performance guarantees. However, in general, searching such a route in the network, to support multimedia applications, is known to be NPcomplete. In this paper, we propose a new heuristic QoS routing algorithm, called QoSR_DKS, for supporting multimedia applications in highspeed networks. QoSR_DKS is a modification of rulebased Fallback routing and Dijkstra algorithms. It can search a unicast route that would have enough network resources so that multiple QoS requirements (bandwidth, delay, and delay jitter) of the requested flow could be guaranteed. Its worst case computation time complexity is the same as that of the Dijkstra algorithm, i.e., O(V²), where V is the number of nodes in the network. Extensive simulations were done with various network sizes, upto 500 nodes networks, where each node uses Weighted Fair Queueing (WFQ) service discipline. Results show that QoSR_DKS is very efficient. It could always find the QoS satisfying route, whenever there exists one (success rate is optimal), and its average computation time is near to simple shortest path Dijkstra algorithm.     

Incorporating QoS into IP Enterprise Network Design

Recent trends in enterprise networks are radically changing the composition of these systems. Instead of having diverse data networks, each of which is dedicated to a single class of applications, corporations are moving to a unified IP (Internet Protocol) Intranet. Traffic demands on these Intranets include delay-sensitive traffic that requires better than the standard best effort service provided by IP networks. As a result, various new technologies and strategies to provide end-to-end Quality of Service (QoS) within IP enterprise networks are being developed and implemented. However, current IP network design methodologies are limited in that they can only design networks providing best effort service or else, a single delay constraint for all traffic. In this paper, we discuss a new design methodology for IP enterprise networks that takes into account the new technologies and techniques that can provide QoS. In particular, we identify and discuss the most crucial design issues that must be addressed when specialized queuing-based QoS strategies are used in the network. We describe the new constraints introduced by the underlying technologies and discuss how these factors affect the formulation of the IP Enterprise Network Design Problem. We then describe some specific features and methodologies that have been incorporated into a network design-planning tool for IP enterprise networks with QoS.     

Surface-Photovoltage Measurement of Volume Electron Lifetime in p-Si Wafers

The problem of estimating the volume lifetime _v of minority carriers in p-type Si wafers by surface-photovoltage measurements is addressed. An experiment is conducted in order to ascertain the relationship between measured and actual values of _v. The measurements are carried out on circular specimens whose thickness is reduced from about 2000 to 450 m by stepwise etching. The specimens are cut from a Czochralski-grown rod, their actual values of _v ranging from 10 to 300 s. The surface recombination rate of minority carriers is determined on both sides of the specimens covered with native oxide, the sides differing in surface finish. The results of the experiment allow one to determine _v up to about 400 s.     

Mobile ATM buffer capacity analysis

This paper extends a stochastic theory for buffer fill distribution for multiple on and off sources to a mobile environment. Queue fill distribution is described by a set of differential equations assuming sources alternate asynchronously between exponentially distributed periods in on and off states. This paper includes the probabilities that mobile sources have links to a given queue. The sources represent mobile user nodes, and the queue represents the capacity of a switch. This paper presents a method of analysis which uses mobile parameters such as speed, call rates per unit area, cell area, and call duration and determines queue fill distribution at the ATM cell level. The analytic results are compared with simulation results.This paper is partially funded by ARPA contract number J-FBI-94-223.The Mathematica code for this paper can be found on http://www.tisl.ukans.edu/sbush.     

Floor acquisition multiple access (FAMA) in single‐channel wireless networks

The FAMANCS protocol is introduced for wireless LANs and adhoc networks that are based on a single channel and asynchronous transmissions (i.e., no time slotting). FAMANCS (for floor acquisition multiple access with nonpersistent carrier sensing) guarantees that a single sender is able to send data packets free of collisions to a given receiver at any given time. FAMANCS is based on a threeway handshake between sender and receiver in which the sender uses nonpersistent carrier sensing to transmit a requesttosend (RTS) and the receiver sends a cleartosend (CTS) that lasts much longer than the RTS to serve as a busy tone that forces all hidden nodes to back off long enough to allow a collisionfree data packet to arrive at the receiver. It is shown that carrier sensing is needed to support collisionfree transmissions in the presence of hidden terminals when nodes transmit RTSs asynchronously. The throughput of FAMANCS is analyzed for singlechannel networks with and without hidden terminals; the analysis shows that FAMANCS performs better than ALOHA, CSMA, and all prior proposals based on collision avoidance dialogues (e.g., MACA, MACAW, and IEEE 802.11 DFWMAC) in the presence of hidden terminals. Simulation experiments are used to confirm the analytical results.     

Microsystems Engineering: A Great Stride Forward in Microelectronics Technology

The development of new-generation technological and engineering concepts by the example of microsystems technology and microsystems engineering approaches is considered.     

A pattern classification proposal for object‐oriented audio coding in MPEG‐4

The future MPEG4 standard will adopt an objectoriented encoding strategy whereby an audio source is encoded at a very low bitrate by adapting a suitable coding scheme to the local characteristics of the signal. One of the most delicate issues in this approach is that the overall performance of the audio encoder greatly depends on the accuracy with which the input signal is classified. This paper shows that the difficult problem of audio classification for objectoriented coding can be effectively solved by selecting a salient set of acoustic parameters and adopting a fuzzy model for each audio object, obtained by a soft computinghybrid learning tool. The audio classifier proposed operates at two levels: recognition of the class to which the input signal belongs (talkspurt, music, noise, signaling tones) and then recognition of the subclass to which it belongs. The results obtained show that fuzzy logic is a valid alternative to the matching techniques of a traditional pattern recognition approach.     

QoS Supporting Algorithms for Optical Internet Based on Optical Burst Switching

In this paper, we propose a protocol architecture and quality of service (QoS) supporting algorithms for optical Internet based on optical burst switching (OBS) technology. Firstly, the function of each layer of the protocol architecture and the formats of control packets are defined in order to adopt GMPLS to the control plane of OBS. Then, the offset time decision (OTD) algorithm to cooperate with the proposed protocol architecture is designed for optical Internet. A new burst loss formula taking into account the effect of offset time is introduced to design the OTD algorithm. This algorithm can decide on the appropriate priority-offset time according to the required QoS by using the reversed equation of the so-called heuristic loss formula (HLF) which is approximated as a proportional equation of our new loss formula. Finally, we propose a CAC algorithm based on the OTD algorithm for the purpose of increasing the availability of wavelength resources and supporting the QoS of established connections in optical Internet. The performance of the proposed algorithms is evaluated in terms of burst loss rate and the number of connections through simulation.     

Simulation‐based performance evaluation of routing protocols for mobile ad hoc networks

In this paper we evaluate several routing protocols for mobile, wireless, ad hoc networks via packetlevel simulations. The ad hoc networks are multihop wireless networks with dynamically changing network connectivity owing to mobility. The protocol suite includes several routing protocols specifically designed for ad hoc routing, as well as more traditional protocols, such as link state and distance vector, used for dynamic networks. Performance is evaluated with respect to fraction of packets delivered, endtoend delay, and routing load for a given traffic and mobility model. Both small (30 nodes) and medium sized (60 nodes) networks are used. It is observed that the new generation of ondemand routing protocols use much lower routing load, especially with small number of peertopeer conversations. However, the traditional link state and distance vector protocols provide, in general, better packet delivery and endtoend delay performance.     

Gaussian radial basis functions and inner product spaces

An approximation result is given concerning Gaussian radial basis functions in a general inner product space. Applications are described concerning the classification of the elements of disjoint sets of signals, and also the approximation of continuous real functions defined on all of ⁿ using radial basis function (RBF) networks. More specifically, it is shown that an important large class of classification problems involving signals can be solved using a structure consisting of only a generalized RBF network followed by a quantizer. It is also shown that Gaussian radial basis functions defined on ⁿ can uniformly approximate arbitrarily well over all of ⁿ any continuous real functionalf on ⁿ that meets the condition that |f(x)|0 as x.     

The Satchel system architecture: Mobile access to documents and services

Mobile professionals require access to documents and documentrelated services, such as printing, wherever they may be. They may also wish to give documents to colleagues electronically, as easily as with paper, facetoface, and with similar security characteristics. The Satchel system provides such capabilities in the form of a mobile browser, implemented on a device that professional people would be likely to carry anyway, such as a pager or mobile phone. Printing may be performed on any Satchelenabled printer, or any fax machine. Scanning, too, may be accomplished at any Satchelenabled scanner. Access rights to individual documents may be safely distributed, without regard to document formats. Access to document services is greatly simplified by the use of context sensitivity. The system has been extensively tested and evaluated. This paper describes the architecture of the Satchel system.     

Differentiated Wavelength Assignment with QoS Recovery for DWDM Next Generation Internet Backbone Networks

This paper describes a differentiated wavelength assignment strategy for the appropriate allocation of wavelengths on wavelength-routed quality of service (QoS) routes with differentiated QoS class and recovery capabilities. The paper is based on the differentiated MPS services (DMS) model as a framework for optical bandwidth management and the real time provisioning of optical channels in re-configurable transport networks. MPS stands for multi protocol lambda switching which is a functional part of GMPLS (generalized MPLS). We discuss here a QoS recovery scheme at the optical layer, at the MPS layer, and at the IP layer, as related to QoS failure caused by device failures or attack-induced faults in dense-wavelength division multiplexing (DWDM) transport networks. According to the QoS characteristics of wavelength in optical links and the type of used optical cross-connect (OXC) nodes, a differentiated wavelength assignment strategy that considers QoS recovery capability is also described. We point out important problems that should be resolved in the DMS model for optical QoS routing with differentiated wavelength assignment.     

On the design of feedback controllers to achieve prescribed initial value constraints

The problem of designing a stabilizing compensator for a control system to achieve prescribed initial value constraints ⁽ⁱ⁾(0⁺)=y_i is considered. Indeed, modulo certain technical conditions, such a compensator exists if and only if y_i=0;i= 0,1,...,rp +rt –2; whererp is the relative degree of the plant andrt is the relative degree of the system input. This theorem is derived and a complete parameterization of the set of compensators that achieve the prescribed design constraints is formulated.This research was supported in part by NSF Grant No. 921106.     

The discrete Einstein relation

In this paper the connection between massM, resistance and commute time for random walks on graphs is further explored, and the relation=2M · is proved. An extension of the result is made to multigraphs, which are an extension of the graph concept where a black box is treated like an edge.     

An adaptive algorithm for optimizing the packet size used in wireless ARQ protocols

We develop an algorithm that allows an ARQ protocol to dynamically optimize the packet size based on estimates of the channel biterrorrate. Our algorithm is particularly useful for wireless and satellite channels where the biterrorrates tend to be relatively high and time variable. Our algorithm uses the acknowledgment history to make estimates of the channel biterrorrate, based on which the optimal packet size can be chosen. We develop a Markov chain model for the analysis of the system, under static channel conditions, and show that the algorithm can achieve close to optimal performance using a history of just 10,000 bits. We also use the Gilbert–Elliott twostate Markov channel to model dynamic channel conditions. We show, through simulation, that the algorithm performs well even under rapidly changing channel conditions. Finally, we discuss a maximum likelihood approach for choosing the packet size, which performs almost optimally but is much easier to implement.     

Symmetry relations in multidimensional Fourier transform pairs

A relation between the types of symmetries that exist in signal and Fourier transform domain representations is derived for continuous as well as discrete domain signals. The symmetry is expressed by a set of parameters, and the relations derived in this paper will help to find the parameters of a symmetry in the signal or transform domain resulting from a given symmetry in the transform or signal domain respectively. A duality among the relations governing the conversion of the parameters of symmetry in the two domains is also brought to light. The application of the relations is illustrated by a number of two-dimensional examples.Notation R the set of real numbers - R ^m R × R × ... × R m-dimensional real vector space - continuous domain real vector - L {¦ – _i , i = 1,2,..., m} - m-dimensional frequency vector - W { – _i ,i=1,2,..., m} - m-dimensional normalized frequency vector - _P {¦ – _i , i=1,2,...,m} - g(ol) g (₁,₂,..., _m ) continuous domain signal - () ( _{1 2},..., _m )=G (j ₁,j ₂,..., j _m ) Fourier transform ofg (ol) - (A,b,,,) parameters ofT- symmetry - N the set of integers - N ^m N × N × ... × N m-dimensional integer vector spacem-dimensional lattice - h(n) h (n ₁,.,n _m ) discrete domain signal - H() Fourier transform ofh (n) - v ₁,v ₂,..., v_m m sample-direction and interval vectors - V (v ₁ v ₂ ...v _m ) sampling basis matrix - [x]^* complex conjugate ofx - detA determinant ofA - X {x¦ – x _i , i=1,2,..., m} - A ^–t [A ^–1] ^t ,t stands for transpose This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-7739 to M. N. S. Swamy and in part by Tennessee Technological University under its Faculty Research support program to P. K. Rajan.     

A scalable wireless virtual LAN

This paper presents a Wireless Virtual Local Area Network (WVLAN) to support mobility in IPoverATM local area networks. Mobility is handled by a joint ATMlayer handoff for connection rerouting and MAClayer handoff for location tracking, such that the effects of mobility are localized and transparent to the higherlayer protocols. Different functions, such as Address Resolution Protocol (ARP), mobile location, and ATM connection admission are combined to reduce protocol overhead and frontend delay for connectionless packet transmission in connectionoriented ATM networks. The proposed WVLAN, through the use of ATM technology, provides a scalable wireless virtual LAN solution for IP mobile hosts.     

Admission control with priorities: Approaches for multi‐rate wireless systems

Priority based linkbandwidth partitioning is required to support wireless multimedia services, having diverse QoS (delay, throughput) requirements, in mobile ad hoc networks with multimedia nodes. A new class of service disciplines, termed batch and prioritize or BP admission control (AC), is proposed. The BP algorithms use the delay tolerance of applications to batch requests in time slots. Bandwidth assignment is made either at the end of the slot, or during the slot, on a priority basis. Analytical and simulation models are developed to quantify the performance of the BP schemes. The results are compared with those obtained for a FirstComeFirstServed (FCFS) service discipline. The class of BP schemes trade off the delay and loss tolerance of applications to improve the net carried traffic on the link. Further, such schemes enable an easy implementation for adaptive prioritization, where the degree of precedence given to an application varies with offered load and the link capacity.     

A unified partitioning and scheduling scheme for mapping multi-stage regular iterative algorithms onto processor arrays

This paper addresses the partitioning and scheduling problems in mapping multi-stage regular iterative algorithms onto fixed size distributed memory processor arrays. We first propose a versatile partitioning model which provides a unified framework to integrate various partitioning schemes such as locally sequential globally parallel, locally parallel globally sequential and multi-projection. To alleviate the run time data migration overhead—a crucial problem to the mapping of multi-stage algorithms, we further relax the widely adopted atomic partitioning constraint in our model such that a more flexible partitioning scheme can be achieved. Based on this unified partitioning model, a novel hierarchical scheduling scheme which applies separate schedules at different processor hierarchies is then developed. The scheduling problem is then formulated into a set of ILP problem and solved by the existing software package for optimal solutions. Examples indicate that our partitioning model is a superset of the existing schemes and the proposed hierarchical scheduling scheme can outperform the conventional one-level linear schedule.