Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Recursive Bayesian traffic prediction for performance improvement in OBS networks Li, Rong 2005

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2005-0250.pdf [ 5.51MB ]
Metadata
JSON: 831-1.0065868.json
JSON-LD: 831-1.0065868-ld.json
RDF/XML (Pretty): 831-1.0065868-rdf.xml
RDF/JSON: 831-1.0065868-rdf.json
Turtle: 831-1.0065868-turtle.txt
N-Triples: 831-1.0065868-rdf-ntriples.txt
Original Record: 831-1.0065868-source.json
Full Text
831-1.0065868-fulltext.txt
Citation
831-1.0065868.ris

Full Text

R e c u r s i v e B a y e s i a n T r a f f i c P r e d i c t i o n f o r P e r f o r m a n c e I m p r o v e m e n t i n O B S N e t w o r k s by Rong L i B . E n g . , Nanjing University of Science and Technology, 1999 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M a s t e r o f A p p l i e d S c i e n c e in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Electrical and Computer Engineering) The University of Bri t ish Columbia A p r i l 2005 © Rong L i , 2005 11 A b s t r a c t This thesis deals with traffic prediction in Optical Burst Switched (OBS) networks with self-similar traffic, i.e., traffic with long-range dependence (LRD) properties. Aggregated traffic in high speed optical networks exhibits LRD properties. OBS is a recent promising optical network technology to facilitate IP-Over-WDM (Internet Protocol Over Wave-length Division Multiplexing). To improve the quality of service (QoS) in OBS transmis-sion networks, traffic prediction is required for dynamic resource reservation. We present and discuss a model of IP traffic based on MMPP (Markov Modulated Poisson Process), which approximates LRD traffic by mimicking the hierarchical generation of data by In-ternet users. The MMPP model is capable of effectively capturing the key aspects of the traffic measured on an OBS edge router, hence representing an aggregation of the traffic generated by a number of sources. The main contribution of this thesis is to derive an optimal Bayesian predictor for the burst size at the ingress router of an OBS network for MMPP approximations of LRD traffic. Bayesian prodiction yields the MMSE (Minimum Mean Square Error) estimate of the burst size. As shown in a simulated OBS testbed, such Bayesian predictor can yield substantial improvement in latency reduction and service differentiation of OBS network compared to linear predictors, without substantial increasing in computational complexity. i i i C o n t e n t s A b s t r a c t i i C o n t e n t s i i i L i s t o f T a b l e s v i L i s t o f F i g u r e s v i i A c k n o w l e d g e m e n t s ix 1 I n t r o d u c t i o n 1 1.1 Background and Motivat ion of the Thesis 1 1.2 Contributions 5 1.3 Thesis Overview 8 2 L i t e r a t u r e R e v i e w a n d R e l a t e d W o r k 9 2.1 Opt ica l Burs t Switched Networks 10 2.1.1 Overview 10 2.1.2 O B S traffic shaping 14 2.1.3 O B S burst reservation protocols 16 2.1.4 Contention resolution 18 2.2 Related Work on Traffic Models in O B S Network 20 2.3 Related Work on Traffic Predict ion 22 Contents iv 3 Self-Similar Traffic and M M P P Approximation 24 3.1' L R D Properties and Self-Similar Traffic 25 3.2 Influence of self-similar traffic in O B S 29 3.2.1 Influence on burst size distribution 29 3.2.2 Methodology 29 3.3 M M P P Approximat ion and Generation 30 3.3.1 Definitions and properties of M M P P 30 3.3.2 M M P P traffic generation model 32 4 Traffic prediction in OBS network 36 4.1 Pre-Reservation and Linear Predictor 37 4.2 M M P P Bayesian Predictor 41 5 Performance Analysis and Simulation Results 48 5.1 Mode l Setup 48 5.1.1 Opt ica l network architecture 48 5.1.2 Traffic generator 49 5.1.3 Edge router 50 5.1.4 Core Rou te r (OXC) 54 5.1.5 Buffer at routers 57 5.2 Simulation Experiments and Results 58 5.2.1 Assumptions 58 5.2.2 Predict ion performance improvement 59 5.2.3 B H P pre-transmission success probabili ty 64 5.2.4 Latency reduction improvement 65 5.2.5 Effect on Burst blocking probability 69 Contents v 6 C o n c l u s i o n a n d F u t u r e W o r k 71 6.1 Conclusion 71 6.2 Extensions 72 G l o s s a r y 74 B i b l i o g r a p h y 76 v i L i s t o f T a b l e s 3.1 Parameter setting for superposition of M M P P s 33 4.1 Program logic to compute $ and T for simple case, eg. N = 25 46 5.1 IP Header format 50 5.2 Burs t Header Packet ( B H P ) format 52 5.3 Edge router switching table 53 5.4 Edge router forwarding table 54 5.5 Information Base (LIB) at Core Node 57 v i i L i s t o f F i g u r e s 1.1 Design issue in optical networks 2 1.2 Three steps to predict burst size in an O B S network 7 2.1 Opt ica l network evolution 10 2.2 Functions at O B S edge node 12 2.3 Functions at the optical cross-connect supporting O B S and M P L S 14 2.4 The timer-based burst assembly mechanisms: (a) the periodic mechanism; (b) the non-periodic mechanism 15 3.1 Variance-time plot 28 4.1 Service differentiation at O B S ingress node wi th traffic prediction 38 4.2 Timer-based burst assembly wi th prediction 39 5.1 O B S network structure 49 5.2 Traffic generator node 50 5.3 M M P P traffic generator - the a im of this figure is to illustrate the trans-actions between this 16-state M M P P 51 5.4 O B S burst structure 52 5.5 Ingress node model (pr_0 and pr_l are inports; txOJBHP and t x l _ B H P are outports for B H P ; pt_0 and p t_ l are outports for data burst, each wi th 4 wavelengths) 53 5.6 O B S core node structure 55 List of Figures v i i i 5.7 P D F of prediction error (in bits) 59 5.8 Comparison of P£ under prediction error e = 10%, 20% 61 5.9 SNR-1 versus burst assembly time ra 62 5.10 S N R - 1 versus traffic in core network 63 5.11 Comparison of Ps versus burst assembly time ra 65 5.12 Comparison of O B S network wi th /wi thout Predict ion 66 5.13 Comparison of E T E delay wi th /wi thout Predict ion 68 5.14 Comparison of burst blocking probability wi th different predictor 69 ix A c k n o w l e d g e m e n t s Firs t and foremost, I would like to dedicate this thesis to my parents, for insti l l ing in me confidence and a drive for pursuing my master's degree. They have waited so long for this moment to come true; I am glad that their never-ending support has finally been rewarded. I would like to express my sincerest gratitude to my supervisor, Dr . V i k r a m K r i s h -namurthy, his encouragement, guidance and support, added considerably to my graduate experience. It is his in-depth theoretical knowledge and constructive suggestion that inspired me and were essential to the completion of this work. I also would like to thank all of my friends and fellow students, who have made my past years of study and work at U B C productive, cheerful and enjoyable. Their knowledge, care, encouragement, assistance and humor have meant a lot to me. C h a p t e r 1 i I n t r o d u c t i o n 1.1 B a c k g r o u n d a n d M o t i v a t i o n o f t h e T h e s i s The development of the Internet has been made possible through the huge increase in bandwidth of worldwide optical networks. Whi le capacity of transmission is growing rapidly, service providers now require a new generation of optical networking solutions to remain cost effective. Opt ica l Burst Switching (OBS) is a promising hybrid approach be-tween coarse grain optical circuit switching (OCS) and fine grain optical packet switching (OPS) , see Figure 1.1. It allows switching of data channels entirely in the optical domain by doing resource allocation in the electronic domain. Therefore, it is considered a viable solution for terabit IP backbone. W i t h the emergence of multi type applications such as data, voice, and videoconferencing, the next-generation network must also be designed to provide a variety of quality-of-service (QoS) functionalities. The basic ideas underlying an O B S system are twofold: the burstification of IP packets, and the decoupling of the transmission and switching of a control header and its data payload. In an O B S network, various types of client data are aggregated at the ingress (an edge node) and transmitted as variable-size data bursts that are later disassembled at the egress node. Each data burst is preceded by a control header, also called burst header packet(BBP)[l], which is transmitted A time units earlier in a separate control channel, and undergos optical-electrical-optical ( O E O ) conversions, to set up a switching Chapter 1. Introduction 2 Switching Required *~ granularity Optical packet switching Optical burst switching Optical circuit switching Figure 1.1: Design issue in optical networks path and reserve bandwidth at the core network. The time interval A that depicts how many time units the B H P preceeds the data burst is called offset time. The essence of an O B S system is the decoupling of the B H P and its data payload, which enables data bursts to be transmitted transparently (without O E O ) throughout the core network. A t present, O B S is attracting a lot of attention as a potential method by which future optical networks may use the available optical resources more effectively, i.e., achieving higher uti l ization. One of the main advantages of an O B S approach lies in its switching granularity, i.e., a data burst, shown in Figure 1.1. A n O B S network can switch variable-size data bursts instead of individual IP packets. It is a solution to compensate for the time constraint of directly switching individual IP packets at optical routers due to the mismatch between the transmission capability of W D M fibers and the processing capability of the electronic control plane, thus alleviating the heavy burden of electronic devices for lightpath configuration. This advantage results from the particular procedure of burstification, whereby multiple IP packets are aggregated into a single data burst at the network ingress. A side effect imposed by such a burst-buildup process, however, is an Chapter 1. Introduction 3 artificial delay. The typical end-to-end ( E T E ) delay of a data burst thus mainly consists of three components: burst assembly delay at edge routers, path setup delay caused by control headers, and the propagation delay in the core network. In real-time bursts, it is imperative to discuss their E T E delay. The time for assembling a burst, which usually consists of hundreds of IP packets and is typically on the order of microsecond to millisecond, is designed to be comparable wi th the switching path setup time. The propagation delay, usually in the range of millisecond, is significant compared to the burst length. Therefore, one-way signalling protocol is widely investigated in today's research to avoid the two-way propagation delay. Meanwhile, we notice that the burst assembly delay can be further saved if we could transmit the B H P before the burst is completely assembled. The assembly delay at network edges is substantial and has a significant impact on the E T E burst delay. This influence is especially detrimental to the real-time traffic, which has stringent delay constraints. Since the propagation time of a data burst cannot be reduced, reducing burst delay at network ingresses wi l l be greatly beneficial to latency reduction and QoS provisioning. Like an O P S network, an O B S network can dynamically control system resources, assigning wavelengths of optical fiber to individual data bursts only when that user needs to transmit data. As one-way reservation scheme is adopted to avoid the two-way prop-agation delay, the data burst is sent out after a certain offset time, and does not wait to receive an acknowledgement from its B H P . Therefore, if the B H P reserved an insufficient bandwidth, its following data burst wi l l be dropped at the core network, which w i l l result in high burst loss and lead to burst retransmission. Since the B H P is transmitted before the burst assembly finished, the actual burst length is not known ahead of time and the burst length prediction is required. The incoming IP traffic characteristics have great influence on the prediction of burst length. Chapter 1. Introduction 4 Internet traffic presents long-range dependence ( L R D ) , non-stationarity and mult i -fractal scaling in short timescales. The abili ty to predict traffic patterns wi th in an O B S network is one of the fundamental requirements of network design and management to facilitate QoS provisioning. A tradit ional linear predictor works well wi th short-range dependent (SRD) traffic, such as Poisson traffic, which is approaching uniform distribu-tion after aggregation number over 1000. Therefore, linear predictors lose accuracy when feeding in L R D traffic, such as Fractional Brownian Mot ion (fBm). There exists direct fractional predictor [2] that could achieve a near-optimal prediction for fBm, but it is too complicated to implement. Recent studies have found that Markovian models, such as M M P P (Markov Modulated Poisson Process) and M A P (Markovian Ar r iva l Process) are solvable mathematical traffic models that can approximate multifractal behaviour in finite time-scales [3]. There is significant motivation to construct an appropriate traffic model that leads to effective prediction algorithms for O B S networks, which yields a more precise prediction of burst length for the dynamic resource reservation. The choice of a prediction method is a tradeoff between the prediction interval, prediction error and computational cost. In this thesis, we present a traffic model based Bayesian (optimal) filter/predictor for O B S burst length prediction under M M P P traffic. We also compare the performance of the recursive Bayesian predictor wi th linear adaptive predictors, such as (least mean square) LMS-based filter in the following widely used criteria: (1), how far into the future can be predicted wi th confidence; (2), how much network resource has to be reserved to absorb the prediction uncertainty. The objectives of this thesis can be summarized as follows: Chapter 1. Introduction 5 • Study the Internet traffic characteristics at O B S edge nodes, i.e., the input traffic at O B S ingress routers. Meanwhile, wi th the influence of long-range dependence of Internet traffic properties, we analyze the assembled traffic statistics as the output traffic at O B S ingress router. • Examine the use of superimposed M M P P s (Markov Modula ted Poisson Process) as an approximation to L R D Internet traffic, which mimics the hierarchical generation of data by Internet users. It is shown in [4] that the superposition of M M P P s has sufficient long-memory characteristics and is therefore more appropriate for modeling the aggregated sources in optical edge networks. • Summarize and compare least mean square ( L M S ) based linear predictor and mini-mum mean square error ( M M S E ) based predictor in traffic prediction. According to our proposed traffic model M M P P , we derive a new prediction algorithm to optimize the tradeoff between efficiency and cost. • We further need to implement our traffic models and prediction algorithms and investigate the performance by means of a simulation program in the O P N E T en-vironment. 1.2 C o n t r i b u t i o n s In order to make effective advanced bandwidth reservations for data bursts, a key re-quirement is that the B H P needs to have an accurate estimate of the size of the data burst. For simplicity of expression, we use a discrete-time stochastic state space model below to illustrate our methodology. It is important to keep in mind that the O B S burst length prediction problem considered in this thesis is a continuous-time stochastic state Chapter 1. Introduction 6 space model, however the definitions below apply (with minor modification). Given the part ial ly observed stochastic dynamical system [ xk+1 = f6(xk) +wk (1.1) Vk+i = he{xk) + vk, (1.2) where k — 0 ,1 ,2 , . . . denotes discrete time, fk, hk are known functions, wk, vk are inde-pendent white processes wi th known densities, our aim is to estimate the state xk+i given the observation history of Yk = (yx, y2, yk)- The Bayesian state estimation is such a model-based optimal filtering, which assume the traffic model fe(.) is known, and then estimate the state xk+\ by x f c + i | f c = E{xk+1\Yk} (1.3) using both Eqs. (1.1) and (1.2). The Bayesian estimate xk xk = E{xk\Yk} (1.4) is the minimum-variance error estimate by minimizing E{(xk-g(Yk)f}, (1.5) where g(Yk) is the estimate xk. O n the other hand, adaptive filtering uses the static observation E q . (1.2), by assuming xk is vary slowly wi th unknown dynamics 9. Since the computation of the opt imal filter involves matr ix manipulation, as shown in Section 4.2, the computational cost is on the order of N2, while the adaptive filter only requires vector mult ipl icat ion at the cost of N, where ./V is the dimensions of the state space. In this thesis, we consider recursive Bayesian (optimal) fil tering/prediction of M M P P s , which are partially observed continuous-time dynamical systems. Similar results to that described Chapter 1. Introduction 7 Traffic Model Approximation M L E Parameter Estimation Bayestian State Estimation Figure 1.2: Three steps to predict burst size in an O B S network above hold for the optimal M M P P Bayesian prediction/estimation. As shown in Figure 1.2, the main idea of our work contains 3 steps: 1), construct an appropriate traffic model for incoming IP traffic in the O B S edge networks; 2), estimate the model parameters by using a maximum likelihood estimate ( M L E ) , for example using the expectation-maximization ( E M ) algorithm; 3), use Bayesian signal processing (predictor) to get the best state estimate. In this thesis, we focus on the first step, i.e., traffic model approximation and the th i rd step, i.e., state estimation. We skip the second step by assuming that the model parameter is known by appropriate parameter estimation. The main contributions of this thesis are as follows: • It is well known that the aggregated Internet traffic at the O B S ingress is self-similar. Based on the investigation of burst assembly mechanisms used at the O B S ingress router, we present to use a superposition of four independent 2-state M M P P s for approximating such self-similar traffic wi th L R D properties over sufficient time scales. The superposition results in a new 16-state M M P P model. Such M M P P approximations to L R D traffic are widely used in the literature [4] [5]. • Using the above M M P P approximation, we derive an opt imal recursive Bayesian traffic prediction algorithm, which dynamically predicts the burst duration of the O B S system. In the O B S network wi th advanced reservation ( A R ) applied, more accurate reservation gives a greater chance of success, and hence reduces burst loss Chapter 1. Introduction 8 probability. There are some studies in the literature focusing on linear predic-tion (LP) methods for traffic prediction, such as [6] [7]. The choice of a prediction method is a tradeoff between the prediction interval, prediction error and com-putational cost. Numerical results of our experimental comparison show that our M M P P Bayesian predictor can substantially improve accuracy compared to adap-tive L P without increasing computational complexity too much, i.e., from 0(16) to 0 ( 1 6 2 ) . • The main advantage is that by using recursive Bayesian predictor for the M M P P traffic, accurate estimates of the burst size can be obtained. That is, the performance of O B S network on-line traffic prediction can be optimized in terms of end-to-end ( E T E ) delay and burst loss probability, which are the two fundamental issues of providing QoS differentiation when applying O B S to the next generation. 1.3 T h e s i s O v e r v i e w The rest of this thesis is organized as follows: Chapter 2 presents related work, including an overview of new techniques in today's optical burst switching networks. Then we introduce the M M P P traffic modelling for self-similar traffic and generating method in Chapter 3. In Chapter 4, we give a detailed theoretic analysis of our proposed Bayesian M M P P predictor, wi th a comparison to L M S based linear predictor. In Chapter 5 we describe the O B S simulation testbed, present the simulation results for the proposed M M P P Bayesian prediction schemes and compare the analytical results. We further show that the simulation results also validate that our proposed M M P P predictor performs better than linear prediction. Final ly, Chapter 6 concludes the thesis wi th a summary of the presented work and suggests future work. 9 C h a p t e r 2 L i t e r a t u r e R e v i e w a n d R e l a t e d W o r k In this chapter, we first give an introduction to optical burst switched (OBS) networks. A comparison between this new switching paradigm wi th other existing optical switching paradigms has been made, and it has been shown that O B S is not only cost-effective but also a viable solution for the next generation optical Internet. We provide a brief historical review of the early work on burst switching as well as the state of the art, including the prevailing protocol for O B S networks, called Just-Enough-Time ( J E T ) , and describe its major features and benefits. Opt ica l Networks, wi th their high transmission speed, are the ideal communication infrastructure to meet the ever increasing demand on bandwidth. W i t h recent advances in wavelength division multiplexing ( W D M ) technology, the potential of fiber was fully realized. It is a technology to increase transmission capacity by transmitt ing data si-multaneously at multiple carrier wavelengths. B e l l Labs scientists have determined that wi th wavelengths and values typically used in optical networks today, it is theoretically possible to transmit data at 100 terabits per second without any excessive signal noise or interference [8]. Current commercial optical systems allow for the mult iplexing of more than 160 wavelengths at lOGbps each to get a total throughput of 1.6 terabits per second per fiber. Chapter 2. Literature Review and Related Work 10 2.1 (0 c o u c <» z Q. O ^ Optical Packet Switched ^ Optical Burst Switched Mesh ^ ^ Optical Burst Switched Ring J Wavelength-Routed Mesh ^ Q Wavelength-Routed Ring ^ AONs c Point-to-Point WDM Links O E O required time Figure 2.1: Opt ical network evolution O p t i c a l B u r s t S w i t c h e d N e t w o r k s 2.1.1 Overview Current W D M networks operate over point-to-point links, where optical-to-electrical-to-optical ( O E O ) conversion is required at each step. However, al l future research is focused on all-optical networks (AONs) where user data travels entirely in the optical domain. The elimination of O E O conversion in A O N s allows for unprecedented transmission rates. A O N s can further be categorized as wavelength-routed optical networks ( W R O N s ) , optical burst switched networks (OBSNs) , or optical packet switched networks (OPSNs) . Switching techniques primari ly differ based on whether data w i l l use switch cut-through or store and forward. The A O N evolution (Figure 2.1) begins wi th the W R O N s , which is also referred to as an optical circuit switched (OCS) network. In circuit switching, it is necessary to establish a dedicated path between the two stations. A call is first set up, the data is transferred and the call is disconnected. Resource reservation is done for the duration of the call . In optical circuit switched architecture, an end-to-end all-optical Chapter 2. Literature Review and Related Work 11 circuit, called lightpath, is established before the transmission of data signals, similar to a telephone line in public switched telephone networks. Ci rcui t switching is advantageous when we have a constant data rate (fixed delays) on the network like voice traffic; how-ever, it is not suitable under bursty traffic conditions, or when circuits are idle. The main constraint of W R O N s is the l imited number of wavelength per fiber. Al l -op t ica l circuits tend to be inefficient for traffic that has not been groomed or statistically multiplexed, and are wasteful when the sustained traffic volume does not consume a full wavelength. In packet switching, the data is broken into small packets and transmitted. The resources can be shared by the different sources. Opt ica l packet switching (OPS) is a technology to transmit user data by means of optical packets, in which a wavelength is only allocated to a packet when it is transmitted, and it can be reused by others after the transmission. Packet switching works well wi th variable rate traffic like data traffic, and can achieve higher uti l ization. Therefore, O P S is more efficient and it can be used to support IP traffic and A T M traffic. However, O P S requires practical, cost-effective, and scalable implementations of optical buffering and optical header processing, which are server years away. X u [9] reviews the O P S technology. Circui t switching uses two-way reservation schemes that have a large round-trip time requirement. Packet switching, on the other hand, has a large buffer requirement and complicated control and strict synchronization issues. Opt ica l burst switching (OBS) is a technology positioned between wavelength routing (i.e., circuit switching) and optical packet switching. O B S has the advantages of both circuit switching and packet switching, and is considered a promising protocol for all-optical networking. The benefit of O B S over circuit switching is that there is no need to dedicate a wavelength for each end-to-end connection. In addition, optical burst switching is more viable than optical packet switching as the burst data does not need to be buffered or processed at the cross connect. Chapter 2. Literature Review and Related Work 12 !P/ATM/GbE(data) Upper layer —I—t data SONET (voice) Ingress Edge Node (a) burst assembly From OBS Core Control packet . _ C 7 L _ . Burst IP/ATM/GbE(data) i 1 l~ l To local destination SONET (voice) Egress Edge Node (b) burst disassembly Figure 2.2: Functions at O B S edge node This allows the strengths of optical switching technologies to be leveraged effectively and the problem of buffering in the optical domain to be circumvented. Opt ica l burst switching is based on the separation of the control plane and the data plane. Thus, costly O E O conversions are required only on a few control channels instead of a large number of data channels. In O B S networks, data packets are aggregated into much larger bursts before transmission through the network. This allows amortization of the switching overhead across multiple packets. There are two kinds of nodes in the O B S network: edge node and core node. The O B S edge nodes consist of an electronic router and a burst assembler while the O B S core nodes require an optical switching matrix, a switch control unit, and routing and signaling processors. The main function of the O B S edge nodes is to collect traffic from various upper-layer users such as A T M switches, IP routers, etc. This collected data is sorted based on a destination address and is assembled into large variable-size units, called bursts, which are typically several hundreds of kilobytes in size. In addition, the O B S edge nodes create a control packet for each data burst, which contains burst length, offset time, and Chapter 2. Literature Review and Related Work 13 all routing information, and is sent toward the destination at an offset time before the burst itself (Figure 2.2 (a)). These control packets are electronically processed at each intermediate node along the path, from the source to the destination. Their goal is to set up the O B S core switches along the way, so that their corresponding bursts can travel transparently in the optical domain through an bufferless or buffer l imited network. The data burst w i l l later be disassembled at the O B S egress edge node (Figure 2.2 (b)). Dur ing the assembly/disassembly, the client data is buffered at the edge, where electronic R A M is cheap, and abundant. There literature indicates that there are two ways to transmit these signaling packets. One is to set up a completely separate electronic control network, such as IP or A T M network, whereas mainly adopted way is to designate a specific wavelength in an all-optical network, which can be considered as an out-of-band control channel. In either case, the separation of control and data, both in time and physical space, is one of the main advantages of O B S . It facilitates efficient electronic control while allowing for great flexibility in the user data format and rate [10] because the bursts are transmitted entirely over an optical signal and remain transparent throughout the network. In general, al l O B S designs include an offset time between the transmission of a control packet and its corresponding burst. This offset allows the control packet to reserve the needed resources along the path toward the destination before the burst arrival. Further-more, the O B S core nodes need this offset time to pre-set their switching fabrics so that the user data can "cut-through" without any buffers (Figure 2.3). There are variations in the O B S literature, explained in the following sections, on how exactly to determine the pre-transmission offset time and when to reserve the needed resources at the core nodes. Despite their differences, however, al l of the proposed O B S networks have a dynamic operation, which has the potential for high resource uti l izat ion and adaptability. Reference [11] describes a burst switch architecture design and operation, as well as Chapter 2. Literature Review and Related Work 14 Optical cross-connects packel n x / v • < < burst ' n f f c r a l ' Reservation request on selected wavelength Select output interface Figure 2.3: Functions at the optical cross-connect supporting O B S and M P L S the concept of control channel, data burst, and head cell, etc. References [12] [1] propose a network architecture such that the O B S network is the backbone of the Internet (IP network), and describe the architecture of an optical switch (router) wi th the functions that include burst control packet detecting, processing, and rewriting; forwarding table lookup; management of shared buffer (fiber delay line, or F D L ) ; wavelength conversion; and data channel scheduling. Reference [13] studied access schemes in O B S for a metro ring architecture. As O B S becomes more mature, reference1 [14] discussed technical issues and general requirements for a transport layer architecture (i.e., services and protocols) for O B S networks. 2.1.2 OBS traffic shaping One of the main functions of an O B S network is to collect upper-layer traffic, classify it and aggregate it into variable-size bursts. The classification and the proper assembly algorithm of small IP packets to larger optical bursts at edge nodes are essential for the performance of burst reservation, transmission and electronic control in core nodes, because it allows the network designers to control the characteristics and therefore shape the burst arrival traffic [15]. Chapter 2. Literature Review and Related Work 15 B l , 8 2 , 8 3 , 3 4 < N« H« H< * (a) B l B 2 B 3 W M (b) t Figure 2.4: The timer-based burst assembly mechanisms: (a) the periodic mechanism; (b) the non-periodic mechanism. A t the O B S edge node, incoming IP packets are classified based on the egress node and QoS class and stored in assembly queues accordingly. For burst assembly, two assembly algorithms are used as basic building blocks [16]: threshold-based and time-based schemes. In the first scheme, a burst is sent out when enough IP packets have been collected in the assembly queue such that the length of the resulting burst exceeds a threshold of Lmax bytes. In the second scheme, a time-out interval Tmax is set upon the arrival of the first IP packet to an empty queue. A burst consisting of a l l packets in the assembly queue is sent out as soon as a time-out occurs. The timer-based mechanism also includes the periodic and the non-periodic alternatives, whose intrinsic features are illustrated in Figure 2.4. In the periodic mechanism, the burst is assembled back-to-back. Tha t is, the new burstification process begins as soon as the previous data burst is assembled and lasts unt i l the pre-determined interval of Tmax elapses. A new data burst, however, is not actually generated if no packet arrives during the whole burstification interval. In the non-periodic assembly mechanism, the next burstification process starts only when a new IP packet arrives. Another variation of the time-based scheme ensures a minimum burst length Lmin by introducing padding bytes if necessary. The characteristics of the output burst traffic can differ between the above algorithms. In the case of the pure threshold-based algorithm, burst traffic has the same self-similarity Chapter 2. Literature Review and Related Work 16 as the input packet traffic. In the case of the time-based algorithm, burst traffic may have a smaller degree of self-similarity than packet traffic and therefore reduce the contention in the core network and make burst traffic smoother at short time scales. [17] studies the traffic characteristics while combining both criteria together, and concludes that the burst departures are not exponentially distributed but are correlated wi th the burst size. 2.1.3 OBS burst reservation protocols There are three main components to set up a connection in O B S framework. The first one is the signaling procedure, which consists of creating the O B S control packets ( B H P ) and sending it an offset time ahead of its corresponding data burst. The other two are routing and wavelength allocation. The various O B S signaling protocols that have appeared in the literature can be broadly classified by three dimensions: (1) the manner in which control is exercised in the network (i.e., distributed or centralized), (2) the reservation scheme used to hold wave-length resources for bursts, and (3) the method in which the offset value is calculated (and the purpose it serves). B y contrast wi th centralized signalling wi th end-to-end reservation in packet switching network, most of the proposed O B S architectures use a distributed one-way signaling procedure to set up a burst transmission path through the network. That is, the data burst is transmitted after a delay (known as the offset) of its control header ( B H P ) , without waiting for a positive acknowledgment ( A C K ) that the entire path has been successfully established. Since O B S wi l l most likely be implemented in long-haul networks, the main benefit!of one-way reservation is that it halves the propagation delay, and therefore it w i l l significantly decrease the time needed to establish a connection. Chapter 2. Literature Review and Related Work 17 The manner in which output wavelengths are reserved for bursts is one of the prin-cipal differentiating factors among O B S variants. We distinguish between two types of reservations schemes: immediate and delayed. Immediate reservation, exemplified by the Just-In-Time (JIT) family of O B S protocols [18], works as follows: an output wavelength is reserved for a burst immediately after the arrival of the corresponding setup message; if a wavelength cannot be reserved at that time, then the setup message is rejected and the corresponding burst is dropped. The Horizon [11] and Just-Enough-Time ( J E T ) [19] protocols employ a delayed reser-vation scheme, which operates as follows: an output wavelength is reserved for a burst just before the arrival of the first bit of the burst; if, upon the arrival of the setup mes-sage, it is determined that no wavelength can be reserved at the appropriate time, then the setup message is rejected and the corresponding burst is dropped. Most O B S time offsetting techniques are based on the assumption that the control packet is sent after the entire burst is assembled. A variation on these techniques is to send the control packet before collecting the entire burst from the upper layers, such as F R R (Forward Resource Reservation) [7]. The F R R scheme involves 3 steps: predict the data burst length before or during the burst assembly; pre-transmit the B H P for resource reservation before the data burst assembly is completed; when the burst assembly is completed, check whether the pre-reserved resource is sufficient to support the actual burst. The main advantage of this variation is the reduction in the burst pre-transmission delay. However, since the exact length of the burst is not included in the corresponding control packet, imperfect prediction regarding burst length may lead to overhead due to waisted bandwidth. In the literature, the immediate reservation is also referred to as "explicit setup" and the delayed reservation is called "estimated setup." Similarly, an "explicit release" is used when the source sends an explicit t rai l ing control packet to signify the end of a Chapter 2. Literature Review and Related Work 18 burst transmission and to release the resources at al l the intermediate nodes. Another possibility for wavelength release, termed as "estimated release," requires that the in i t ia l control packet contain the oncoming burst length and thus the O B S core node would know exactly the end of the burst transmission and would automatically release the occupied resources. Based on this classification, the four possibilities in an O B S network are: explicit setup/explicit release, explicit setup/estimated release, estimated setup/explicit release and estimated setup/estimated release. Overall , there no clear winner between these schemes, and each has advantages and disadvantages. For example, the estimated schemes occupy resources for shorter times, and therefore they can achieve a higher network throughput. The difficulty wi th these schemes, however, lies in the fact that they are inherently quite complicated and their performance greatly depends on whether the esti-mates are correct. B y contrast, the explicit setup/explicit release scheme is much easier to implement but it occupies resources for longer periods than the actual burst transmission, and therefore it may result in higher burst loss probability. 2.1.4 Contention resolution In O B S , when one-way reservation schemes (e.g., J IT , J E T , and Horizon) are adopted, it is possible that two bursts compete for the same output port; thus contention may arise. Such a contention situation can be resolved through one or a combination of the following three domains: • Wavelength domain: B y means of a wavelength converter, a burst can be sent on a different wavelength channel to the designated output fiber. Thus, al l the wavelength channels of an output fiber can be considered a single shared bundle of Chapter 2. Literature Review and Related Work 19 channels. • T ime domain: In a fiber delay line ( F D L ) buffer, a burst can be delayed unti l the contention situation is resolved and the wavelength becomes available. In contrast to buffers in the electronic domain, F D L s provide only a fixed delay, and data bursts leave an F D L in the same order in which they entered. That is, they do not have random access functionality. • Space domain: In deflection routing, a burst is sent to a different output fiber of the node and consequently on a different route towards its destination node. Thus, deflection uses the entire network as a shared resource for contention resolution. Almost al l work on O B S assumes contention resolution by full wavelength conversion. That is, a dedicated wavelength converter is provided for each input or output wavelength. For a low to medium load, this provides a low burst loss probability because all wavelength channels of an output fiber can be shared among all bursts directed towards this output fiber. For a high load, the number of wavelength channels has to be very large to reach burst loss probabilities of 1 0 - 6 or less, e.g., 350 wavelength channels are needed to carry a load of 0.8 Er lang per wavelength channel at this loss rate. Wavelength conversion has also been complemented by providing a number of F D L s in an F D L buffer. It can be seen that the application of an F D L buffer has a significantly reduced burst loss probabili ty compared to the bufferless case. W h e n using F D L buffers in O B S nodes, the physical length of the F D L has to be considered. Even if the F D L s are dispersion compensated if needed, the maximum length of an F D L is l imited by the power budget. Thus, combining performance and technology arguments, mean burst lengths in the order of Mbytes cannot be realistically stored in F D L buffers. Chapter 2. Literature Review and Related Work 20 Deflection routing has also been analyzed in the context of O B S for irregular mesh networks [20] [21]. In general, the path a deflected burst takes through the network should be as short as possible to minimize resource consumption. In O B S schemes which apply offset .times, the problem of insufficient offset times has to be avoided. Tha t is, it has to be ensured that there always be a large enough offset between control packet and data burst even if extra nodes are traversed. Thus, [20] proposes to use F D L buffers to increase offset times in intermediate nodes prior to deflection. B y an intelligent combination of different contention resolution strategies, the cost and performance of O B S nodes can be optimized. Burs t segmentation or composite burst switching is an approach for contention resolution that is based solely on burst scheduling: It tries to minimize the data volume discarded by not dropping an entire burst but dropping only that part of a burst that actually conflicts w i th another burst [22] [23], 2.2 R e l a t e d W o r k o n T r a f f i c M o d e l s i n O B S N e t w o r k Traffic models play very important roles in the planning, design and analysis of communi-cation networks. Different models have different results, and the discrepancy between the results using different models can be huge. Applications of traffic models include resource allocation, call admission control and QoS provisioning. In the design of O B S networks, a major a im is to solve the problem of the mismatch between extremely high optical transmission rates and the relatively slower electronic processing. Burs t assembly is required at the O B S edge nodes, where short IP packets Chapter 2. Literature Review and Related Work 21 are demultiplexed according to their destination and gathered into larger size packets. These super packets are also called bursts. The outcoming burst traffic from the edge node w i l l depend highly on the incoming IP traffic and the burst assembly algorithm. Internet IP traffic has been demonstrated to affect network performance by two kinds of bursty property: short-range dependent (SRD) burstiness and long-range dependent ( L R D ) burstiness. Memoryless Poisson models were assumed in the O B S network in the past few years; however, recently, there has been a significant change in the understanding of network traffic. Poisson models for network traffic become essentially uniform when aggregated by a factor of 1,000; while actual network traffic shows no such decrease in variabili ty over the same range of aggregation. Numerous studies have found that data traffic in high-speed networks exhibits self-similarity that cannot be captured by classical models. Tradit ional Markov models and Regression models can only capture short range dependencies in traffic. In a classical Markov chain, the next state of the system depends only on the current state. Regression models define explicit ly the next random variable in the sequence by previous ones wi th in a specified time window and a moving average of white noise. The degree of self-similarity, defined by the Hurst parameter, typical ly depends on the uti l izat ion level of the network and can be used to measure the "burstiness " of the traffic. The Hurst parameter is basically a measure of the speed of decay of the ta i l of the autocorrelation function; as H increases the degree of self similari ty increases. If 0.5 < H < 1, then the process is long-range dependence ( L R D ) , and if 0 < H < 0.5, then it is short-range dependence (SRD) . Hence, H is widely used to capture the intensity of the long-range dependence of a traffic process. The closer H is to 1 the more long-range dependent the traffic is, and vice versa. In this section we review some long-memory models, which are widely used in theory Chapter 2. Literature Review and Related Work 22 and practice to model self-similar traffic. The observation of L R D property in the Internet traffic has initiated studies of new models such as chaotic maps [24], fractional Brownian motion (fBm) models [25], fractional Gaussian noise (fGn), and fractional autoregressive integrated moving average ( F A R I M A ) [26]. F B m is a non-stationary stochastic process developed as a generalization of the standard Brownian motion model. F G n is a station-ary process. F G n is related to fBm, since fGn is produced by taking the differences in f B m realizations. They can describe self-similar behavior in a relatively simple manner. Wavelet analysis was shown to be one of the most powerful methods for the description of stochastic properties of traffic, which takes explicit ly into account a multi-fractal model as in [27]. The main advantage of these models, especially when multifractality is taken into account, is their rich scale-invariance property. These models are computationally efficient, but they suffer for the lack of a simple mapping between the traffic parameters and the model coefficients. The queuing theoretical techniques developed in the past are hardly applicable to these models. O n the other hand, a number of models based on tradit ional traffic models have been proposed. One approach is to emulate self-similarity over a certain range of time scales wi th finite state Markovian models. [28] [4] have proposed a model based on the Markov Modula ted Poisson Process ( M M P P ) as a superposition of two-state Morkov processes. M M P P is considered as the best Markov process to emulate L R D and scale invariance [3]. In this work we w i l l also apply such an approach. 2 . 3 R e l a t e d W o r k o n T r a f f i c P r e d i c t i o n In an O B S network, the burst reservation message provides a report of the incoming burst length in a tell-and-go fashion along the path from source (ingress edge node) to Chapter 2. Literature Review and Related Work 23 destination (egress edge node). Note that there is a packetization delay, due to the burst assembly time, which is inherent to burst switching. W h e n to send the reservation message to the core network belongs in the scope of QoS provisioning. Burst length prediction is required if the reservation signaling message is sent before burst assembly finishes. Linear predictor is the simplest one, which does not need prior knowledge of incoming traffic patterns, and suitable for any traffic model. In the literature, some studies propose to use the least mean square ( L M S ) based linear prediction method to predict the burst length in the O B S network [6] [7]. Another more sophisticated non-linear method is M M S E (minimum mean square error) predictor, which aims to minimize the expected value of the squared prediction error, and also works for on-line prediction that does not require the underlying structure of the incoming traffic. O n the other hand, the quality of the prediction depends on the amount of uncertainty, which in turn depends on a number of factors, including the amount of traffic history used to make the prediction, the prediction horizon, and the nature of traffic itself. Predictors based on traffic structure have the significant benefit of computing the weight factor on history samples. Considering the abundant evidence that high-speed network traffic is self-similar and long-range dependent ( L R D ) in nature and the fact that the history of L R D processes has a significant impact on the present value of the process, it is natural to assume that predicting L R D traffic would be rather rewarding. There are particular predictors [2] based on fractional traffic models, such as fBm and fGn processes. From the engineering perspective, these fractional predictors are too complicated to implement and time-consuming when doing dynamic bandwidth reservations. 24 C h a p t e r 3 S e l f - S i m i l a r T r a f f i c a n d M M P P A p p r o x i m a t i o n It is well known that the characteristics of aggregated Internet traffic at the O B S ingress nodes is fractal and can be described in terms of self-similar stochastic processes. However, in the last few years, considerable effort has been devoted to studying the O B S burst traffic after assembly, as the burst size distribution determines the optical buffering requirements. Therefore, the self-similarity of O B S burst traffic has a significant impact on the overall network performance, e.g., burst blocking probability. Self-similarity indicates long-range dependence ( L R D ) in the correlation structure of network traffic. Generally speaking, although the incoming packet traffic is aggregated in O B S assembly nodes, the number of assembled burst input flows in the O B S core node is in fact not large, and not enough to be aggregated to Poisson burst traffic. Furthermore, the claim that burst assembly could reduce traffic self-similarity [29] was disproved by analysis and the simulation of both synthetic traffic and traffic traces [30] [31]. In this chapter, we show first special interest on how the self-similarity features of incoming traffic affect the burst size distribution. Then we propose to use M M P P ap-proximation to represent the aggregated Internet traffic at the O B S edge. The traffic generation of this special M M P P model is also provided. Chapter 3. Self-Similar Traffic and MMPP Approximation 25 3 . 1 L R D P r o p e r t i e s a n d S e l f - S i m i l a r T r a f f i c A s the term implies, long-range dependence refers to a correlation structure that decays at a rate much slower than the exponential decrease that occurs in the correlations of a short-range dependent (SRD) process. A n interesting characteristic of the correlation structure of a long-range dependent process is that its autocorrelation obeys the well-known power-law distribution. That is, for a stationary L R D process {Xt},t = 0 ,1 ,2 , . . . wi th mean p, variance a2 and autocorrelation function rLRD{k), we have[32] Thus the autocorrelation function of such a process decays hyperbolically. Hyperbol ical decay is much slower than exponential decay, and since (3 < 1, the sum of the autocorre-lation values of such a series approaches infinity. This description is closely associated to self-similarity and a Hurst parameter defined by the equation: As we stated in section 2.2, the Hurst parameter H is the index of self-similarity. That is, for general self-similar processes, it measures the degree of "self-similarity." When the parameter lies in the interval (0.5,1), the resulting self-similar process exhibits long-range dependence as defined in Eq.(3.2). In contrast, a short-range dependent process requires that its autocorrelation function of {Xt} decays exponentially to zero. Tha t is, {Xt} would have a correlation function rsRD(k) decreased according to rLRD(k) ~ k 0 , as k —> oo, where (0 < (5 < 1) (3-1) H = 1-/3/2 (3-2) rSRD(k) -> C\ as k —> oo, where — 1 < C < 1. (3-3) Chapter 3. Self-Similar Traffic and MMPP Approximation 26 Common traffic models wi th L R D are based on self-similar processes. Intuitively, a process is self-similar if its statistical behavior is independent of the time-scale. In other words, the characteristics of a self-similar process look the same at any time scale. Th is feature means that averaging over equal periods of time does not change the statistical characteristics of the process. Consider the above stationary time series {Xt},t — 0 ,1 ,2, . . . , wi th zero mean and autocorrelation function r(k), representing the number of packets during time intervals observed on a given link, where r(k) is given as We define the m-aggregated series X[m^ by summing the original series X over non-overlapping blocks of size m, replacing each block by its sample mean. That is, for each m = 1, 2 , 3 , X [ m ^ is given by •^(m) _ — y ^ X ( t _ i ) m + j , t = 1,2,... (3.5) The processes {X^} are also wide sense stationary wi th mean /J, and autocorrelation r^ m ' (A;). There are different classes of self-similarity: • Exact Self-Similar: the process {Xt} is said to be exactly self-similar if for al l m = 1 , 2 , i t satisfies r(m\k) = r(k). (3.6) (3.6) also implies an equivalent definition: Var{X{m)) = m-0Var(X), for al l m, and 0 < B < 1. (3.7) Chapter 3. Self-Similar Traffic and MMPP Approximation 27 In other words, the autocorrelation structure is preserved across different time scales. • Asymptot ic Self-Similar: the process {Xt} is said to be asymptotically self-similar if for al l k large enough, r{m){k) - » r(jfe), when m -> co. (3.8) which could also be represented by: Vcir{X{m)) ~ m-PVariX), as m - • oo, where 0 < /? < 1. (3.9) • iStochastic Self-Similar: This is a continuous time definition. The process {Xt} is statistically self similar wi th the parameter H , if for any positive stretching factor a, the re-scaled process wi th time scale at, a~HXat is equal in distribution to the original process {Xt}, and they satisfy the relation Xat ~ a-"Xt, for a l l (a > 0), (3.10) where ~ denotes equality in distribution. This is a very strict form of self-similarity called self-similarity wi th stationary increments. F B m is an example of such a process. Taking the logarithm of both sides of E q . (3.7) gives the following equation: \ogl0(Var(X™)) = \og10Var(X) - / ? l o g 1 0 (ro) (3.11) The variance-time plot (Fig.3.1), often used to test traffic for self-similar properties, is based on this equation. Self-similar traffic results in a straight line wi th slope G [—1,0]. Chapter 3. Self-Similar Traffic and MMPP Approximation 28 E CO > o U) O Self-similar: slope - P \ Poisson: slope -1 0 1 2 3 4 5 Log 1 0 m Figure 3.1: Variance-time plot For successive values of m that are equidistant on a log scale, the logarithm of sample variance of is plotted versus m on a log-log plot. Therefore, in practice, the most common way to validate if a generated process is L R D is by fitting a least-square line to the points of the plot and then calculating its slope. A n estimate of the Hurst parameter is obtained as H = 1 — The relation between self-similarity and L R D is that if a process {Xt} is self-similar wi th Hurst parameter H , then its increment process Yt = Xt+S—Xs is L R D wi th parameter H . , Chapter 3. Self-Similar Traffic and MMPP Approximation 29 3 . 2 I n f l u e n c e o f s e l f - s i m i l a r t r a f f i c i n O B S 3.2.1 Influence on burst size distribution The distribution of burst length can be influenced by offered traffic and burst assembly parameters. In general, according to Central L i m i t Theorem ( C L T ) , by aggregating IP packets into bursts, the burst size distribution w i l l approach Gaussian distribution as the number of packet arrivals goes up or the assembled burst size goes up, as verified by our simulation results. O n the other hand, the influence of self-similarity (H parameter) is significant, especially as the timeout value grows. This is due to the fact that, as the H parameter grows, the variance of the traffic sample mean (aggregated traffic) decays more slowly than in the independent case (H=0.5). Thus, the larger the H parameter the larger the burst size variance. As discussed in Chapter 2.1.2, the traffic shaping (burst assembly) at the O B S edge node can smooth traffic on short time-scales, i.e., reducing its variability. If the correlation extends only over timescales smaller than a burst assembly period, the correlation in the packet traffic process is shaped away by burstification; i.e., it w i l l not be observed in the burst traffic process. If, on the other hand, the correlation extends over timescales much larger than a burst assembly period, burstification w i l l not shape it away, so that a similar correlation structure wi l l exist in both packet and burst traffic streams. Longer assembly times lead to improved smoothing. 3.2.2 Methodology Motivated by the above observation, we now introduce a simple Markovian approach to approximate the self-similar traffic over sufficient time scales for burstification at O B S edge nodes. In traffic modelling, a superposition of several M M P P s is practically sufficient Chapter 3. Self-Similar Traffic and MMPP Approximation 30 to represent self-similarity over several time-scales to model the real traffic. We construct an M M P P wi th apparently self-similar behaviour over several time-scales by superposing several M M P P s . Firs t , consider two-state M M P P s wi th different time-scales. That is, the mean sojourn time of each process is in accordance wi th the different time-scale. Let us superimpose them to make a new M M P P . When we see this process on a large time-scale, it looks like an ordinary two-state M M P P . If we look on a smaller time-scale, we find that each state is composed of a smaller M M P P . If we look on a s t i l l smaller time-scale, we find that each state of a smaller M M P P is again composed of a s t i l l smaller M M P P . This can be repeated only a finite number of times. It is impossible to measure given traffic during an infinite amount of time. Thus, it is in practice sufficient to use the process that has self-similarity over only several time-scales to model the real traffic. Refer to [4] [5] for details. We use a continuous-time discrete-state M M P P for modeling the self-similar traffic. Tha t is, for our O B S system wi th self-similar traffic input, we assume first that the traffic carried by each forward equivalence class ( F E C ) is a M M P P and that M M P P s are independent of one another. The O B S network supports several F E C s from different edge O B S shapers, which are assumed to have the same mean, variance and Hurst parameter, without loss of generality. 3.3 M M P P Approximation and Generation 3.3.1 Definitions and properties of M M P P In this section, we summarize some of the main characteristics of M M P P defined on a probabili ty space. M M P P is a doubly stochastic Poisson process where the intensity of Chapter 3. Self-Similar Traffic and MMPP Approximation 31 a Poisson process is defined by the state of a Markov chain. The Markov chain can therefore be said to modulate the Poisson process, hence the name. Now, let {Xt} be a continuous-time S-state Markov chain, without loss of generality, defined on the state space e = { d , e 2 , e s } , where e, 6 R s is the unit vector wi th 1 in the i-th position. This Markov chain modulates an integrable Poisson traffic rate process; hence in this S-state M M P P , the packet arrival rate is determined by the state of the continuous-time Markov chain wi th infinitesimal generator Q and Poisson arrival rate A,, i € [1,5]. That is, the traffic rate process behaves as a Poisson process wi th arrival rate \ when the Markov chain is in state i. B o t h the Markov chain and Poisson process can have simultaneous jumps. Transitions between states are dependent and governed by the above continuous-time Markov chain. Q is also known as the transition rate matrix of the modulating Markov chain. ' . ' #11 #12 ••• 0is 021 022 ••• 025 Q 0si 0, S2 055 j=l (3.12) which equals £ ^ = 0 , V i e { l , 2 , . . . ) S } . j=i (3.13) Define the arrival rate matrix A = diag[X\, A 2 , A s ] , whose diagonal elements con-tains the arrival intensities that corresponds to the different states of the Markov chain. Also define P{Xt = i} — p\, i € {1,2 , . . . , 5 } . Then the transition probabili ty distri-bution pt = {ptPt-'-PtY should be [e^'4], which satisfies the forward equation ^ = Q'pt, where ' denotes the transpose operation. Let Nt denote the above Markov chain {Xt} modulated Poisson process, which repre-Chapter 3. Self-Similar Traffic and MMPP Approximation 32 sents the number of events that occur during the interval [0,t]. For the time-stationary M M P P , the mean of Nt is given by [33] where 7r = [ni, 7T2, ITS] is the steady state vector of the Markov chain such that 3.3.2 M M P P traffic generation model We use a continuous-time M M P P for modeling the self-similar traffic. We construct an M M P P wi th apparently self-similar behaviour over several time-scales by superimposing several M M P P s . Firs t , consider two-state M M P P s wi th different time-scales. That is, the mean sojourn time of each process is in accordance wi th the different time-scales. Let us superimpose them to make a new M M P P . W h e n we see this process in a large time-scale, it looks like an ordinary two-state M M P P . If we look at a smaller time-scale, we find that each state is composed of a smaller M M P P . If we look at a st i l l smaller time-scale, we find that each state of a smaller M M P P is again composed of a s t i l l smaller M M P P . This can be repeated only a finite number of times. Therefore, the M M P P is not self-similar according to the definitions in the previous section because it looks constant when time-scale is larger than the time constant in itself. However, it can emulate self-similarity over several time-scales. It is impossible to measure given traffic during an infinite amount of time. It has also been observed that high-speed traffic loses self-similarity over days [34]. Thus, it is practically sufficient to use the process which has self-similarity over only several time-scales to model the real traffic. Now we assume that the number of the states E{Nt} = vrAei, (3.14) nQ = 0, 7re = 1 (3.15) Chapter 3. Self-Similar Traffic and MMPP Approximation 33 source A* 0~2i IPPX 6.579 5.715* 1 0 - 1 2.285 * 1 0 - 1 IPP2 2.562 1.231 * 10~'2 4.923 * 1 0 - 3 IPP3 0.914 2.653 * 10~ 4 1.061 * 1 0 ~ 4 IPP4 0.448 5.715 * 10"^  2.285 * 10~ e Pois. A P = 0 Table 3.1: Parameter setting for superposition of M M P P s of every underlying M M P P is two. We construct a model that consists of a superposition of four independent two-state M M P P s and one Poisson process. We consider O N / O F F model as a special case for each two-state M M P P , which is also known as interrupted Poisson processes ( IPP) . We also assume that the two modulating parameters of each I P P are equal. The superposition of M M P P s is itself an M M P P , and is sufficient to model self-similar behaviour reasonably accurate over four to five time scales [4]. We can describe the i th I P P as follows: Qi = —o~u A,- = \ 0 0~2i -On 0 0 (1 < i < 4) (3.16) where Qi and A* are the transition rate matrix and the arrival rate matrix of the i th IPP , respectively. Aj is the mean arrival rate of each i th I P P when in the O N state. We give one example of the set of source parameters defining the traffic model described above in Table 3.1, wi th overall mean rate, described in E q . (3.19), A = 3 * 10 6 bps and H = 0.75. The interested reader may find the detailed procedure of fitting to an asymptotic second-order self-similarity of the counting process in [4]. Note that the four 2-state M M P P traffic sources are independent. A t O B S edge node, the incoming IP traffic itself is self-similar aggregated traffic, and is demultiplexed at the Chapter 3. Self-Similar Traffic and MMPP Approximation 34 edge shaper according to each FEC in separate queues, based on the destination and QoS requirement. We assume each FEC traffic is also self-similar and can be represented as the superposition of the above four IPPs . The superposition can be described as follows: Q = Qi@Q2®Qz@Qi (3.17) A = A 1 © A 2 e A 3 © A 4 © A p (3.18) where © denotes the Kronecker's sum and Ap is the arrival rate of the Poisson process to be superposed. The mean arrival rate A of each FEC traffic process can be calculated as: We denote the M M P P obtained by the superposition of IPPs as the stochastic process {Nt,t > 0}. This M M P P Nt has an underlying 16-state continuous-time Markov chain which we denoted as {Xt,t > 0} in the previous section, wi th transition rate matr ix Q (3.17) and arrival rate matr ix A (3.18), representing aggregated FEC traffic sources as an input at the O B S edge node, wi th L R D properties. The Markov chain Xt generates the M M P P Nt as Nt = f g'Xsds + mt, (3.20) Jo where the superscript ' denotes vector transpose, Nt denotes the IP packet arrivals that occur during the interval [0,t], and g = [A1,A2,Ai6]' is the vector of intensities of the process Nt and mt is a Poisson martingale stochastic process, which satisfies E { m T | M } = mt, for r > t, (3.21) where J\ft is the observation history of the M M P P Nt, and E { . } denotes the expectation operator. Chapter 3. Self-Similar Traffic and MMPP Approximation 35 Again , since the 16-state worked well for modeling self-similar behaviour over four to five time scales, we choose 16-state for our Markov chain. One example of the transition rate matr ix Q generated from Tabel 3.1 in our simulation is shown below: -0.58 0.00 0.00 0 0.01 0 0 0 0.57 0 0 0 0 0 0 0 0.00 -0.58 0 0.00 0 0.01 0 0 0 0.57 0 0 0 0 0 0 0.00 0 -0.58 0.00 0 0 0.01 0 0 0 0.57 0 0 0 0 0 0 0.00 0.00 -0.58 0 0 0 0.01 0 0 0 0.57 0 0 0 0 0.00 0 0 0 -0.58 0.00 0.00 0 0 0 0 0 0.57 0 0 0 0 0.00 0 0 0.00 -0.58 0 0.00 o • 0 0 0 0 0.57 0 0 0 0 0.00 0 0.00 0 -0.58 0.00 0 0 0 0 0 0 0.57 0 0 0 0 0.00 0 0.00 0.00 -0.58 0 0 0 0 0 0 0 0.57 0.23 0 0 0 0 0 0 0 -0.24 0.00 0.00 0 0.01 0 0 0 0 0.23 0 0 0 0 0 0 0.00 -0.24 0 0.00 0 0.01 0 0 0 0 0.23 0 0 0 0 0 0.00 0 -0.24 0.00 0 0 0.01 0 0 0 0 0.23 0 0 0 0 0 0.00 0.00 -0.24 0 0 0 0.01 0 0 0 0 0.23 0 0 0 0.00 0 0 0 -0.23 0.00 0.00 0 0 0 0 0 0 0.23 0 0 0 0.00 0 0 0.00 -0.23 0 0 0 0 0 0 0 0 0.23 0 0 0 0.00 0 0.00 0 -0.23 0 0 0 0 0 0 0 0 0.23 0 0 0 0.00 0 0.00 0.00 -0.23 36 C h a p t e r 4 T r a f f i c p r e d i c t i o n i n O B S n e t w o r k In this chapter we look at the problem of O B S traffic prediction in the presence of self-similarity. One of the key issues in QoS provisioning in the O B S network is to predict the optical burst length in the next burst assembly time interval based on the online measurements of traffic characteristics. The goal is to forecast future traffic variations as precisely as possible, based on the measured traffic history. Traffic prediction requires accurate traffic models that can capture the statistical characteristics of actual traffic. Inaccurate models may overestimate or underestimate network traffic. Whi l e a certain amount of error is allowable (and expected), the overall predictor is required to be accurate enough so as not to reduce uti l ization in the worst cases. We start from investigating the B H P pre-transmission mechanisms in O B S networks for QoS provisioning, where the LMS-based linear predictor is assumed. We then derive an opt imal prediction algorithm in the M M P P predictor sense and discuss further the implementation aspects of our proposed algorithm. Chapter 4. Traffic prediction in OBS network 37 4 . 1 Pre-Reservation and Linear Predictor As we have introduced that, different offset-time based approaches have been proposed to provide service differentiation in O B S networks. The common purpose is t rying to manage QoS on a class-by-class basis using different extra offset times for different classes of bursts. The basic idea is that by giving a larger extra offset time to a higher priority class, reservation for higher priority bursts can be made far in advance of lower priority bursts and thus have a better chance to succeed. Al though offset-time based differenti-ation is easy to implement and provides efficient isolation between service classes when a sufficiently large extra offset time is assigned to higher priority bursts, the extra offset time introduces an additional delay at the edge. A variation on these approaches is to send the control packet ( B H P ) prior to collecting the entire burst from the upper layers. The main advantage of this variation is the reduction in the burst pre-transmission delay. However, the control packet is sent before the burst is completely assembled; therefore the estimation of burst length is required in the O B S edge node in order to utilize the estimated setup/estimated release scheme. For simplicity, we divide the incoming IP traffic into two classes, i.e., low-priority (delay tolerant) and high-priority (delay sensitive), and apply burst-size prediction for high-priority traffic. Only basic offset time, T0 is considered. That is, the B H P is transmitted r Q t ime units before the data burst so that the B H P can set up a switching path and reserve bandwidth. B o t h classes of traffic use the estimated setup/estimated release scheme. However, the low-priority traffic uses the Just Enough T ime ( J E T ) signaling protocol [19], where the occupation of the resources is exactly from the burst arrival unti l the transmission of its last bit. The B H P is sent after the entire burst is completely assembled and no estimation is made. The bursts s t i l l wait in the queue and w i l l be transmitted to the O B S core after a certain offset time r 0 . We assume that the offset time is short Chapter 4. Traffic prediction in OBS network 38 IP Traffic Predictor BHP Generator BCuV" Classifier Labeled assign label LRD Traffic Burst Assembly BHP ...J. 1—1> Control Channel s. Data Channel Data Burst Ingress Node Figure 4.1: Service differentiation at O B S ingress node wi th traffic prediction and constant (equals to burst assembly time in most cases). Thus the influence of the offset time in the data burst arrival process is only a time shift. This scheme is termed as delayed reservation. For high-priority traffic, we use F R R signaling protocol [7], a so-called advanced reservation scheme, where B H P is sent before the burst is completely assembled, and the estimation of burst length is made by a predictor between the traffic classifier and the burstification control unit ( B C U ) . Figure 4.1 shows this scenario under analysis. A key requirement for successful implementation of F R R is that the B H P needs to have an accurate estimate of the size the data burst. We now briefly introduce how traffic prediction works for bandwidth reservation in O B S networks. The O B S ingress node performs the grouping of a number of small IP packets in variable-size bursts before transmitting them to the optical domain. A s M P L S traffic en-gineering is deployed, the IP packets given same destination address and QoS requirement are classified into one forward equivalent class ( F E C ) and are assigned wi th the same la-bel. The O B S ingress node maintains a separate queue per F E C . The classified traffic of per F E C is assumed self-similar wi th long-range dependence ( L R D ) in property, which is approximated as an M M P P process in the previous chapter. In our system, we use a timer-based non-periodic burst assembly mechanism, described in section 2.1.2. Figure 4.2 depicts how the predictor works while burst assembling. Chapter 4. Traffic prediction in OBS network 39 kdi burst assembly time (k+J)di burst assembly time i r . > * r« > 1^ 1 s t p <k) (k) -(*) ,.(*) ?l ?2 "'•+1 ""W acket of kth burst 1 ^ pa cket of burst ( A time unit 5 t Prediction of the (k+l)th burst Send burst send BHP Figure 4.2: Timer-based burst assembly wi th prediction Assume the A;th burst has been transmitted down the optical network, and let r 1 f c + 1 ^ denotes the arrival time of the first new IP packet, which w i l l be assigned to the (k + l ) t h data burst. U p o n a timeout expiration, the burst is framed and relayed for transmis-sion. A s a result, the burst assembly time r a is kept wi th in the timeout value, which is independent of network load. O n the other hand, prior to burst transmission, a control header ( B H P ) , wi th burst label, predicted burst size, etc., has to be released to reserve the necessary bandwidth at each intermediate node in the O B S core network. A s shown in Figure 4.2, the B H P is sent at the time r x ( f c + 1 ) + r a - A , where 0 < A < r a . The number of packets arriving during the time interval A is not known at this time, so the B H P needs to predict the number of packets arriving from r f + 1 ) + r a - A to r[k+l) + ra in order to specify the reservation duration. A is termed as prediction interval in traffic prediction, and in our case A is physically equal to offset time r 0 . Vary ing A is a way of service differentiation for different QoS requirements. Since we only consider two classes of traffic in our system, we can simply choose A = ra. Tha t is, we predict the (k + l ) t h burst size at the time its first packet arriving. It is usually difficult to make a prediction algorithm practical, while accurate and ef-fective, especially for the self-similar traffic. Among these widely used estimations derived from a mean square error based method, linear predictive filter ( L P F ) adopted in [7] is Chapter 4. Traffic prediction in OBS network 40 the simplest one. Before deriving the Bayesian predictor we first briefly outline the linear prediction method for predicting burst size. W i t h the knowledge of the burst length of the last N bursts, (Lfc_/v, .. . ,Lfc), the length of the next incoming burst L^+x could be expressed as a linear combination of the lengths of the previous N bursts by: N Lk+i = ^2w{i) • Lk-i+i (4.1) i=\ where w(i),i € {1, ...N} are the coefficients of the linear predictor. These are typically updated by an adaptive filtering type algorithm such as the normalized L M S (Least Mean Square) algorithm [35]. Another benefit of using L M S is that there is no need to know the underlying structure of traffic. A control header makes an advanced resource reservation according to the predicted value. If the prediction is optimal, the predicted value should be equal to the actual incoming burst length. Ana lyz ing the performance of prediction techniques and the pre-dictabil i ty of network is an important study in the O B S network. The quality of a prediction depends on the amount of uncertainty that accompanies the prediction, and mathematically this is measured by the variance of the prediction error. We modelled the L R D traffic as Markov Modulated Poisson Process ( M M P P ) , which matches correlation lags over four to five orders of magnitude. The linear predictor compute only a moving average of the N past burst lengths. A major deficiency is that it does not use knowledge about the M M P P structure to predict the burst length. We now introduce an optimal (conditional mean) Bayesian prediction algorithm for predicting the O B S burst size when the traffic is for L R D traffic approximated by an M M P P model. Bayesian estimation is opt imal in the sense of minimum-variance. Chapter 4. Traffic prediction in OBS network 41 4.2 M M P P Bayesian Predictor In the previous chapter, we introduced a 16-state M M P P model as a superposition of four independent 2-state M M P P s for modelling O B S incoming traffic in finite time scales. We now derive a recursive Bayesian predictor based on this M M P P model, which calculate a new estimate for each time-step, based on the previous estimate and new measurements. Recursive Bayesian estimation works by simulating the process, while at the same time adjusting it to account for new measurements, taken from the real process. For simplicity, we assume IP packet sizes are fixed in our system, i.e., equal, and the burst length is measured in the number of packets in the burst. A s we introduced in section 3.3, in a state space model, for each F E C , let the classified IP traffic be rep-resented as M M P P Nt process, i.e., Nt denotes the number of IP packet arrivals that occur during the interval [0,t\. A n d let J\ft denote the M M P P observation history, i.e., the times of arrivals of al l the packets up to time t. (Note that the observation history can be defined more rigorously in measure theoretic notation in terms of sigma algebras.) Given the observation history M i.k+i), our a im is to predict the (k + l ) t h burst size Lk+i, i.e., the number of IP packet arrivals in the time interval [r[k+1\ r[k+1^ + r j . The best prediction of Lk+\ can be derived by the Bayesian estimation algorithm, i.e., computing E { L f c + i | A / " r ( f c + i ) } , which is the minimum mean square error ( M M S E ) estimate. In order to derive the Bayesian predictor for the burst length Lk+i, it is first necessary to derive the optimal state estimate Xt of the underlying state of the 16-state continuous time Markov chain {Xt}, w i th transition rate matrix Q and arrival rate matrix A = diag[\i, A 2 , A 1 6 ] , at the time t given the observation history J\ft. Namely, Xt = E { X t | M } , (4-2) Chapter 4. Traffic prediction in OBS network 42 where E{.} denotes the expectation operator. This Bayesian estimation is essentially a continuous-time Hidden Markov Mode l ( H M M ) , which can be represented in Martingale formulation as: Xt = X0 + / Q'XTdr + Mt, (4.3) Jo where' Mt is a martingale wi th respect to the filtration generated by X . For a brief intro-duction of the concept of martingale theory see [36, Appendix B] . Then dXt = Q'Xtdt + dMt. (4.4) Given the observation history J\ft, the estimation Xt (4.2) is obtained v i a the so called M M P P filter as follows: = ^ i e * M (4-5) where the un-normalized filtered density qt (which is a 16 dimensional vector wi th non-negative elements) is computed by the following Zakai equation [36]: dqt = Q'qtdt + (A - I)qtdnt (4.6) where nt = Nt — t. qt = qo+ [ Q'Qrdr + (A - I)qTdnT (4.7) Jo Note that the above integral involving dnT is Stieltjes integral. Recal l dnt = dNt — dt and dNt = 1 if an IP packet arrivals at time t, and is zero otherwise. The derivation of the above M M P P filter equation (4.7) appears in [37] [38]. A s shown in Figure 4.2, let r-k\i = 1 ,2 ,n(k) denote the packet arrival times of Chapter 4. Traffic prediction in OBS network 43 M M P P Nt. Then (4.7) can be writ ten as Qt = 9o+ / (Q' ~ A + I)qrdT + (A - / ) V 9T(*,_, •/o f r r * (4.8) r 4 ( f c , < t where T-^ — denotes the time just before the IP packet arrival at time r-k\ This leads to the following exact implementation: For r-k^ <t< r-k\, qt = exp ( Q ' - A + / ) ( r - r , (4.9) Tha t is, qt evolves deterministically between two successive IP packet arrivals. A t the packet arrival time t = r^k\, q <*) is updated as Ti+1 q (k) = Aq ik) _ , Ti+i  Ti+i (4.10) Therefore, q <k) can be updated just at each packet arrival: q ik) = A exp r i + l ( # - A + /)(T#-7i<*>) (4.11) Note ( r^{ — r ^ ) is the packet interarrival time of the fcth burst. F rom this equation, it also follows that the optimal predicted state estimate of the 16-state Markov chain Xt given the observation of M M P P Nt up to time r , r < t can be computed as: Xt = E{Xt\Nt} ? t | T E"I9*|T(*)' A exp ( Q ' - A + / ) ( i - r ) (4.12) (4.13) Given the above M M P P filter (4.7) and the predictor (4.13), we can now derive the Bayesian predictor for the (k + l ) t h burst. Recal l that our a im is to predict the (k + l)th Chapter 4. Traffic prediction in OBS network 44 burst size at the time its first packet arrival r[k+1\ since we set the prediction interval A as the burst assembly time r Q . We shall use the following representation for E q . (3.20): N t = f g ' X s d s + mt. (4.14) J o Then the M M S E (conditional mean) predicted number of packets arriving in the interval / (fc+i) (k+i) _j_ g j y e n tfiQ observation history J\f (jt+i) is: Lfc+i = E ( / ^ + 1 ) g ' X t d t + d m t \ M T ^ } (4.15) = E { / 5 'X t dt |A/" T ( f c + i )} + E { m r ( f c + i ) + A - m ^ + u l A / ^ + u } (4.16) / • ^ i ( f c + 1 > + A = / 5 ' E { X t | A ^ ( f c + 1 ) } d i ( 4 - 1 7 ) ' g ' X ^ + 1 ) d t . (4.18) r , ( f c + 1 ) + A (fc+i) l where the equality (4.17) follows the property of martingales stated in equation (3.21). Final ly , substitute X^k+i) w i th E q . (4.12) and (4.13) in E q . (4.18), we can get the following Bayesian predictor for the (k + l ) t h burst size: In the O B S system, since this prediction interval A is referred to as burst assembly time, which is usually preconfigured as a system parameter at the network design stage, the integral of matrix exponential in E q . (4.19) can be precomputed, while the update of qT involves a matr ix vector multiplication of complexity 0 ( 1 6 2 ) . This predictor can be implemented numerically by suitable discretization. Chapter 4. Traffic prediction in OBS network 45 However, in the case of a threshold-based mechanism is adopted for burst assembly, the burst is framed when the maximum burst size is reached. Therefore, the burst length is fixed while burst assembly time is varying. We can use the same prediction algorithm to predict the burst assembly time, and determine when to begin a reservation. In order to facilitate the solution of E q . (4.19), let n = t-Tl (fc+i) Then we have (4.20) If we define (4.21) the matrix exponential approximated by <& series expansion $ = e^i = i + Q>v + (Q'v)2 , (Q'V? + ... (4.22) 2! 3! can also be writ ten as: $ = / + Q'nV, (4.23) where Chapter 4. Traffic prediction in OBS network 46 1 M a t r i x 7 <— Identity 2 M a t r i x $ « - 7 3 A; <— 25; Comment: we are using AT = 25 in (4.25). 4 If k = 1, go to step 5 M a t r i x * = 7 + 6 fc = /c - 1 7 Go to step 4 8 M a t r i x r *- ^n 9 M a t r i x $ = 7 + Q'r?* Table 4.1: Program logic to compute $ and Y for simple case, eg. N = 25 The T integral in (4.21) can be evaluated term by term to give Q'k4k + 1) r = E fc=0 oo = E (fc + l ) ! (Q'nf = ^n •n (4.24) We evaluate \f by a series in the form 7 + f ( 7 + ^ ( - 7 V - 1 1 + TV J j j ' (4.25) which has better numerical properties than the direct series of powers. We then find Y from (4.24) and $ from (4.23). B y comparing to the direct computation of the matr ix exponential, we choose N = 25 here as an approximation. Then the program logic for computation of <J> and Y is given in Table 4.1 Due to the imperfection of a predictor, an estimated length may turn out to be smaller or larger than the actual burst duration. A smaller burst length prediction wi l l result in insufficient reservation on the path holding time for the data burst. This wi l l cause burst drop at the intermediate node on the path in the core network. So, we compare Chapter 4. Traffic prediction in OBS network 47 the predicted value and the actual value at the edge node when the burst assembly is finished. W h e n the smaller prediction happens, it requires the B H P to be re-transmitted after the burst assembly finishes, thus degrading the latency reduction performance. C h a p t e r 5 48 P e r f o r m a n c e A n a l y s i s a n d S i m u l a t i o n R e s u l t s In this chapter we present several simulations to illustrate the Bayesian M M P P predictor and its effect on the latency reduction and burst blocking probabili ty of the O B S network. The input traffic is assumed to be self-similar wi th L R D properties. The simulation platform is O P N E T . 5.1 Model Setup This section describes how an O B S network model has been implemented in O P N E T Modeler 9.1. In general, section 5.1.1 briefly describes our network methodology; in sections 5.1.2, we give a detailed introduction on how to develop our M M P P traffic models in O P N E T ; in section 5.1.3 and 5.1.4 we focus on the functionality and system parameters set up on the O B S edge node and core node, separately. 5.1.1 Optical network architecture We use the optical network architecture in Figure 5.1, which is similar to [39]. Chapter 5. Performance Analysis and Simulation Results 49 Figure 5.1: O B S network structure 1. The network consists of a core part ( O T N ) a n d an external part (optical edge routers), where control channel and data channel are separated. 2. Core network ( O T N ) consists of a fully connected mesh of four optical cross connects ( O X C s ) , wi th full wavelength conversion. 3. Network edge routers are capable of aggregation and de-aggregation of IP packets. 4. The network supports two classes of traffic. 5.1.2 Traffic generator The generator node must generate packets, process them, and send them on to the point-to-point transmitter. This can be modelled using a traffic source processor to generate packets, another processor to perform any necessary operations, and a point-to-point transmitter to transmit the packets on the point-to-point link. This node structure is shown in Figure 5.2, where the "src" module generates M M P P traffic and the "proc" Chapter 5. Performance Analysis and Simulation Results 50 5 ^ m src proc Figure 5.2: Traffic generator node xmt field name type size comments dest .address integer 32 bits egress address QoS integer 8 bits Qos class Table 5.1: IP Header format module specifies other information, such as destination address, QoS requirements etc. "xmt" is simply the point-to-point transmitter. For simplicity, the IP packet header contains only information needed in our experiment, as shown in Table 5.1. Recal l that in our simulation, the traffic model for each F E C is a 16-state M M P P process, which is mathematically computed by superposing four 2-state M M P P s in section 3.3.2. The structure of this M M P P traffic generator is shown in Figure 5.3. Simulation results validate that our 16-state M M P P model is good at modelling self-similar traffic in four to five time scales. Therefore the traffic generated from the above source processor has the property of long-range dependence ( L R D ) in four to five time scales. 5.1.3 Edge router The main role of edge routers in the O B S network is to provide packet transmissions between the optical domain and the electrical domain. There are two types of edge routers, i.e., ingress and egress routers. The one transmitt ing packets from the electrical domain to the optical domain ( O T N ) is referred to as ingress router, and vice versa. Edge routers also implement O B S M A C layer functions between IP and optical layer. Chapter 5. Performance Analysis and Simulation Results 51 Figure 5.3: M M P P traffic generator - the a im of this figure is to illustrate the transactions between this 16-state M M P P • K e y functions of O B S M A C layer at the ingress router are: 1. Classify the incoming IP packets based on their destinations and QoS class into different F E C classes. Later, optical burst wi l l be generated from each F E C queue. The optical burst structure is shown in Figure 5.4. 2. For different classes traffic, service differentiation is provided. For high-priority traffic, a predictor is inserted to predict the burst length before it has been fully assembled. In this case, the offset time r 0 between B H P and the data payload is equal to the burst assembly time r 0 . Then B H P contains the above information and routing information (label) is launched, and will-be sent out directly after it has been generated. For low-priority traffic, the B H P is generated after the burst assembly is finished, so the B H P contains the exact knowledge of Chapter 5. Performance Analysis and Simulation Results 52 data HJ IP packet "^X Payload data H data H H B u r s t — • Burst size Offset time Cos Wavelength ID Label Control Header Packet Figure 5.4: O B S burst structure field name type size comments label integer 32 bits M P L S routing information waveJd integer 8 bits for outport wavelength reservation class integer 4 bits setting F E C class for Qos requirement offset_time integer 32 bits offset time between B H P and burst num_pk integer 8 bits number of packet of a burst burst .size integer 32 bits actual burst size Table 5.2: Burst Header Packet ( B H P ) format the burst length. However, the assembled data burst has to be queued in the ingress for a preconfigured offset time r 0 , which is set to the total path set up time in the core network. A B H P format is shown in Table 5.2. 3. Frame the burst after the offset time has elapsed and send the burst into the optical layer. A burst is set to be at least several kilobytes long in order to be comparable wi th the real O E O time needed for its header to set up a switching path, which is presumed to be in the range of microseconds. Usually a burst consists of several tens to hundreds of IP packets and the assembling time is also in the range of hundreds of microseconds (ps) to several milliseconds ( m s ) . 4. Support two interfaces for input and output on the O T N side as well as the terminal workstation side. 5. The ingress router processor has a switching table, for example, Table 5.3, Chapter 5. Performance Analysis and Simulation Results 53 which is used to forward the optical bursts on a particular output stream on an output port. Dest. address Dest.egress Dest.port Dest.wavelength 0 1 0 0 1 2 1 0 Table 5.3: Edge router switching table The node model of an ingress router is depicted in Figure5.5, where the "aggregate" module performs the above functions, and the control channel is separated from those data channels at the electrical to optical interface. It also shows that the ingress node supports four data channels (wavelengths) at each out port. p r _ l txl_BHP Figure 5.5: Ingress node model (pr_0 and pr_ l are inports; t xOJ3HP and t x l J 3 H P are outports for B H P ; pt_0 and p t_ l are outports for data burst, each wi th 4 wavelengths) K e y functions of O B S M A C layer at the egress router are: Chapter 5. Performance Analysis and Simulation Results 54 1. Deframe the bursts and extract IP packets from them. 2. Look up the final destination for al l the workstations connected to it. 3. The egress router processor also has a global forwarding table, which is used to look up the final destinations directly connected to the egress router. Egress address Dest. address Dest.port 1 0 2 2 1 2 Table 5.4: Edge router forwarding table 5.1.4 Core Router(OXC) A simplified architecture of a core node wi th 4 input /output links is represented in Figure 5.6. There are 8 inputs and 8 outputs, each represented by a point-to-point receiver and transmitter, respectively. Four of the receivers and transmitters have four channels, witch represent 4 data W D M channels. The other receivers and transmitters are single channel and represent the B H P channels on each link. Thus, each combination of B H P transmitter and receiver, and 4-channel data receiver and transmitter represents the connection to a fibre link to an edge node or other intermediate core node. A l l of the receiver/transmitter components are connected to a central process model S C U (switch control unit) v i a packet streams. The S C U is responsible for: 1. reading switching information from a precomputed M P L S - t y p e label information table (LIB) 2. swapping input and output labels Chapter 5. Performance Analysis and Simulation Results 55 rxO BHP r x l BHP o t 2 BHP rx3 BHP txO BHP t x l BHP tx2 BHP tx3 BHP Figure 5.6: O B S core node structure 3. calculating new offset times 4. performing wavelength conversions 5. making resource reservations for corresponding data bursts 6. reassembling B H P wi th new necessary information 7. relaying optical bursts to output ports according to the switching table 8. implementing optical output buffers needed for each outgoing burst In the process model, decisions are made depending on whether a B H P or a data burst is received. W h e n a B H P is received, al l of its information is extracted to the S C U . Here Chapter 5. Performance Analysis and Simulation Results 56 the control packet is transformed to the electrical domain. In the electrical domain, the following actions take place: • The label in the B H P is used to point to the data burst forwarding information in the L I B , such as the output interface and Qos information. • Information in the B H P about burst length and the offset time of the data burst is used in addition to the forwarding information derived from the L I B . In particular, the latter is used to determine the mapping from the incoming fiber and wavelength to the outgoing fiber and wavelength. To be able to forward successive data bursts of the same connection (LSP) on different wavelengths in a given fiber, we pro-pose that the label specify only incoming-fiber-to-outgoing-fiber mapping, while the information about the wavelength be appended to the outgoing label at every hop. • The S C U determines burst outgoing fiber by looking up its precomputed L I B , and makes wavelength reservation on designated output port, which supports full wave-length conversion. Then the cross-connect is set up to switch the data burst corre-sponding to that control packet in the all-optical domain. • B y recalculating a new offset time, the B H P is reassembled wi th new necessary information and undergoes label swapping (and wavelength information appending) and is forwarded on the dedicated control channel of the outgoing fiber as indicated by the L I B . Thus the O E O transformation is finished. If, on the other hand, a data burst is received, a check is made wi th the S C U to extract the next hop of the burst. The data burst is transmitted transparently in the pure optical domain. Table 5.5 is an example of a label information table for label switching. In this simulation, we use one-way reservation scheme. That is, the sender of a burst Chapter 5. Performance Analysis and Simulation Results 57 Input Output Port Wavelength Labe l Port Wavelength Labe l 0 0 20 0 0 27 0 1 21 2 0 24 0 2 22 0 0 30 0 16 23 2 0 21 1 3 25 0 1 28 Table 5.5: Information Base (LIB) at Core Node does not wait for a positive acknowledgment ( A C K ) of its reservation request. The ad-vantage of one-way reservation is higher efficiency, as there is no overhead caused by the propagation delay. This scheme is appropriate because O B S wi l l most likely be im-plemented in long-haul networks and therefore the one-way reservation w i l l significantly decrease the time needed to establish a connection. A n example may illustrate this. The transmission time of a 100KB burst on a lOGbps link is 80/xs while the propagation delay over a distance of 200km (which is not long in a backbone network) is typically about 1 ms. 5.1.5 Buffer at routers • Electronic buffers at each ingress router for packets aggregation purpose are repre-sented by a single server F I F O queue per F E C . • Opt ica l buffers (FDLs) are fixed for each label and should be allocated among al l classes. A group of F D L s wi th variable length can act as the F I F O queue. Chapter 5. Performance Analysis and Simulation Results 58 5 . 2 S i m u l a t i o n E x p e r i m e n t s a n d R e s u l t s In this section, we first compare the LMS-based linear predictor wi th our proposed M M P P Bayesian predictor based on the prediction quality. We then show the performance im-provement in terms of E T E delay and burst blocking probabili ty when applying our M M P P predictor. 5.2.1 Assumptions • A l l sources of data from upper clients are assumed to be self-similar traffic. A superposition of four 2-state M M P P s are used in this simulation to represent the aggregated self-similar traffic of each F E C at the O B S ingress nodes. • IP Packet size is fixed in each scenario. • Packets wi th the same destination address and QoS requirement belong to one Forward Equivalent Class ( F E C ) . • Assume M P L S is used to set up a lightpath and to reserve bandwidth for each source-destination pair (SD). Each Labe l Switching Pa th (LSP) is identified wi th a label and can be transmitted v i a more than one channel. • Fu l l wavelength conversion is assumed at each core node. • Opt ica l buffers are allocated on a per-class and per-label basis, according to the incoming traffic intensity and priority. • Traffic from different sources may share the same label, provided they are destined for the same egress. Chapter 5. Performance Analysis and Simulation Results 59 5.2.2 P red ic t ion performance improvement We first study the L R D traffic prediction performance by comparing two prediction meth-ods: simple LMS-based predictor [7] and our proposed M M P P Bayesian predictor. Figure 5.7 shows the probability density of the prediction error for both our proposed M M P P Bayesian predictor and the traditional LMS-based linear predictive filter ( L P F ) . It is ob-vious that the LMS-based L P F has larger prediction error variance in comparison wi th our M M P P Bayesian predictor. Recall that the Bayesian estimation algorithm is optimal in the sense of minimum variance. Note that the error in this figure is un-normalized. • • mmpp 4 0 u s m mmpp~200us mftvpp_lrfts * • l m s _ 2 n s l m s ~ 4 0 u s l ruapp_400us * • l m s _ 2 0 0 u s l m s _ 4 0 0 u s mnipp_2ms 0 . 0 0 0 0 8 0 . 0 0 0 0 ? 0 . 0 0 0 0 4 0 . 0 0 0 0 2 . 0 0 0 0 1 . 0 0 0 0 0 0 . 5 1 . p r e d i c t i o n e r r o r ( b i t s ) ( x lOOOOO) Figure 5.7: P D F of prediction error(in bits) Chapter 5. Performance Analysis and Simulation Results 60 Let Lk+i be the predicted burst length and Lk+i be the actual burst length. The performance is further evaluated by the following two criteria. Firs t is the prediction interval, which refers to how far into the future the traffic can be predicted wi th confidence. Define the normalized A-step prediction error as: E(A) = l ^ + i - ^ + i I. (5.1) Lk+i Assume that confident prediction requires that E(A) should not exceed a percentage e (e.g. 20%) wi th a probability Pe (e.g. 0.01), where {P£,e) is the specified prediction confidence interval. Therefore, a large prediction confidence interval implies good traffic predictability. Now, if we define P e = P{E > e}, we can compare the performance of two predictors on how confidently and how far they can predict the future. Figure 5.8 compares the simulation results of P£ vs. prediction interval A . The simulation results show that Pe of M M P P predictor grows much slower then L P F when the prediction interval A increases. Furthermore, the M M P P predictor can bound the confidence pair (P£,e) as (0.012,10%) and (0.008,20%) when A approaches 3ms, which is usually sufficient for assembling optical bursts. Signal-to-Noise Rat io (SNR) is another criterion for evaluating the prediction perfor-mance, which refers to the accuracy of a prediction algorithm. Now denote S N R as: SNR(A) = E [ L 2 + 1 ] / 4 , ai = E[ (L f c + 1 -L f c + 1 ) 2 ] , (5.2) where A is the prediction interval, and a\ is the A-step prediction variance. The larger S N R implies the better prediction accuracy. In our thesis, we use the inverse of S N R , i.e., Chapter 5. Performance Analysis and Simulation Results 61 >> !5 ns o 0.05 0.045 0.04 0.035 0.03 0.025 0.02 0.015 0.01 0.005 LMS predictor E= 10% LMS predictor E = 20% MMPP predictor e = 10% - A J i - - . MMPP. predictor, E .=. 20% 500 1000 1500 2000 Prediction Interval A (us) 2500 3000 Figure 5.8: Comparison of Pe under prediction error e = 10%, 20% S N R 1 for comparing the above two prediction methods. Namely, S N R - 1 = E [ ( L fc+i Lk+i)2 (5.3) S N R - 1 is usually influenced by the parameters such as burst assembly duration T q , i.e., prediction interval, and traffic load p, since increasing traffic load implies increasing of hurst parameter H (the traffic bursty degree). We conduct a set of simulations by tracing the dependence of S N R - 1 on the above two parameters, respectively. Figure 5.9 shows the effect of burst assembly duration. In this scenario, we set the other parameters as p = 25% and H = 0.75, since the bandwidth uti l izat ion of today's optical network is typically under 25%. Figure 5.10 compares SNR 1 wi th the variation of traffic load in the core network. Chapter 5. Performance Analysis and Simulation Results 62 SNR 1 versus burst assembly time x rr CD a) > 18 16 14 12 10 8 - 6 0 1.5 ••A-- MMPP predictor -©• • LMS predictor load = 25% H = 0.75 ,« p / / O / / / / '/ 6 / / / / / 1.. o -. ^ . A - - A " ~" • ~~ £ . J. ^  A • — ^ ^ 2.5 iog 1 0 T A (us) 3.5 Figure 5.9: SNR versus burst assembly time r a In this scenario, we consider small assembly time ( r a = 200ps) and large assembly time ( r a = 2ms) cases, respectively. Aga in , smaller S N R - 1 implies better prediction accuracy. For our M M P P predictor, Figure 5.9 shows that ( S N R - 1 < 1%) is achieved when the burst assembly time r a is between lOO^xs to 1ms. Meanwhile, as r a grows to 3ms, the S N R - 1 is kept wi th in 2%. O n the other hand, the S N R - 1 of the LMS-based predictor increases dramatically when r a grows from tens of microsecond to the time scale of millisecond. This is because the traffic behaves long-range dependence over several time scales while the burst is in assembling. It is inherent in the fact that L M S algorithm converges and adapts to sudden changes is slower. In this scenario, it also yields the average accuracy improvement of M M P P predictor over L M S predictor as 87%. From Figure 5.10 we observe that S N R - 1 Chapter 5. Performance Analysis and Simulation Results 63 S N R versus traffic load in core network - A - M M P P predictorT a=2ms -o - M M P P predictor Tg=200ns - 0 - L M S predictor Tg=2ms _ ^ L M S predictor-ra=200ns i 5 _ — (>- — -•€ ~ — f: .... *- - ' ~~ ~ ~ 5 <> <! - • - < > < > < > 0I I I I I 1 _ _ J 20 30 40 50 60 70 80 Core network traffic load% Figure 5.10: S N R 1 versus traffic in core network of M M P P predictor almost remains constant while increasing traffic load. This is because the M M P P predictor has the knowledge of incoming traffic structure, which is independent of traffic load. However, the LMS-based predictor behaves different when feeding traffic becomes heavier. In the case of small assembly time applied, S N R - 1 is decreasing while traffic load increasing. This result indicates that when many source traffic aggregated, the aggregated traffic turns out to be smoother in very short time scales. Now we look at larger time scales, i.e., the case of large assembly time applied. S N R - 1 is increasing wi th the traffic load since the traffic bursty degree also grows, which can not be shaped away at this burstification range. Chapter 5. Performance Analysis and Simulation Results 64 5.2.3 B H P pre-transmission success probability In our system, a successful B H P pre-transmission means sufficient bandwidth is reserved before burst data arrives at each intermediate core node. That is, a smaller prediction of burst length: e(k + l) = {Lk+1-Lk+l)<0 (5.4) w i l l result in an insufficient reservation of the path-holding time for the data burst. This requires the control header to be retransmitted after the burst assembly finishes, thus degrading the latency reduction performance. A common method for correcting this problem is to add a small correction margin for the predicted value. Instead of making the reservation length the predicted value Lk+X, we define the reservation length as: Lr{k + 1) = Lk+1 + S (5.5) where 8 is a small margin of correction. Let Ps denote the probability of success B H P pre-transmission: Ps = P{e{k + 1) < a}, a = max{a,S}, . (5.6) where a is the variance of prediction error e(k + 1). Here the constraint a indicates that the prediction error overhead is ' l imi ted in our system. Figure 5.11 shows the B H P pre-transmission success probabili ty versus burst assembly time r 0 . Since Ps depends largely on the correction margin 5, we also compare the results of Ps w i th 6 variations. Based on the central l imited theorem, the prediction error e(k + 1) is assumed to be normal, wi th zero mean and variance a2. For al l normal distributions, the density function is symmetric about its mean value. Abou t 68% of the area under the curve is wi th in one Chapter 5. Performance Analysis and Simulation Results 65 standard deviation of the mean, 95.5% within two standard deviations, and 99.7% wi th in three standard deviations. Therefore, we only need to consider the correction margin: 5 = na, n e [ 0 , 3 ] . (5.7) From Figure 5.11, we notice that the B H P pre-transmission success probability could be highly improved wi th a small amount of correction value. 100 Q. m in CD O O 3 Cfl c o 'in if) 90 Q_ >. 80|-!n to - Q o B H P prelransmission success probability with LRD traffic in c (0 Q. 70 60 h S 50 40 30 20 l 1 M M P P predictor 8 = 2o M M P P predictor 5 = a \ v . . . A * : J L M S predictor 8 = 2rj ; LMS predictor 8 = a ; LMS predictor 8 = 0 500 1000 1500 2000 2500 3000 aggregation time (us) Figure 5.11: Comparison of Ps versus burst assembly time r a 5.2.4 Latency reduction improvement Now we can study how prediction accuracy and efficiency influence the system end-to-end ( E T E ) delay at edge routers. We consider first low-priority traffic without burst length Chapter 5. Performance Analysis and Simulation Results 66 edge node Packet arrival Bandwidth allocator edge node Packet arrival Bandwidth allocator No prediction With prediction Figure 5.12: Comparison of O B S network wi th /wi thout Predict ion prediction in the O B S edge routers. In this scenario, we use a one-way reservation protocol such as J E T [19]. A t the edge node, packets wi th the same F E C class are aggregated into a container. W h e n assembly time is over, i.e., when r a expires, the B H P is made and sent out to the core network immediately, while the container is framed to a burst and stored in the edge node, and wi l l be sent when the determined offset time expires. The E T E delay Dn = + T o + Tu (5.8) where rt is the total transmission time of data burst throughout the designated L S P . The offset time r 0 is set to be the total O E O time + switching setup time at each intermediate node through the designated L S P in the core network. For high-priority traffic wi th burst length prediction, we can dynamically reserve suf-ficient bandwidth at the O B S core network. In this scenario, we also use a one-way Chapter 5. Performance Analysis and Simulation Results 67 reservation protocol, such as F R R , proposed in [7], which is a variation of J E T that focuses on delay deduction. The edge nodes determine all the routing and reservation information before the entire burst is assembled, then make and send the control header ( B H P ) immediately, while the burst is s t i l l being assembled. The burst assembly wi l l be finished when the preconfigured assembly timer r a expires. However, the knowledge of the burst length has been predicted at the arrival of the first packet of the burst. Simulation results show that the latency deduction value achieves the maximum when r 0 is set to the same as r a [7]. It is quite straightforward that the assembly time is saved when r 0 = r a , as shown in Figure 5.12. Therefore, wi th prediction, the E T E delay: Dp = l~Ta • Ps + (^Ta + T0) • (1 - P.) + Tt. (5.9) For r 0 = Ta, E q . 5.9 can be rewritten as: Dp = (^-Pa)-Ta + Tt. (5.10) In the O B S network, we observe that the bandwidth in the core network (OC192 or more) is much higher'than that in the edge network (OC3 to OC48) . The time for assembling a burst, which is usually in the hundreds of microsecond, and is comparable wi th the O E O time. The transmission time in the core network is usually in the time scale of several microseconds, which could be negligible to the assembling time. When pre-transmission probabili ty Ps achieves 1, the system end-to-end delay is Dp = | r 0 . The latency improvement (77) could be expressed by Chapter 5. Performance Analysis and Simulation Results 68 If the burst length could be predicted precisely such that the pre-transmission of the B H P succeeds wi th a high probabili ty (Ps —> 100%), the edge could reduce the latency by 66% when T0 = ra, and transmission time is negligible. ETE delay with/without prediction 4 5 0 0 -4 0 0 0 -3 5 0 0 -3 0 0 0 -CO >, 2 5 0 0 -to 03 ° U LU 2 0 0 0 -H LU 1 5 0 0 -1 0 0 0 -5 0 0 -0 -s r s / ,<* s / / / / , S „ ' ' „ 9 " < -+- LMS predictor -0- No predictor " 0 2 0 0 4 0 0 6 0 0 8 0 0 1 0 0 0 1 2 0 0 1 4 0 0 1 6 0 0 1 8 0 0 2 0 0 0 aggregation time (us) Figure 5.13: Comparison of E T E delay wi th /wi thout Predict ion In our simulation, we calculate the actual E T E delay by also considering the transmis-sion time through the light path, since the transmission time should not be ignored in a complicated network. A n example may illustrate this. The transmission time of a 100KB burst on a 10 Gbps link is 80yus. A s shown in our fully meshed network structure, optical burst usually undergos several hops in the core network. So the accumulated transmission time might be comparable to burst assembly time. Figure 5.13 compared the overall E T E delay wi th no prediction, linear prediction, and our M M P P prediction. The simulation result shows that our proposed M M P P predictor can improve the performance of E T E delay about 30% ~ 35% compared to a tradit ional linear predictor, wi th a relatively larger Chapter 5. Performance Analysis and Simulation Results 69 prediction interval, and around 50% compared to the situation without predictor. 5.2.5 Effect on Burst blocking probability Comparison of burst loss probability O ID in o .a CD > O I 1 I ! : _ -() I ^ - " JS _ . i •A- • MMPP predictor -o- LMS predictor wavelength = 4 H = 0.75 x = 1ms a i 25 30 35 40 45 50 55 60 65 70 Core network traffic load% 75 Figure 5.14: Comparison of burst blocking probabili ty wi th different predictor In the O B S system wi th its one-way reservation scheme, if the requested bandwidth is not available, the burst is said to be blocked and dropped. A s a burst may contain several user packets, the loss of a burst is cri t ical in O B S networks, which may incur severe problems at upper layers, e.g., T C P packets out of sequence. The performance of O B S networks in terms of burst blocking probability has been studied extensively [40] [41] using either simulation or simple analytical models. Burst blocking probability is influenced mainly by traffic load, traffic chrematistics, and number of wavelengths, as discussed in [42]. Chapter 5. Performance Analysis and Simulation Results 70 Figure 5.14 compares two predictors for the following criteria: burst loss ratio, also called burst blocking probability. In our simulation, we mainly consider the L R D traffic wi th H = 0.75 and our system support full wavelength conversion for only 4 wavelengths. So the blocking probability is higher in comparison to more wavelengths cases. The simulation results validate that, wi th a more precise prediction of the burst length, the burst loss ratio can be highly decreased. 71 C h a p t e r 6 C o n c l u s i o n a n d F u t u r e W o r k 6.1 Conclusion This thesis studies optical burst switched (OBS) networks, Internet IP traffic modeling at the O B S edge networks, and on-line burst size prediction for dynamic bandwidth reservations. • Firs t , this thesis presents a detailed analytical model for the burst shaping (assem-bly) , scheduling and wavelength reservation schemes for O B S networks. Though there has already been research on this subject, the models proposed in this thesis are more viable and valid for general burst length and offset length distributions. QoS differentiation is facilitated at network edges. • In the second part of the thesis, special attention has been paid on traffic modeling for self-similar Internet traffic wi th long-range dependence ( L R D ) properties. The incoming IP traffic at O B S ingress nodes is approximated by using the superposi-t ion of several M M P P s . We find that, under reasonable assumptions regarding the system parameters of burst assembly, i.e., burst assembly time and O E O time-scales in optical switch and electronic hardware, the performance of our traffic model us-ing the superposition of four 2-state M M P P s seems to get close to that of more Chapter 6. Conclusion and Future Work 72 complicated F B m and F G n . That is, it is practical sufficient to model L R D traffic properties in several time scales. • Last but not least, a recursive Bayesian (optimal) filtering/prediction method is proposed to predict optical burst length at the O B S ingress node. For IP traffic ap-proximated by a N-state M M P P , the computational complexity is 0(N2). B y this burst length prediction, burst control header ( B H P ) can be transmitted down to the core network before burst assembly is completed, thus greatly reducing burst assem-bly delay at the edge node and further facilitating the service differentiation based on QoS requirements among different classes. Simulation studies are presented to i l -lustrate the performance of our proposed predictor in comparison to earlier proposed LMS-based linear predictive filter. Theoretical analysis and simulations exhibit en-couraging results. The performance study indicates that, the recursive Bayesian predictor delivers excellent forecasting performance for the self-similar traffic which best models the Internet traffic, and is proved to be practical in reducing the data burst delay at network ingress routers of an O B S system. 6.2 Extensions Several issues remain open and are worthy of further investigation to generalize our pre-diction scheme and to unleash the potential of QoS provisioning for the O B S system. For example, the proposed Bayesian predictor is an on-line optimal (minimum-variance) predictive filter, which provides an optimization of the burst-length prediction. However, there are two disadvantages of this estimation scheme, i.e., the "curse of computational cost" and the "curse of traffic model". The algorithm involves matr ix multiplication, which results in the computational effort being of the order 0(N2), which can be large for Chapter 6. Conclusion and Future Work 73 large N. Recently, some reduced-complexity filtering algorithms have been proposed [43] to solve this problem. In this thesis, the Bayesian prediction algorithm is derived based on a M M P P traffic model, assuming full knowledge of the M M P P traffic structure. As we stated in Chapter 1, we skipped the step 2, i.e., parameter estimation. The expectation-maximizat ion ( E M ) algorithm is a popular off-line locally convergent scheme for obtaining maximum likelihood estimates of the H M M parameters. Future research may focus on online Bayesian prediction of M M P P models wi th unknown transition matrix. 74 G l o s s a r y Operators diag[-] diagonal matr ix wi th diagonal entries of vector argument [ •J transpose (•, •) scalar product || • | | 2 the Frobenius norm Other Functions exp(-) exponential function ln(-) logarithm to base e log 1 0 (-) logarithm to base 10 Acronyms A O N s Al l -opt ica l Networks A R Advanced Reservation A R I M A A u t o Regressive Integrated Mov ing Average B C U Burstification Control Uni t B H P Burs t Header Packet E { - } P{-} expectation probabili ty Kronecker's sum e C L T Central L i m i t Theorem D R Delayed Reservation E T E End- to -End F A R I M A Fractal A u t o Regressive Integrated Moving Averag F E C Forward Equivalence Class F D L Fiber Delay Line fBm Fractional Brownian Mot ion fGn Fractional Gaussian Noise I P P Interrupted Poisson Process J E T Just-Enough-Time J I T Just-In-Time H M M Hidden Markov Mode l M M P P Markov Modulated Poisson Process M M S E M i n i m u m Mean Square Error M P L S Mul t i -Pro toco l Label Switching L M S Least Mean Square L P F Linear Predict ion Fi l ter L R D L o n g Range Dependence L S P Labe l Switched Pa th O B S Opt ica l Burst Switching O C S Opt ica l Ci rcui t Switching O E O optical-electrical-optical O P S Opt ica l Packet Switching O T N Opt ica l Transport Network O X C s Opt ica l Cross Connects QoS Qual i ty of Service S C U Switch Control Uni t S N R Signal-to-Noise Rat io S R D Short Range Dependence W D M Wavelength Divis ion Mul t ip lex ing W R O N s Wavelength-Routed Opt ica l Networks 76 B i b l i o g r a p h y [1] Y . X i o n g , M.Vandenhoute, and H.C.Cankaya , "Control architecture in optical burst switched W D M networks," IEEE Journal on Selected Areas in Communications, vol . 18, no. 10, pp. 1838-1851, October 2000. [2] G . Gripenberg and I. Norros, "On the prediction of fractional Brownian motion," Journal of Applied Probability, vol. 33, pp. 400-410, 1996. [3] A . Horvath and M . Telek., " A markovian point process exhibiting multifractal be-haviour and its application to traffic modeling," in Proc. 4th International Conference on Matrix-Analytic Methods in Stochastic models, Adelaide, Austra l ia , Ju ly 2002, pp. 14-18. [4] A . T . Andersen and B . F . Nielsen, " A markovian approach for modeling packet traffic wi th long-range dependence," IEEE Journal on Selected Areas in Communications, vol . 16, no. 5, pp. 719-732, June 1998. [5] T . Yoshihara, S. Kasahara, and Y . Takahashi, "Pract ical time-scale fitting of self-similar traffic wi th Markov-modulated Poisson process," Telecommunication Systems, vol . 17, no. 1-2, pp. 185-211, 2001. [6] D . Morato , J . Arac i l , L . A . Diez, M . Izal, and E . Magana, "On linear prediction of internet traffic for packet and burst switching networks," in Proceedings of ICCCN, October 2001, pp. 138-143. Bibliography 77 [7] J . L i u and N . Ansar i , "Forward resource reservation for QoS provisioning in O B S systems," GLOBECOM '02 IEEE, vol . 3, pp. 2777-2781, 2002. [8] M . H I L L and N . J . , "Scientists at lucent technologies' bel l labs calculate theoretical l imits of fiber optic communications," Lucent Technologies," Press Releases, June 28 2001. [9] L . X u , H . Perros, and G.Rouskas, "Techniques for optical packet switching and op-t ical burst switching," IEEE Communications Magazine, vol. 39, no. 1, pp. 136-142, January 2001. [10] C . Qiao, "Labeled optical burst switching fore I P - o v e r - W D M integration," in IEEE Communications Magazine, ser. 9, vol. 38, September 2000, pp. 104-114. [11] J . S. Turner, "Terabit burst switching," Journal of High Speed Networks, vol. 8, no. 1, pp. 3-16, January 1999. [12] F . Callegati , H . C . Cankaya, Y . Xiong , and M . Vandenhoute, "Design issues of optical ip routers for internet backbone applications," in IEEE Communications, December 1999, pp. 124-128. [13] L . X u , H . G . Perros, and G . N . Rouskas, " A simulation study of optical burst switch-ing access protocols for W D M ring networks," in Computer Networks, ser. 2, vol. 41, January 2003, pp. 143-160. [14] A . Bragg, I. Baldine, and D . Stevenson, " A transport layer architectural framework for optical burst switched (OBS) networks," in In Proceedings of the First Interna-tional Workshop on Optical Burst Switching, October 2003. [15] A . Kaheel , T . Khat tab , A . Mohamed, and H . Alnuweir i , "Quality-of-Service mech-anisms in I P - o v e r - W D M networks," IEEE Communications Magazine, December 2002. Bibliography 78 [16] K . Dolzer, "Assured horizon - a new combined framework for burst assembly and reservation in optical burst switched networks," in NOC, Darmstadt, 2002. [17] K . Laevens, "Traffic characteristics inside optical burst switched networks," in Optical Networking and Commun. Boston: O p t i C o m m , 2002. [18] J . Y . Wei and R . I. McFar land , "Just-in-time signaling for W D M optical burst switch-ing networks," Journal of Lightwave Technology, vol . 18, no. 12, pp. 2019-2037, De-cember 2000. [19] C . Qiao and M . Yoo, "Opt ical burst switching (OBS)-a new paradigm for an optical internet," Journal of High Speed Networks, vol . 8, no. 1, pp. 69-84, January 1999. [20] C . Hsu, T . L i u , and N . Huang, "Performance analysis of deflection routing in optical burst-switched networks," in In Proceedings of INFOCOMM, vol . 1, 2002, pp. 66-73. [21] A . Zalesky, H . L . V u , Z. Rosberg, E . W . M . Wong, and M . Zukerman, "Reduced load erlang fixed point analysis of optical burst switched networks wi th deflection routing and wavelength reservation," in In Proceedings of the First International Workshop on Optical Burst Switching, October 2003. [22] V . Vokkarane, J.P.Jue, and S. Sitaraman, "Burst segmentation: A n approach for reducing packet loss in optical burst switched networks," in In Proceedings of IEEE ICC, vol . 5, 2002, pp. 2673-2677. [23] L . Sofman, K . Laevens, and T . El -Bawab, "Segmentation overhead in optical burst switching," in In Proceeding of Opticomm, 2002, pp. 101-108. [24] A . Er rami l l i , R . Singh, and P. P ru th i , "Chaotic maps as models of packet traffic," in The Fundamental Role of Teletraffic in the Evolution of Telecommunications Net-works, vol. 10, no. 6. Proc. of the 14th I T C , June 1994, pp. 329-338. Bibliography 79 [25] I. Norros, "On the use of fractional brownian motion in the theory of connectionless networks," Selected Areas in Communications, vol . 13, no. 6, pp. 953 - 962, August 1995. [26] R . Narasimha, S. Lee, and R . Rao, "Discrete-time scale invariant systems: relation to long-range dependence and F A R I M A models," in Acoustics, Speech, and Signal Processing, ser. 13-17, vol. 4. I C A S S P '02, M a y 2002, pp. lV-4170 . [27] R. Ried i , M . Crouse, V . Ribeiro, and R. Baraniuk, " A multifractal wavelet model wi th application to network traffic," IEEE Transactions on Information' Theory, vol. 45, no. 3, pp. 992 - 1018, A p r i l 1999. [28] S. Robert and J . - Y . L . Boudec, "On a Markov modulated chain exhibit ing self-similarities over finite timescale," Perform. Eval, vol . 27-28, pp. 159-173, 1996. [29] A . G . F . Callegati and L . Tami l , "On optical burst switching and selfsimilar traffic," IEEE Communications Letters, vol. 4, pp. 98-100, March 2000. [30] G . H u , K . Dolzer, and C . Gauger, "Does burst assembly really reduce the self-similarity," in Optical Fiber Communication Conference (OFC 2003), vol . 86. O S A , 2003, pp. 124-126. [31] M . Izal and J . Arac i l , "On the influence of self similarity on optical burst switching traffic," in IEEE Global Telecommunications Conference-Globecom'02, New York, 2002, pp. 2320-2324. [32] J . Beran, Statistics for Long-memory Process. New York: Chapman and H a l l , 1994. [33] H . Heffes and D . Lucantoni , " A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer performance," IEEE J. Se-lect. Areas Commun., vol . S A C - 4 , no. 6, pp. 856-868, September 1986. Bibliography 80 [34] A . Errarni l l i , 0 . Narayan, and W . Wil l inger , Fractal Queueing Models, J . H . Dsha-lalow, E d . C R C Press, Inc., 1997. [35] J . R . Treichler, C . J . Jr., and M.G.Lar imore , Theory and Design of Adaptive Filters. New York: Wiley, 1987. [36] R . J . El l io t t , L . Aggoun, and J . B . Moore, Hidden Markov models : estimation and control. New York: Springer-Verlag, 1995. [37] V . Krishnamurthy and R . El l io t t , "Filters for estimating Markov modulated Poisson processes and image-based tracking," Automatica, vol . 33, no. 5, pp. 821-833, M a y 1997. [38] P.Bremaud, Point Process and Queues. New York: Spring-Verlag, 1981. [39] A . Mohamed, A . Kaheel , T . Khat tab , and H . Alnuweir i , "Evaluation of optical packet switch as edge device using O P N E T modeler," Opnetwork, 2002. [40] K . Dolzer, C . Gauger, J . Spath, and S. Bodamer, "Evaluation of reservation mech-anisms for optical burst switching," AEU International Journal of Electronics and Communications, vol. 55, no. 1, January 2001. [41] M . Yoo, C . Qiao, and S. Dix i t , "QoS performance of optical burst switching in IP-o v e r - W D M networks," Journal on Selected Areas in Communications, vol . 18, no. 10, pp. 2062-2071, October 2000. [42] H . L . V u and M . Zukerman, "Blocking probabili ty for priority classes in optical burst switching networks," IEEE COMMUNICATIONS LETTERS, vol . 6, no. 5, 2002. [43] V . Krishnamurthy and S. Dey, "Reduced spatio-temporal complexity M M P P and image-based tracking filters for maneuvering targets," IEEE Transactions on Aerospace and Electronic Systems, vol. 39, pp. 1277-1291, October 2003. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065868/manifest

Comment

Related Items