I‘1 q W. ‘. n".'. 5* , 3-H I. I-IVII' 1fiw‘1'm1pltfiwfhfl 1‘3.“ TII IIIIFI: IIIIII;.~I I; l mixtgn. "W 5"". iii. '“1'1‘111'1111111351111 I :- .55. m. 1. 1.3311115}: II (51 I 1'. 1 $1.11 17111 "1 5 11 . . 51.11; 111‘111511J1LI’18 “13‘. ., ‘6 “I; #:J g; .111 «r? I ‘ . x' h: W 2:31.“. II 'I:.:i£‘:“1£:"l;t .9 M} 5:17 1115;111:11’1‘13“:': -, 13% 1: ting ”3.91:1‘13'31'3-799 1 by: E: ‘ 2.5. . u. .5 f :rHQi u h." I . ~.‘ I ‘. w. i. it trgiryzafit: I 41119111 I 121.1‘127QE51‘3111”. 1511523» "ILL”:HHSLIL‘E . 1.1515: {5.13; {11:91141'1115fi1’1’ .1 '. {-9. . 9. .55.: 11‘5" ".5"““15155‘555'51‘" ’ 1545‘ ‘* 1' $531.35 5 1‘, .’1;' :1' l I: . 1H1. . 7 .‘k; ‘ 1 ._ :‘l'fyg‘ . 5'?" if“: ':5_5_= 25775. “51 .53'-u.‘;1"‘fi. .3. - ‘ €93.43: f: .5353 {and}: 7L11'“ .535 411' :1 3,9... I .1355». 111515; 5a.”? 5 5... £10. .5. $1.. .5”? 1 ~,. ; 311111} I j; 3 5 - z. I I -‘..‘ '. I.” I. _‘ 1P, 93.2; . ' E . :‘5 f I .fxfi3:?%I5r 19.. QI‘I'J” ""5193J1511955..111.1.*“5 2 an. Wu. ”.3 : f1 1“ '- fin" IIII 3&3; ' ' ‘3“ $51151 ' NW.“ ‘11:”; gigwfi‘f‘él" 1” 31 L" .51" “tiff .1112! 4"! ‘ithyg: ’2} big? ‘0‘?” 1454:... ... .555“?.. . I 51:' .H. .1132. .o .1 {1.351 I “(any ‘QpI I '5 I 1% E511} gfigfll‘i 1’31 .311? LU" 411.3?1’ blg‘gshdfi‘fi; It]! “g“ juiii‘filbh {3341.1}? 1 ' 1' ""11 ‘ ' '"15‘3‘555551'455 5531.; ‘31 5:15.55?! ’5. 2555.155? 5.15 55.5 .4.» .5555. 1...". 1 ”111-! l. [33.511 111%...551551" ‘Ufi'hd’imlifl IanIIg} "1 51‘7...1‘:i“'i :2“. . s m, 1".¥“.5 “Rf; it? '11:.11‘1’1'1hfi51‘01‘ wwpzmfl‘f 5 ‘13, , 11.11;“:‘11311'1“;’:fif113fi’1;’;; 11 iftxjfih“... 3:343:15 1513*. ‘f’t .. {37?}! '111135 ' I." “-511? r 11: 1"”; "1111133555 3. 3.. {.‘I ’1'“? 711,111311‘1‘1115': '1‘1'1391 1' :1!" big“ tif'filp 111M111“ 53'5“”: ‘. 17.13.12» i 1"“,{25 11 ¢¢d11r1¥u1m1w£1kfiijfil £9». 5 ' .955: .95.... 9 .‘ .I €111,135: “£1,311 L41.“ 5 3"?» ‘r: ID‘) L5 ‘11’1 255. .1111 1111“ ""31" {I3LP ”3:.” IIgaI . - l‘ h 1:11.359? .9 “51“" av w w~.'~l - 3 ; 41: . ’1 'uf :13!“ : -‘i;:;1;‘ £152 5" v: '- " c . i11""'.:‘§1;.wf {hi 511.151 .0; 33.119 .55.; ~ 53‘)“ 1“"5 .1 . i1.' .fuflr‘ ‘f'fz o l§;; 4‘62”! '§_ .f‘I’ “I 1‘!“ [In 1:31.}“4'2hq‘ILju' 11-? .511 1}}:1‘111.‘ I‘IIA ‘ . .i: .. ‘. j : fl:- : 13': . 1 I - 11mm: [15.1 511:1,1§111:5‘.1:,:57“1': ' . :1 1 ‘1 1 ' . . ,e . . y. x: 2 3-‘..‘;'. 5.. . F * " 75: I?‘w!5h.11éfi$f555»1111n£nfl 1H§kh$h. ..11‘1wb¥ 3% n L mflfl1pm'w 5‘152151555."5.53.55.55.55 ' 5:19:55. 5551542151111“ 5’I 5 5 9'1 5'5?‘ '51“ 111”» 15“" "”11 ' ‘ 1411-1 " 1 ‘ '1 ‘ " "'11“ .1115‘5n-F'ai; ;:z§5‘.“-:5;;..555 513531155: 5.7.5.555. :I 2.5. "5‘ NW. "“' 2." 155‘ 53175555.":1553‘? 1 ""1“ 1.5? '95?“ "1‘1‘35’5‘1’ . 5:. ' «7555 5-. 5.- .5 .5 " 55.5111. ’51»... ‘ 5 H5». :3 .,..:.s.-;:.v;..-.n::-. ». '5‘ , 2' ' 3" 1 . ‘1— "1". . .1} . "1"". 95 5 ‘I "1 I ‘11 . . “M : ' I 115111341”? 1" L“ :g' .1 21-: -. '. ... . 5.1.5 II .- 5.31111115111111111511111111. .5‘.':IIII.I. 1.5M. .iflhmpégd. 1.3.: . ".455 ‘ 11111111113141"-.1111 ' .lv. ‘ ‘5' . ' . 4.2:?- ..._ - -‘: f... z “@1151. 955' . . "“ {(31.1 . 1!? _ 1.; 99.1113?“ 5 ml;- 54.: _ 1.1-1?" 11011.11411‘” 1g“ lqu 3‘5“?! mind” .I. z!“ 3.5- I‘; 7" . 1‘ I .‘.l 1.1-1.1..." 113M711; . 1‘ ‘fi‘ . .5 I. j L‘Mt‘ II i 1.1-1131'1-‘5111'4‘511915 Em. -- 1b?! 41 : I Ib ;:_Is tnIItIublIl’bI (I g... 5.5.: “£13331“ng .5. “-15.351151, J‘flgnfig'fl EH" H $25le - .: .‘ 1"”i5ifi‘1 .5 I 5, 1’1, :1}? i ., '1 u _ 51 ' "L ‘. I. i I: .'1 ‘.":' .4“; 1’g5.! ‘ " I l!“ . ' “ . I ' “‘ {3‘ I ' ' a V V 551,1,” ,_"~“~« 111 » ‘5‘ 3.14? 1’“ ".9. I . y. . I3. . ‘. 9 ‘ n. . Inns-n. . I-T'I-i f . «49X. - .<—- .. ' "a -O~ - . 1-. r ' '—.,.I . .-. a. ~ ":~. I.” .- THESIS Illll’li'llllllllfillililllllililillfill 3 1293 02058 2114 This is to certify that the dissertation entitled. BOUNDED-CELL-LOSS-RATIO FLOW CONTROL AND RELIABLE ABR MULTICAST presented by Wei-Kuo Liao has been accepted towards fulfillment of the requirements for Doctoral Computer Science degree m WT—‘ing neer ng \vmg \Vi \Vt Major professor Date 12/16/99 MS U is an Affirmative Action/Equal Opportunity Institution 0- 12771 LIfiRARV Michigan State University PLACE IN RETURN BOX to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE moo WWW.“ BOUNDED-CELL-LOSS-RATIO FLOW CONTROL AND RELIABLE ABR MULTICAST By Wei-Kuo Liao A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science and Engineering 1999 ABSTRACT BOUNDED-CELL-LOSS-RATIO FLOW CONTROL AND RELIABLE ABR MULTICAST By Wei-Kuo Liao In this dissertation, we focus on the development for Available- Variable-Bit (ABR) flow control in ATM networks. We give a sufficient condition of mam-min fairness convergence for ER-based ABR flow control. The tractability of this sufficient condition is verified by deriving three switch algorithms. Bounding the loss ratio is another critical issue in flow control design. We use a learning model called Hedge Boosting and recursive least-squares estimation to capture the long-range dependence. With the on-line prediction, the cell loss ratio is bounded below a given ratio by reducing the available bandwidth with a number calculated under the Gaussion process assumption. We study how to extend error recovery for ABR multicast (one-to-many com- munication). We use the backward resource management cells for ABR flow control to carry error information, and design an error control algorithm for mul- ticast. In most of time, the algorithm will forward the retransmission cells only to the destinations requesting those cells. At last, we prove that with max-min fairness guarantee, for a multicast session with two link-disjoint connections to support fault tolerance, a third connection atop these two existing connections could be available for the multicast session. © Copyright 1999 by Wei-Kuo Liao All Rights Reserved ACKNOWLEDGMENTS I would like to have my deepest gratitude to Dr. Lionel M. Ni, a mentor and my advisor, who has given me constant and strong help, advises and support during my study. My special thank is to Dr. Abdol H. Esfahanian, my project co-advisor, who kept encouraging me and elevated me to have the graph-theoretic thinking. Dr. Raoul LePage, a member of my Ph.D. program committee, always inspired me by his special and precious view on various probability models. I am very lucky to have him as my committee member. I am also grateful to Dr. Matt W. Mutka, one of my committee members, as well as all faculty members, staffs, and colleagues in the Department of Computer Science and Engineering in Michigan State University. Moreover, I would like to take this chance to thank my former advisor during the master study, Dr. Chung-Ta King. From the bottom of my heart, I would like to thank my wife, Yi-Hsuan Lai. Her pleasant personality, kindness, and creative thoughts made my study easy and interesting. At last, I would like to dedicate this dissertation to my most wonderful family — my parents, sister and brother-in—law, who gave me generous and invaluable support in all respects throughout the whole study. iv TABLE OF CONTENTS List of Tables vii List of Figures viii Introduction 1 1 Background 3 1.1 Traffic Modeling and Prediction ....................... 3 1.2 Loss Probability Approximation ...................... 5 1.3 Max-Min Fairness and ER—Based ABR Flow Control ........... 9 1.3.1 Fairness Criteria and Definition of Max-Min Fairness .......... 9 1.3.2 Determining a, in ABR Flow Control .................. 11 1.3.3 Survey of Literatures on Max-Min Fairness Convergence ........ 12 1.3.4 Assumptions ................................ 14 1.4 The Model .................................. 16 1.5 ABR Multicast ................................ 17 1.6 Criteria of Reliable Multicast ........................ 17 2 Convergence of Max-Min Fairness for Single-ER—based Flow Con- trol 20 2.1 Centralized Algorithms ........................... 21 2.2 Sufficient Conditions for Max-Min Fairness Convergence ......... 32 2.3 Distributed Update Rules .......................... 47 2.3.1 Slow Update Rule (SUR) ......................... 47 2.3.2 Modified Slow Update Rule (MoSUR) .................. 48 2.3.3 Algorithm SHARE .............................. 48 2.4 Simulation .................................. 50 3 Bounded-Cell-Loss-Ratio Flow Control 53 3.1 Framework .................................. 54 3.1.1 Bandwidth Predictor: On—line Estimation for FARIMA model . . . . 55 3.1.2 Loss Ratio Limiter: The Decision of Linear Drift n ........... 57 3.1.3 Bounding Total Rate ........................... 62 3.1.4 Overall Flow Control Algorithm ..................... 65 3.2 Two Loss Priority Tiaf‘fic Stream ...................... 65 3.3 Simulation .................................. 69 3.3.1 One-Broadband-Link Network ...................... 69 3.3.2 Multi-Broadband-Link Network ...................... 70 4 Error Control for ABR Multicast 4.1 The Error Control Algorithm ........................ 4.2 Simulation 5 Flow Control for ABR Dispersity Multicasting 5.1 Flow Control Algorithm ........................... 5.1.1 Example .................................. 5.1.2 Correctness of Algorithm ......................... 5.2 Implementation Issues ............................ 5.3 Simulation 6 Conclusion vi 75 76 82 89 91 95 96 97 98 104 1.1 1.2 2.1 2.2 3.1 4.1 5.1 5.2 5.3 LIST OF TABLES The definitions of parameters ......................... 9 The fairness criteria .............................. 9 The notations used in the proofs ....................... 37 The notations used for analysis of Local Convergence. .......... 42 Squared errors for each predictor ....................... 59 The important parameters for the simulation. When there are thirty- two cells in underlying connection being sent after the last RM cell, a new RM cell will be sent. We use ADTF (ACR Decrease Time Factor) as the sleep time of the timer in both source and sender. . . 82 The representation of fields in RM cells. .................. 92 The results in “md2” in the second simulation where the simulation time is 3 seconds .............................. 102 The results in the third simulation where simulation time is 3 seconds. . 103 vii 1.1 1.2 1.3 1.4 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 LIST OF FIGURES The queuing model. ............................. 6 The example network. ............................ 10 The assignment. ............................... 11 The definition of A1(T), where T is the rooted tree for backward RM (BRM) cells traversing backwards, MER, being PCR initially, is a register in the switch and a8, being zero initially, is a binary variable associated with the branch e. ...................... 18 The centralized algorithm to find an assignment resulting in max-min fairness flow. ............................... 26 The revised centralized algorithm to find an assignment resulting in max-min fairness flow. .......................... 31 An example of g ................................ 34 The network for the counter-example. ................... 45 The iterative procedure SHARE. ....................... 49 The network topology. The session 2' has source s,- and destination d,. . 51 The simulation results for multi-broadband—link network system. . . . . 52 The Components for BLCR flow control ................... 54 The autocorrelation function for the trace .................. 57 The autocorrelation function for the prediction error process by Hedge boosting. ................................. 58 The plot for IEV,2 vs. time lag t ........................ 58 The flow control algorithm in the switch. ................. 66 Two buffer management schemes ....................... 67 The one-broadband-link network system. The session 1 has source 31 and destination d1. ............................ 70 The loss ratio when x = 2000 in the one-broadband-link network. . . . . 70 The K when x = 2000 in the one-broadband-link network ......... 71 The bandwidth prediction for x = 2000 in the one-broadband-link net- work ..................................... 71 The loss ratio when a: : 1000 in the one-broadband-link network. . . . . 72 The loss ratio when a: = 5000 in the one-broadband—link network. . . . . 72 The second network topology. The session 2' has source 5,- and destina- tion di .................................... 73 The loss ratio for multi—broadband—link network system with x = 2000. 73 The it for multi-broadband-link network system with x = 2000 ...... 73 viii 3.16 The bandwidth prediction for multi-broadband—link network system with x = 2000. .............................. 74 3.17 The 77 for multi-broadband-link network system with x = 2000 ...... 74 3.18 The ACRs for multi-broadband-link network system with x = 2000. . . 74 4.1 The switch error and flow control algorithm. ............... 79 4.2 The decision rules for ACR“ and ACR, when a BRM cell is received. 4.3 4.4 4.5 4.6 4.7 4.8 5.1 5.2 The parameters RDF and AIR stand for rate decreasing factor and ACR increasing rate, respectively ..................... 80 The service model in the source. ...................... 82 The network configuration. The multicast session has source ms and three destinations md1,md2,md3. In addition, for each broadband link BB j, there exists another ABR session 3 j sharing the same link with the multicast session ......................... 82 The simulation results using BCLR flow control when 7 = 8 and W = 100. 85 The simulation results using BCLR flow control when 7 = 16 and W = 100. .................................... 86 The simulation results using BCLR flow control when 7 = 16 and W = 500. .................................... 87 The simulation results using BCLR flow control when 7 = 16 and W = 1000 ..................................... 88 The concept of virtual connection. ..................... 91 The defintion of A1(T), where T is the rooted tree for backward RM (BRM) cells traversing backwards, MER, being PCR initially, is a register in the switch and ae, being zero initially, is a binary variable associated with the branch e. ...................... 92 5.3 The defintion of A2(T,-). ........................... 94 5.4 The example illustrating the algorithm. .................. 95 5.5 The first network configuration ........................ 99 5.6 The bandwidth utilization of B81 in the first simulation. ........ 100 5.7 The bandwidth utilization of BB3 in the first simulation. ........ 100 5.8 The bandwidth utilization of BB2 and BB4 in the first simulation. . . 101 5.9 The bandwidth utilization of links “sw4”-“ad” and “sw4”—“md2" in the first simulation ............................. 101 5.10 The second network configuration. ..................... 102 5.11 The third network configuration. ...................... 103 ix INTRODUCTION Many real-time applications for B-ISDN , such as teleconferencing, movie broad- casting, and multi—party chattering, must use multicast communication (or one- to-many communication). Extensive studies, [1—8] have shown that with effi- cient multicast communication, both network throughput and connection setup latency [9] can be improved. While the Mbone has been put into practice for multicast communication in the Internet, how to efficiently implement multicast communication for different classes of services in B—ISDN is still an open issue, i.e., there is no consensus on the multicast routing, dimensioning, flow control, error control, and support for fault tolerance, under the current situation. We will study the deve10pment for flow control, error control, and support for fault tolerance. Available-Bit-Rate (ABR) service has been defined in ATM forum. The aim of ABR service is to adapt and highly utilize the available bandwidth left by Constant-Bit-Rate (CBR) and Variable-Bit-Rate (VBR) trafiic. The network uses closed-loop feedback control for each ABR session to carry out the max- min fairness and prevent users from injecting traffic which may degrade network throughput. The AER service can be used to convey the data stream and multi- media stream [12]. In the study of ABR flow control, the cell loss ratio (CLR) is always very low by assumption. However, up to date, no upper bound has ever been given by any work. A guideline of the flow control for ABR multicast (point-to-multipoint connec- tion) has also been specified by [13]. Basically, the guideline extends the bottleneck flow control [14] from the point-to-point communication for multicast. Different implementation techniques based on the specified guideline have been developed in [15-17]. Lossless data delivery for multicast communication (reliable multicast) is nec- essary for some applications, such as distributing the information of stock markets. In this thesis, we will propose a flow control scheme called bounded-cell-loss-ratio (BCLR) flow control which will guarantee the maximum cell loss ratio (CLR). The BCLR flow control is developed with following the standard for ABR service defined in ATM forum. With this flow control, we show how to extend the standard to support reliable multicast. The remainder of this thesis is organized as follows: In Chapter 1, we will give a survey for the background of this study. In Chapter 2, we will develop a set of sufficient conditions for the max-min fairness convergence guarantee. In addition, we will derive a set of algorithms based on these rules. In Chapter 3, the bounded cell loss ratio flow control is described. The error control scheme for the multicast will be discussed in Chapter 4. Chapter 5 gives the flow control for a multicast scheme called dispersity multicast, which will provide the fault-tolerance property. We draw the conclusion in Chapter 6. Chapter 1 Background In this chapter, we first consider the traffic modeling and the prediction using the corresponding model. We show the prediction error process can be treated as i.i.d. process even when the underlying process has long range dependence. Second, we do the literature review for the loss probability when the queue length process behaves asymptotically as Brownian motion process with negative linear drift in [18]. We give a brief background for ER—based flow control. A graph model is proposed and based on this model, the ER-based multicast is described. Finally, we survey some criteria for reliable multicast. 1.1 Traffic Modeling and Prediction The traffic characteristics in the modern networks appear to be self-similar or long-range dependent [19, 20]. To explore the characteristics, from the viewpoint of modeling, the fractional Brownian motion (FBM) and fractional autoregressive integrated moving average model (FARIMA), etc. have been proposed. A variety of actions, such as control signal tracking or multi-step predictions, can be performed based on these models. In [21], a bibliographical survey for the related works for probability models and estimations on self-similar process are given. We select the FARIMA model to model the traffic due to more freedom to explore the short range dependence. A process W, is said to be FARIMA(p, d, q) if it is the solution of the following equation 9(B)V"W, = ¢(B)Z,, where B is the backward shift Operator, V" 2: (I — B)", d E (—1, 1) is the degree of this FARIMA process, p and q are the orders for the polynomials 0(a) and (15(25), respectively. The binomial expansion of (1 — B)d is as follows: (1 — B)d = anwwi. where the coefficients 7rJ-(d) is Wild) = H 2%}- k=1 The process Z, is an i.i.d. random process with zero mean. It is known that when d E (—0.5, 0.5), W} has the stationary solution [22] and has autocorrelation function p(h) with [)(h) ~ C'hz‘t‘l as h —> 00, where C is some constant, It is the time lag between two random variables and two functions f and 9 have the relation f (:12) ~ g(;z: ) as :1: —> 00 if lim il- z—mogu .5)— Suppose we have estimators 91,92,...,ép, 81,82,...,q3q, for the coefficients 61,62, ...,6’,,, 461,82, ..., a,“ respectively and we have the degree d. For the l-step prediction, we consider the innovation predictor Ut+1 3: IIM'e q A HZ 93H, j=l where the prediction error 2, = U, — L7,, U, = V"W,, and then we define ()0 ”1+1 = L2+1 - E ”junk—J‘- 1:0 Note that ”1+1— W1+1 = UH-l - Ut—H = Zr- In addition, if w e {l,2,...p},j e {1,2,...,q}, 6,- = 9,- and c2),- = ¢,, then {2,} = {Z,}, which is an i.i.d. process. 1.2 Loss Probability Approximation Currently a large body of literatures investigate the loss ratio where the service rate is deterministic and the arrival process has long memory property (e.g., see [18,23-25]). These studies focus on how to guarantee the maximum CLR for VBR traffic. Our work is based on the result obtained in [18] which uses the technique Extreme Value Theory for the Gaussian process with negative linear drift. Up to date, there is no identification that the aggregated traffic, either the arrival process or the departure process for a bufier in the switch, will converge to a continuous-time Gaussian processl. We will empirically show how close the loss ratio in [18] can be under Gaussian process assumption when the ER—based flow control is considered. Consider the queuing model as shown in Figure 1.1, where A, and S, is the arrival fluid process and service fluid process, respectively, and ES, — EA, 2 at, where kappa n is a positive constant. Consider the process X, := A, — 5,. Then ——> . 1 Qt Figure 1.1: The queuing model. 1In [26], a large amount of independent binary renewal processes has been proved to converge to a fractional Brownian Motion. However, the convergence takes place when the number of processes and the time lag go to infinity. In [18], the author mentioned that the arrival process is Gaussian process by their empirical studies. the queuing process Q, can be expressed as follows: Qt : sup (JYt "' 4X5) OSsgt Suppose the process {X,} has stationary increments, i.e., the distribution X,+, — X, depends only on 7', then HQ: > :17) 2 IP( sup (X, — X,) > a") Ugsgt 2 IP( sup (X, — X,) > 11.“) —t§s§0 —> lP’(sup(X0 — X_5) > :12) as t —> 00, 320 where the second equality is because X, has stationary increments, and the con- vergence is due to monotone convergence theorem (see [18] for detail). Suppose X0 — X_, 2 0B, — H8 where o > 0 and {BS} is standard Brownian motion process with B, E 0. Then. s>0 02 2 HQ‘ > x) : M5111) 033 - res > as) = exp [’3] (see page 190 in [27]). Indeed, if {X,} is a Gaussian process, i.e., for each fi- nite sequence t,,t2, ...t,,, (X,,,X,,, ...,X,n) has multi-variate normal distribution, Var(X0 — X_,) ~ ozt as t —> co and lE(X0 — X_,) = —r~zt, then under some condi- tions, 2517], (12) HQ: > 1‘) 2 exp [“32— as :1: —> oo (e.g., see (29) in [18]). The approximation (1.2) uses the inequality as follows: IP(sup X0 — X_,. > :1“) 2 sup IP(X0 — X_, > 1:). s>0 s>0 In addition, let t, E arg sup,>0 IP’(X0 — X_,,. > :13), then :1; t,~—as:r—>oo, (1.3) It (see Proposition 1 in [18]). Furthermore, we have the following proposition: Proposition 1 If {X,} and {X,’} are Gaussian processes with continuous path almost surely and V12 2 0,\7’t,lE(X,’+,, — X,’) S IE(X,+,, — X,), and Vt,s,Cov(X,’,X;) = C011(X,,X3), then lP(sup X0 - X_, > 2:) 2 lP’(supX6 — XLS > r). s>0 s>0 Sketch of the proof: Let Z, be the Gaussian process with above covariance and mean zero. Let X, := 8 Z,+IEX, and x; z: Z,+IEX;. Thus sups>0 X, —X_, 2 sups>0 X5 —X'_, everywhere. Then X, and X,’ have the same distributions of X, and X ,’ , respectively. Therefore, supXo — 5L, 2 supXo — X_, in distribution and supXO — XL, 2 supXO — X_s in s>0 s>0 s>0 s>0 distribution. The proposition follows. [3 1.3 Max-Min Fairness and ER—Based ABR Flow Control A main criterion of ER—Based ABR flow control is max-min fairness. In this section, we will discuss the definition of max-min fairness, the ER-based ABR flow control, a survey of the literatures on convergence of max-min fairness, and assumptions on ABR flow control we will use for the bounded cell loss ratio flow control. 1.3.1 Fairness Criteria and Definition of Max-Min Fairness The definitions for discussing the max-min fairness are in Table 1.1. The major ] parameter I description ] L the set of links in the network \IJ’ the set of existing connections in the network L, the set of links used by connection 3 \II, the set of connections using link l as minimum cell rate (MCR), which is non—negative, for connection 3 K , the static available bandwidth of link 1 17, a non-negative parameter associated with the link l 2391/, “S S Kl Table 1.1: The definitions of parameters. fairness criteria with minimum cell rate (MCR) guarantee specified in [13] can be interpreted by 7,, as in Table 1.2. The hardest fairness criterion to achieve will be I fairness criterion | The bandwidth of link l for connection 8 ] equal share 771 equal share plus MCR 77, + as maximum of MCR and equal share max{17,, us} *There are three other weighted fairness criteria defined in [13]. We leave the study of weighted fairness criteria as future work. Table 1.2: The fairness criteria. the maximum of MCR and equal share, and we will focus on how to fulfill this fairness criterion. In this dissertation, we have the uniform assumption on fairness, i.e., each link in the network is associated with the same fairness criterion. Let the sending rate for the connection 3, denote by as, be as follows: as = max{u,,r2knn,}. (1.4) Equation (1.4) will be referred to as the flow assignment equation. The max-min fairness is then an assignment of 77,,Vl 6 £, such that Vl E E, 2,6,,” (1, s K,, i.e., feasibility constraint, and every connection has a bottleneck link, namely, V3 6 \IJ’, there exists a bottleneck link i 6 £3 such that 2191!, a, = K, and as = max{u,, 7),}, i.e., bottleneck constraint. Such an assignment of 17,,Vl E L, is referred to as an assignment resulting in mar-min fairness flow. Example 1 Figure 1.2 shows the example network. The link set L = {11,12,13}. The connection set \II’ = {31, 32, 33}. We have the link parameters 771,772,713 as- sociated with links l1,12,13, respectively. The capacity ofl1, [2, l3 are 15, 10, 2, re- spectively. The M CR3 for the connections 31,32,513 are 2,0,5. Figure 1.3 shows 10 Figure 1.2: The example network. the assignment to achieve max-min fairness. The max-min flow (a,,,a,,,a,3) s3 is Figure 1.3: The assignment. is (3,2,5). A possible assignment (711,172,773) resulting in mar-min fairness flow is (:L‘, 3, 2), where :1: 2 3. The satisfaction of feasibility constraint is easy to check. For the bottleneck constraint, the link [2 is the bottleneck link for connections 31 and 53 and the link 13 is the bottleneck link for connection 32. 1.3.2 Determining as in ABR Flow Control In ER—based ABR flow control defined by ATM forum, resource management (RM) cells are used to convey the control information. We will focus on a special field in RM cell called ER. Whenever there is a fixed number of data cells being sent, an RM cell will be sent from the source. Initially, ER in the RM cell will be set to be peak cell rate (PCR). On receiving an RM cell, the destination will adjust the field ER in the cell according to its maximum allowed receiving capacity and 11 then return to the source along the previous path in the backward direction. The RM cell sent from the source to the destination is in the forward direction and will be called FRM cell. Reversely, the RM cell will be in the backward direction and called BRM cell. On receiving the BRM cell coming from the link 1, the switch will update the field ER in the cell by min{ER, 77,}. The BRM cell will then be passed up to the source. Therefore, as the source receives the BRM cell, the field ER in the cell already contains the minimum of all feedback rates, i.e., for connection 3, ER : min,E 1:. 77,. The source then adjusts its sending rate according to the field ER and its MCR. In mathematical formulation, let the 77, be time varying, thus we denote 77, at time t by 17,(t). Therefore, for the connection 8, the sending rate a, at time t, denoted by a,(t), is determined as follows: a3(t) = max{u,, {gin 77,(t — 778(t))}, where V1 6 .Cs‘v’t Z 0, rf(t) > 0. 1.3.3 Survey of Literatures on Max-Min Fairness Conver- gence Suppose when determining 17, for each link i, we only have the information \II,, and r,(t), u,,Vs e \II, as well as the time-varying available link capacity K,(t) at time t, where r,(t) is the arrival rate to the link 1 at time t for the traffic belonging 12 to connection 3.2 In what follows, we will drop the subscript I if there is no ambiguous. Notice that 7:3(t) = a,(t —- 7(t)), where Vt 2 0,7(t) > 0 and thus 775(1) is time varying. To determine each link parameter 77, i.e, each coordinate of the assignment resulting in max—min fairness flow, in [28], Abraham and Kumar consider the following update rule: 77(t+1) <— 77(t) + a(t)K where {a(t)} is any sequence which is squared summable, but not summable, and R(t) :2 2191773“)- When {K(t)} is a bounded i.i.d. process, then the max-min fairness is proved (to be fulfilled and the total utilization will converge to BK (t) (Theorem IV.1 in [28]. To implement their rule, as stated in Section V.B of [28], the sequence {a(t)} needs to be reset if IEK(t) has changed. In addition, in the proof of Theorem IV.1, the updates for all the rates in each link should happen simultaneously. In [29], Hou, Tzeng, and Panwar has proposed an algorithm (Algorithm 4 in the paper) which can converge to the max-min fairness within finite time. They use the notion marking consistency to calculate the advertise rate. We will refer their algorithm as to H TP algorithm. The switch algorithm needs to sort the MCRs and thus leads to high computation complexity. 2This problem setting is more interesting since in real networks, the parameter is preferred to be obtained in distributed way so that there is no need for extra handshaking. 13 In [30], they propose the update rule: 77(t+1) (- min{K(t), m}. The rule is very simple. However, to guarantee the max-min fairness, the interval between two consecutive updates should be greater than the maximum round trip delay (see Section 3.4 in [30]), which is considered too long for the convergence. Usually, the update interval should be as small as possible subjective to the com- putation limitation or whenever an FRM cell arrives, the update will be fired. Moreover, they did not prove that their update rule can obtain an assignment re- sulting in max-min fairness flow using the criterion ” maximum of MCR and equal share” (see Table 1.2). In [31], Tsai and Kim modified HTP algorithm to have faster max-min fairness convergence. However, the algorithm, called CPG protocol, should use an unspec- ified bit called “RM.state” which is not supported in current traffic management specification by ATM forum [13]. In Chapter 3, we will propose a set of general rules to check the max-min fair- ness guarantee. With these rules, we also derive three viable switch algorithms conforming to the ATM traffic management specification [13] with no delay infor- mation needed. 14 1.3.4 Assumptions Let \Ilj‘ denote the set of sessions 3 using link I such that rate r, 2 77,. We call such a session to be unconstrained for link I. It is trivial to see that for each link l 6 L3, 2 max{us,lr’réiLI:77,l} _<_ Z max{us,77,} (1.5) SEW? sell? The inequality (1.5) simply indicates that the total feedback rate for those uncon- strained sessions for link I will be bounded by a number known locally. Note that this inequality is independent of the update rule. For those constrained sessions for link l, their rates are limited by the data generating rate in the source end, receiving capacity in the destination, or the bottlenecks elsewhere. Therefore, we have the following assumption: Assumption 1 The rate of the constrained session for each link I is inde- pendent of change of available bandwidth forl and the rate of unconstrained session for Z. We also have the following assumption: Assumption 2 The change of the total arrival rate of all constrained sessions for each link I is relatively small to the change of available bandwidth for l. Beside updating and passing the BRM cell, the ATM traffic management spec- ification 4.0 [13] allows the switch generating and returning a BRM cell to the source in case that the feedback rate 77, is reduced. The operation is called back- ward congestion notification (BCN) by switch. In this dissertation, we assume the 15 switch will bypass BRM cell to the source without letting it enter into the ordinary ABR buffer. In this way, we have next assumption: Assumption 3 The time interval for a BRM cell traveling from a switch to the source is constant. In this dissertation, we assume that when a call for establishing a connection for the ABR session arrives, the network uses MCR and the network status to decide whether to establish the connection for the ABR session. Therefore, for each link i, if i E ‘11,, then u,- is known in the controller for link l. In ATM traffic management specification 4.0 [13], the ABR session is only allowed to use the data cell with zero cell loss priority (CLP). For the future application of ABR service, such as hierarchically encoded video streams, ABR service must be applicable to the data cells with CLP :1. In this dissertation, we will consider how to restrict the cell loss ratio for cells with CLP = 0 while there exist cells with CLP : 1 flowing through the same buffer. 1 .4 The Model The network is modeled as the directed graph G (V, A), where V(G) and A(G) are the vertex set and arc set, respectively. Each arc e in A(G) has a head vertex Me) and a tail vertex t(e). A vertex models a switch, or a source, or a destination, and an arc models a link. We write a directed graph G as G (V, A, C') if necessary, where C : A(G) ——> [0, 00). For each arc e E A(G),C(e) denotes the available bandwidth of that arc. A path is a sequence of distinct arcs 81, e2, ..., e, where s 2 1 such that 16 Vj,k 6 {1,2, ...,s}, t(ej) -_—_ [t(ek) ifj +1 2 k S s, and t(ej) # h(e,,) otherwise. In addition, eg):(%)0(6) is called path bandwidth of path P. A rooted tree T (V, A, C) rooted at r is a directed graph where Vv E V(T) — {r}, there exists a unique path from r to v; in addition, Ve E A(T), h(e) 79 r. A vertex v is said to be a leaf of the rooted tree T if v e V(T) and Ve E A(T), t(e) # v. The set of leaves of T is denoted as L(T). Moreover, 8$l(¥)C(€) is called connection bandwidth of T. An arc e E A(T) is called a branch of a vertex v if t(e) = v. The two arc-disjoint subtrees (or underlying connections) for dispersity multicasting, denoted by T1 and T2, are rooted trees rooted at the same vertex, L(Tl) = L(Tg), and A(T,) n A(Tg) = 0. In this dissertation, for a rooted tree T rooted at r, we restrict that r models the source, Vd E L(T), of models a destination and W E V(T) — L(T) - {r}, 77 models a switch. We also restrict that Vi 6 {1,2}, [{e e A(T,) : t(e) = r}| = 1, where r is the root of T,. Note that the general definition of subtree for multicasting can be easily transformed to the subtree with the above restrictions. In this dissertation, we always let the index i 6 {1,2}. 1 .5 ABR Multicast Consider the ABR multicasting with a single connection T(V, A, C). As a simplified version of the fourth algorithms in [15,16], to obtain the connection bandwidth, the source generates a forward RM (FRM) cell with the field explicit rate (ER) being peak cell rate (PCR). Upon receiving an FRM cell, the switch multicasts the cell 17 For every destination: Upon receiving an FRM cell, return the cell as BRM cell to source. For every switch 71: Upon receiving a BRM cell with ER from branch e, MER <— min{MER,ER}; a, <— 1; if for each branch e’, a8, = 1, then pass the BRM cell to source with ER+— min{MER,min{C(e’) : e’ is a branch of v}}; MER+— PCR; for each branch e’, ae’ <— 0; else discard the BRM cell. Figure 1.4: The definition of A,(T), where T is the rooted tree for backward RM (BRM) cells traversing backwards, MER, being PCR initially, is a register in the switch and a,, being zero initially, is a binary variable associated with the branch 6. to all its branches. Then an operation A ,(T), defined in Figure 1.4, is performed. Upon receiving a backward RM (BRM) cell, the source adjusts its allowed cell rate (ACR) according to ER in the cell. 1.6 Criteria of Reliable Multicast The criteria of great importance in the design for reliable multicast tranSport pro- tocol are fast error detection, reduction of feedback messages and retransmission traffic, and reducing the impact of the number of receivers on the sending rate. The criteria with the approaches to solve it are listed as follows: 0 fast error detection and reduction of feedback messages: approach: To enable fast error detection, a negative acknowledgment (NAK) will be sent back to the sender if the receiver detects an error. The receiver needs a timer for ensuring that the sender receives the NAK. The sender has no knowl- 18 edge about the data arrived at all the destination correctly; therefore, the sender should periodically inquire the receiver status. In addition, when the number of receivers is large, the NAK will not be sent after a random period to avoid the overflow of buffers near the sender. The analytic study in [32] indicates that the multicast transport protocol using N AK will balance the load between the sender and receivers and thus will result in better scalability. o reducing the number of retransmitted data: approach: By partitioning the set of receivers to several local groups and electing a local group server for each receiver subset, the server can only multicast retrans- mitted data to the receivers in the local group [33,34]. Each receiver needs to know its local group server. Another approach counts the number of receivers requesting the same packet and selectively unicasts or multicasts a retransmission [33]. The sender needs to maintain the information for each receivers. o reducing the effect of the number of receivers on sending rate: approach: In TCP, a packet loss indicates congestion and thus the sending rate should be reduced. Suppose there are k 2 1 receivers and the packet error prob- ability associated with each receiver is pe > 0 and let these error probability dis- tributions among all the receivers be independent. Therefore, for each packet, the sender will receive an NAK with probability p" = 1— (1 —pe)k > 1 —e"€i’¢. In a large- scale multicast communication, it is possible that kpe z 1, e.g., k = 100, p, =2 0.01 and thus pn > 0.63. Thus, the local group size should be small. Another approach takes advantage of bandwidth reservation and thus congestion will never take place for the multicast session [35]. 19 Chapter 2 Convergence of Max-Min Fairness for Single-ER—based Flow Control There are a large body of literatures (e.g., [28,36—41]) on the ER-based flow con- trols. Basically, they can be divided into two categories: single-ER (SER) flow control and multi—ER (MER) flow control. In SER flow control, at a time point, the feedback rate for a link will be the same for all the ABR sessions through the link. On the other hand, the feedback rate for a link in MER flow control might be different at the same time for the diflerent ABR sessions through the link. Exam- ples for SER flow control are NIST [39], UT [38] and EPRICA [13]. The popular flow control algorithm ERICA [40] is considered to be in the category of MER flow control. Basically, SER flow control has the advantage of simplicity and thus its properties are easy to derived. In this paper, we study the SER flow control algorithm. In [43], they proposed a sufficient condition marking consistency for max-min 20 fairness convergence with the fairness criterion ”equal share” (or called ”max-min share” in page 79, [13]). Based on the marking consistency, literatures [29,31] propose algorithms for the fairness criterion ”MCR plus equal share.” The advan- tage of the technique marking consistency is fast convergence. However, as stated in Subsection 1.3.3. extending from marking consistency appears leading to high computation complexity or inconformity to the ATM forum traffic management specification [13]. Instead of marking consistency, based on the insight in [42], we will try to set up a simple sufficient condition which has convergence guarantee for max-min fairness with the fairness criterion ” maximum of MCR and equal share.” We will use this sufficient condition to generate three SER flow control algorithms conforming to ATM traffic specification [13]. As the analysis and simulation show, though in general, the transient behavior of the algorithm with higher complexity will behave better, there exists a possibility for an algorithm with computation complexity 0(N), where N stands for number of connections via the link, but the transient behavior is close to the one with computation complexity C(Nz), which is considered as the optimal one. 2.1 Centralized Algorithms For the description of notation we will use, please refer to Table 1.1. Given a network with link set L = {[1,12, ...,l,,}, a set of existing connections \IJ’, we can develop a simple centralized algorithm to find an assignment _77_’ :2 (771,77771'27 ..., 777’") resulting in max-min fairness flow. To avoid the trivial case, we have the following 21 assumptions: Assumption 4 Throughout the whole dissertation, V1 6 [1,313 e \Il’ such that tells. Assumption 5 Throughout the whole dissertation, Vs E \I", Q) 75 £3 g [1. Let the function g,,, with l e E be defined as follows: g,,,,(77) z: max{77, up} + Z (max{77, 71,}ll(a,- 2 77) + a,ll(a,~ < 77)) , (2.1) iE‘I’I—{J'} where 7* E arg mgxa“ and the indicator function lI(-) = 1 if (-) is true; otherwise, IE 7 II() = 0. Moreover, by (1.4), Vi E ‘11,,0 3 71,3 a,. Remark 1 First, 967(0) = $7911, 77,. Second, 9c! is continuously increasing to infinity. Remark 2 Suppose we use 777‘ such that 9151(7)?) : K, as the link parameter for link 1. After the flow assignment, e.g, (1.4), we have 2,6,,” a,- s K,. This is because for each item corresponding to an indexi E \II,, a,- is less than or equal to the item. Lemma 1 Let ‘1’: = {1,2, -.-,kz}- Suppose that there is a sequence a’l,a§, ...,ajcz such that Vj,1 g j g k,,a,~ g 0.3-. Define function g,,, as follows: 717(7):: max{n.u,.}+ Z (max{n.u.}n(a22n)+a:II(a'.-<77>), iE‘I’I—{i‘} where 7* E arg mam-6,7, (1;. Then V77 6 [0, oo),g,.,,(77) g 9,3,(77). 22 Proof: Since Vi E \117, if a; 2 77, then max{77, 'u,}ll(a',. _>_ 77) + a]ll(a;- < 77) = max{77, 71,} _>_ max{77, 71,}Il(a,- 2 77) + a,ll(a, < 77); on the other hand, if a; < 77, we have max{n,uz~}l(ai 2 77) + 0211(02 < 77) Z a, = 111ax{77,u,}ll(a, 2 77) + (1.,ll(a,- < 77). Therefore, we have V7? 6 \II,, max{77, u,}II(a; 2 77) + (121l(a; < 77) Z max{77, 71,-}li(a,- 2 77) + a,lI(a,- < 77). (2-2) In addition, suppose 7" 7t 7*. Notice that d}. g a,- g (13.. If a}. 2 77, then max{77, 713's} + max{77, u3.}H(aJ-. Z 77) + a3.ll(a3. < 77) = max{77, up} + max{77, 713.} = max{77, uj.} + max{77, uj.}H(a3. Z 77) + (73.1(a3. < 77). 23 If a}. < T) S ajo, then |/\ max{77,11J-.} + 111ax{77,u]~.}ll(a3. 2 77) + a3.ll((13. < 77) max{77, 71,-} + (1.5. 77 + max{77, 71,-} n1ax{77,713.} + max{77, uj.}ll(a;-. 2 77) + a'j.ll(a}. < 77). If a}. S (1,. < 77 g (13., then by Vj E ‘11,,0 S 71,3 (1.], max{77, 71,-} + max{77, 713.}ll(a3. 2 77) + a3.ll(a3. < 77) 77 + a}. 77+" max{77.11]~.}+111ax{77.u,-}II(a3-. Z 77) + a;.ll(a;. < 77). 3. < 77, then max{77, 71,-} +n'1ax{77,u3.}ll(a3. 2 77) + a3.I[(a3. < 77) 7) + (15-. 77+ a}. max{77, ur} + max{77, uj.}ll(a3. 2 77) + a3.l[(a;-. < 77). 24 Therefore, Hence, if j * = 1.777) max{77, 717.} + max{77, u3.}ll(a3. 2 77) + a5.lI(a3-. < 77) (2.3) g max{77,u§.} + max{77, uj.}ll(a;. Z 77) + a3.ll(a3-. < 77). 7, then by inequality (2.2), 177* ¢ 7*, then 911(7) |/\ |/\ max{77, 717-} + Z (max{77, Ui}H(ai Z 77) + 0711(01? < 77)) iE‘I’z-{j'} max{77, 713.} + Z (maX{7], u1}11(a2 Z 77) + 0211(02 < 0)) iE‘i’z—{i‘} 9131(0) max{77, Uj‘} + Z (max{77,ui}1[(at Z 77) + a711(ai< 72)) iE‘I’z-{j'} max{77,uj—} + max{77, 713.}Il(a3. Z 77) + a.3.lI(aJ-. < 77) + Z (max{77, '11,}Il(a., Z 77) + a,ll(a,- < 77)) lE‘I’l—{j‘j‘} max{77, 717.} + max{77,uJ-.}II((15. Z 77) + a3.ll(aJ-. < 77) + Z (max{77, u,}lI(a: 2 77) + a;I(a; < 77)) zeta-{723'} max{77, uj.} + max{77, uj.}II(a;. Z 77) + a3.ll(a3-. < 77) + Z (max{77, 71,}ll(a; Z 77) + «Mai < 71)) iE‘I’I—{j.,7.} 96,101): 25 where the first inequality is from (2.2) and the second inequality is from (2.3). C] Then we have the greedy1 algorithm shown in Figure 2.1. 1 [It—(AWE\II’,a,+—oo;Vl€£,777’<—oo; 2 while c ¢ c”, do 3 ioreachzec-L‘, do 4 777" <— min{77 : 967(7)) 2 K,}; 5 end for; 6 choose a link I E arg min‘nf ; rec—c 7 77} <— 77;; 8 for each s E \117, do 9 as (— max{us: 1111117658 771,}; 10 end for; 11 c“ <— c‘ u {i}; 12 end while; 13 output 1’; Figure 2.1: The centralized algorithm to find an assignment resulting in max-min fairness flow. Let 77:7 be the function we use in kth while-loop iteration in line 4 for link 1. Moreover, let C, be the 777 at line 7 in the ith while-loop iteration in Figure 2.1, where l g i g n. We have the following lemma: Lemma 2 If 37ml 3 m g 71,C1 g (2 < g (m, then V8 6 \Il’,as has been changed at most once before (771+ l)th while-loop iteration. Proof: If 771 = 1, the assertion is trivial. Therefore, let m > 1. Suppose that by the end of kth while-loop iteration with k < m, Vs E \II’, a, has been changed at most once. For those a, being changed, i.e, a3 < 00, by line 9, we have a, g (7,. Therefore, before line 9 in the (k + l)th while-loop iteration, V3 E \II,, if a, < oo, 1The notion greedy here does not mean that we can obtain each parameter 77, for link 1 independently. Instead, the notion indicates that in each step, we can obtain one coordinate of the assignment resulting in max-min fairness flow. 26 i.e., a, is changed at kSth while-loop iteration where k, g k, then by line 9 in the (k + l)th iteration, a, = max{u3, min 777'} = max{71.,, {7,3}, 1e11, due 130 that (7,5 S (“+1 S S C7, S (7,711 and Vi E £3, either Eik’,k,. g k’ g k,777’ = (7,1, or 777’ = 00. Hence, a, will not be changed at (k + l)th iteration. By induction, we have the proof. [:1 Theorem 1 The output 77_’ obtained by the centralized algorithm in Figure 2.1 is an assignment resulting in mar-min fairness flow. Proof: First, note that if there is an 777’ being changed, then V3 6 \II,, a, is updated at line 9, which is the flow assignment equation (1.4). Therefore, except line 7 - 10, during each while-loop iteration, V3 6 \II’, a, will satisfy the flow assignment equation. Second, we claim that (1 _<_ C2 5 _<_ C,,. If so, by Lemma 2, Vs E ‘1",a, will be changed once. Notice that if 1’ is chosen in the kth while-loop iteration, K7, 2 91-77(717'1) 2 2:97,, a,- after kth iteration, and thus the feasibility constraint will not be violated. To prove the claim, suppose we already have Q, g (2 g g (3-1. Therefore, by Lemma 2, a, has been changed at most once before 7th while-loop iteration. Let I’ be I at line 6 at jth while-loop iteration. Let Af, _C_ \I’y be the set such that Vs E Aft, a, is finite in line 3 during the kth while-loop iteration. Hence, Affl g; A{,. 27 Therefore, we have V77 6 [0, 00), £7,107) 2 g§,7,(77) since a, will be changed at most once, A771 g A{, and by Lemma 1. (Apply 93,71 as 7,, and 93:7, as gc7.) Since 957, is increasing, therefore, we have 715,741 g C], where 71277-1 is the 77;; obtained at line 4 during the (j —- l)th while-loop iteration. Since (7-, is the minimum among those 777,1 6 L — L’ in (j — l)th while-loop iteration, therefore, we have (7-, g 777";J._1 g (7. Thus by induction, C, 5 (2 g g (n. Third, if in some while-loop iteration, l’ is chosen at line 6, then, if 33 such that a, : 00, then at line 11 in the same while-loop iteration, a, = max{us,777’,} and 2,9,,” a,- = 90,7:(777',) = K ,7. Therefore, 1’ is the bottleneck link for 3. Since Vs, a, will be from infinite to finite eventually by Assumption 5, therefore, Vs, there exists a bottleneck link for s. D As stated in the proof above, V3 6 \II’, a, will be changed once. Therefore, we can replace line 8 and 9 with the following statement: 8’ for each s E \II, such that a, 2 00, do 9’ a, <— max{u,, 77;}; In addition, we can omit the initialization of 777’ at line 1. In the centralized algorithm, we need to find the smallest 777* to satisfy g,,,(77,“‘) = K, at line 4. The question will be as follows: Can we simply choose any 77;" such that g,,,(77{) = K ,? Suppose we are at line 4 in 7th while—loop iteration. We choose any 777' such that 9,707,"). If 1 is chosen in line 6 as l, in the analysis, instead of using 777" as Q], 28 we can use (7 redefined as follows: Cj :2 max{777‘,(j_1}. where 770 :2 0. Notice that if we can prove that 572.7(9) S K,, then gilmj) = K, since 773‘, is increasing and 95.107” = K,. We have the following lemma. Lemma 3 At line 7 in kth while-loop iteration with 1 g k g 71, VI 6 .C — 17,757,.) s K,, where 57 is the c“ at line 3 - 10 in kth while-loop iteration. Moreover, if 77, 9t 77;, and 9:7(771) = 927(772) = K,, then Vs E \117, a, at line 11 in the same while-loop iteration can be in one of the following cases: case 1: If s = 7*, then u, 2 max{77,, 772} and, case 2: ifs 7t 7"“, then u, 2 max{77,,772}, 0r min{77,,772} S u, = a, g max{77,,772}, or a, g min{771,772}. Therefore, Vs E \117, a, will be the same when 77, or '77-, is used as the parameter for link 1. Proof: Suppose for some 7' with 1 g j < n, the first statement holds true when k = 7'. Therefore, if 1’ is chosen as l at line 6 in (j+1)th while-100p iteration, in this iteration after line 5, we have V1 6 L—Bj, 937((7) s K, and 95:1(775) _<_ 9741,1777” s K, (see the third paragraph in the proof of Theorem 1). Since 775:1“ J) g 7717((7) s K, and (7+, = max{Cj, 77;}, the first statement holds true when k = j-I—l. By induction, we prove the first statement. 29 For the second statement, without loss of generality, suppose 77, < 77,. Consider the following cases: For case 1, 71,. < 772 and s = 7*: We have max{u,,77,} < 772 = max{usfllz}; for case 2: '11,. < 772, u, < (1,, a, > 77,, and s 76 7*: we have max{77,, 71,}II((1, 2 771) + asH(as < 711) l/\ max{77,, us} |/\ min{772, as} = max{77,, 71,}ll(a,. Z 772) + a,,ll(a, < 772). If 33 E \II, such that one of the above two cases holds, then due to that each item corresponding to an s E \II, in 9,7 is increasing with respect to 77, and thus 9,707,) < 9,407,). We have a contradiction. For the third statement, if s = 7*, then by case 1, after the flow assignment at line 9 in the same while-loop iteration, a, = u, by using 777’ = 77, or 777’ = 772. If s ¢ 7" and a, = 00 before line 8, then by case 1, after the flow assignment at line 9 in the same while-loop iteration, a, = u, by using 77] = 77, or 777’ = 772. If a, < 00 and s 75 7*, then a, will not be changed since 31’ 6 £,, 777’, has been defined in the previous while-loop iteration with 77], g 77,, or (1,. = 71,. [:1 Therefore, in the proof of Theorem 1, the sequence (1, C2, ..., n is still increasing 30 and resulting in the same flow sequence as {as} just before the algorithm finishing. Hence, the statement of Theorem 1 still holds. Therefore, we can replace line 4 with 4’ find 777* satisfying 9,7(777’) = K,; The revised centralized algorithm is shown in Figure 2.2. 1’ [It—(0;Vse\ll’,a,<——oo; 2 while£7$£, do 3 for eachlEL—B, do 4’ find 77;" satisfying 9,707,“) 2 K1; 5 end for; 6 choose a link l E arg min_777*; (EC—C 7 7715 (— 77,1“; 8’ for each s E \II, such that a, : 00, do 9’ as +- maX{us,77}}; 10 end for; 11 1: +— 1‘ u {i}; 12 end while; 13 output 77:; Figure 2.2: The revised centralized algorithm to find an assignment resulting in max-min fairness flow. To reduce the time spent in obtaining g,,,(77,), for each link 1, we keep a variable initially zero. If for some 3, a, is changed from 00 to a finite number, then add this finite number to the variable. That is, we mark 3 for I so that in the following steps, we do not cope with s anymore except the variable kept for 1. This mark operation will be used in some distributed algorithm. It will be noteworthy that though a, has been changed at most once, we cannot K7—276W1a,l(a, 77, and thus gc,,(fi,) > K,. 31 2.2 Sufficient Conditions for Max-Min Fairness Convergence We will drop the subscript 1 if there exists no ambiguity. We have developed a centralized algorithm in Figure 2.2 to find an assignment 77_’ resulting in max- min fairness flow in Section 2.3. In the following sections, we will focus on the development of distributed algorithms to find the assignment resulting in max- min fairness flow. Consider the following problem: Problem 1 Given K > 0, an index set \II, and sequences of non-negative numbers (7,),677, (11,),97, and a subset {7*} g \IJ“ g \II with 7* E arg max,” max{uh 7,}, find an 77* such that 9(77‘) = K- where g(77) 2: Z max{77,'11,-} + Z (max{77,u,~}ll(max{r,, 71,} 2 77) 264’“ iEW—W“ (2.4) + max{r,,u,}ll(max{r,,u,} < 77)) , where the indicator function ll() 2 1 if (-) is true; otherwise, ll(-) 2 0. Remark 3 If we let a, = max{r,, 11,-}, then for link 1, V77 6 [0,00),g(77) = 91:70]); where 9,7 is defined in (2.1). 32 Remark 4 If we use the solution 77* of Problem 1 as the feedback rate and currently network is in the equilibrium, i.e., for each link, the vec- tors (r,),-Eq,,(u,-),Eq, and the available bandwidth K are time-invariant, then 2,6,1, 7‘, g K. That is, Vi E T, if r,- > 77“, then 7‘, S Inax{'11,-,77*} due to the flow assignment equation (1.4) and 7*, = a,. Remark 5 The solution of Problem 1 is not unique, e. 9., when 2,6,, u,- = K, V77 E [0,min,€q, 71,-], 77 is a solution. Remark 6 Note that the first summand in (2.4) is continuously increasing to infinity with respect to 77 since [\Ilul _>_ 1. The second summand in (2.4) is continuously increasing with respect to 77. Therefore, g(77) is continuously increasing to infinity. Hence, if 9(0) 2 27:1 u,- s K, then by the intermediate value theorem, the problem has a solution. Indeed, g is a continuously piece- wise linear function. Remark 7 It is usually assuming u, g 7,. However, we will not stress this inequality throughout our analysis. In fact, in some case, as > r, if we refer r, as to 16 5131977, when considering the arrival rate of connection 5 at link 1’. That is, when a source sends an FRM cell, the ER field will be min{PCR,C,} initially, where C, is the maximum sending rate user currently is allowed to requested. On receiving an FRM cell belonging to connection 3, the switch updates the register r,f by the ER field in this cell and then updates the ER field by min{ER, 77}. on receiving a BRM cell belonging to connection 3, the switch updates the register 72 by the ER field in this cell and then updates the 33 ER field by min{ER,77}. Then assign r, = min{r{,r§’}. On receiving a BRM cell, the destination updates ER field in the cell by min{PCR,C,,} where Cd is the maximum capacity allowed in the destination. We refer the calculation of r, by using ER field in both FRM cell and BRM cell to as advanced calculation. Example 2 Figure 2.3 shows the plot for 9 vs. 77 when 0 \II = {1,2,3,4}, o (71,72,7‘3,r4) : (4,2,5,2), o ('u1,u2,u3,u4) :- (3,2,4,1), and 0 \Il“ ={1}. (1,10) (0.8) + eta Figure 2. 3: An example of 9. We have an important property referred to as lower bound potential as follows: Lemma 4 Consider the function 9,7 defined in (2.1). Let 77’ :2 min{77 : 91:70]) 2 K7} and let \II = {i E \II, : a,- 2 77’}. There exists a sequence {7,}(,E.p) such that 34 Vi E \Il,max{u,-,r,-} Z max{u,,77’} and Vi E \117— \Il,r,- = a,. Define g, as g(77) :2 Z max{77,u,} + Z (max{77, u,}ll(max{r,-, u,} _>_ 77) tell,“ iE‘I’z—‘il‘f + max{77, '11,}II(1’11ax{r,-, '11,} < 77)), where {7*} Q 4'? (_I \I1 U {7*} and 7* E arg max,eq,,(max{u,,r,}). We have 77’ 2 mini"? 1 511(7)) = K,}. Proof: Recall 7* e arg mine-6,, a,- in (2.1). If 7* = 7*, then vn g 77', we have g(77) = max{77,uj=.}+ Z max{77,-u,} test—{3*} + Z (max{77, u,}lI(max{7‘,-, Ui} 2 ll) iEW1"‘i’I‘—{3‘} + max{r,, u,}ll(maX{Ti, at} < 77)) = max{77, 11,-} + Z max{fl, Uzi} telly—{7"} + Z max{77, u,}ll(a, Z 77) + a,ll(a,- < 77) iE\II7—\i!]‘—{7‘} : 9cm?)- If7* 7t 7*, then either 1) max{rj.,uJ-.} < 77’ and aj. < 77', or 2) max{77, uj.} > 77’ and a7. 2 77’. If it is the case 1), then \II" = {7*}, and a,— = max{713.,73.} = a3“ 35 Therefore, V77, a,- < 77 S 77’, 91(7)) n1ax{77,u3.}+ Z max{TnU7} iE‘l’z—{i‘} = 7] + (If + Z a,- test-{321'} : 774—11.}. + Z a,- iE‘PI—{j‘tj'} = max{77,uJ--}+ Z (.1, iE‘llz—{j‘} = 911(7)) If it is the case 2), then V77 3 77', 91(7)) = The lemma follows. max{77, 113.} + max{77, Uj-} + Z max{77, 71,-} dew—{jar} + Z (max{77, u,}lI(maX{7‘1, U1} 2 7)) iEWI-qlr—{j‘} + max{r,, u,}ll(maX{Ti, “1} < 77)) max{77, ujo} + Z max{77, 71,-} iEq’i‘ii‘} + Z max{77, u,}l[(a,~ 2 77) + (1.,ll(a,- < 77) rapper—{7*} 90,1(77) Lemma 5 Consider Problem 1. IfA g B E \II, then V77 E [0, oo),g,,(77) 3 93(77), where 97, and 9,3 are the function 9 using \II" = A and \II" = B, respectively. 36 Proof: For all i E B — A, either 7,- g u, or r,- > 71,-. In either case, max{77, 71,-}Il(max{r,, u,} 2 77) + max{r,, u,}ll(max{r,~, u,} < 77) S max{77, u,}. Therefore, 17,,(77) 3 (73(77). [:1 Let L = {11,12, ..., l,,}. Suppose under the persistent environment, we use the centralized algorithm in Figure 2.1. In what follows, we will use the notations in Table 2.1. [ parameter] description 7,7(t) r, at time t for link l g,‘ the function g for link I at time t \I'7‘(t) as Q!“ in g,‘ jf(t) in arg mam-6,7,, (max{r,,,(t), u,}) 7,*,, 7* for link i at line 4 in kth while-loop iteration of algorithm in Figure 2.1 7733* {s e 717, : o, = oo at line 4 in kth while-loop iteration of algorithm in Figure 2.1} (7:, the function 9,7 at line 4 in kth while-loop iteration of algorithm in Figure 2.1 77,(t) parameter at time t for link 1 EU) (7711(t)37112(t)7*'*7771n(t)) 777’ the assignment for link 1 by the algorithm in Figure 2.1 1’ (771,, 771,, ---,77,’,) '3 the flow for connection 3 resulted from 1’ W21" {1521} U ‘I’Z’fi’k U {s 6 ‘1’: = a; 2 771} 9,“ 9 using ‘1’1,{T7,l(t)}(ic—w,),{uiiuewm‘I’Zik as \II, {Triuemr {ui}(iE\II)a ‘1’” 7,, maximum round trip delay among each pair of switch and source 7,, maximum interval between two consecutive updates for each link parameter Table 2.1: The notations used in the proofs. Lemma 6 Given 17,13 k g n and i,k g i g 77, let \ll = \II,,, \II” 2: ‘11” and (‘Ji ’ 37 Vs E ‘I’ — \Pfi;k,1’11ax{us,r,} = a’s. Therefore, V77 E [0, 771,1]! g(77) = 957777). Proof: For all 77 E [0,7771], we have g(77) = Z max{77,uJ-}+ Z ( . u‘k . u,k max{77,11,-}Il(max{7'J-, 71,-} 2 77) + max{77, 71,-}Il(max{rj, 71,} < 77)) : 111ax{77,u,~; k} + Z max{77, “1} + Z ( J'E‘I’Lf—Uivk} jE‘I’H-‘I’g'fi—{jka} max{77, 71,-}11(a3- 2 77) + ag-ll(a;- < 77)) = 95,1, (7}) Without loss of generality, we assume Vi,1 g i g n, l; is chosen to be l at line 7 in ith while-loop iteration of Figure 2.1 and thus 77;, s 77;, s --- g 77;". Theorem 2 First Version of Global Convergence: Under the persistent environment, suppose we use 77,(t) = min{77 : gf'(77) = K,}, as the parameter for link I at time t, where {7;(t)} g \II}‘(t) g {77*(t)} U 45(1), and \II](t) 2: {i E \II, : max{7‘,(t),71,~} 2 min 777(3)}, sE[(—T,t] and r is a non-negative constant. Then 3T < 00 such that Vt > T, g(t) = 2’. 38 Proof: Let to = 0 and Vi > 0, define t, :2 t,_1+T,-r+2r,,+(T,- +1)7,,, where T,- is a finite positive integer. We claim that Vk,l S k S 71,Vt 2 t,,,Vi,1 S i S k, 77,,(t) = "i. and Vi, k < i S 71, 77,,(t) 2 771’7' For all t 2 T,,,V1,1 _<_ i S 71, V77 E [0, Mir-911(7) < (J, k-( 77) : 9:27:07) by @3311 = \II,” Lemma 5 and Lemma 6, and thus 77,,(t) 2 77]. In addition, Vt 2 7,, + 7,,Vs E \II,, , 7,7,(t) 2 max{71,, 77’,} by the flow assignment equation (1.4) and thus by Lemma 4, Vt 2 7,, + 27,, 77,,(1) = 77;]. Suppose our claim holds true for some k < 71. Therefore, Vt 2 t, + 7,7,V1', k < i < 71, Vs E \I', — \II°° “1,7,, t = a' and Vs E \I/ookJr1 ,r,,, t 2 max 71,,7’ by . ,. 717,. flow assignment equation (1.4). The following two cases need to be considered: 0 777":+1 = 77sz By Lemma 4, Vt 2 t,c + 7,, + Tu, 77,,+,(t) = 777’“). o 77,,chl > 77“: At line 6 in kth while loop, Vi, k < i S 71 ,gf, (7711.) S gf11(777,) < K1, by Lemma 1, and thus by Lemma 5 and Lemma 6, Vt 2 t7, + 7,, + 7,, (772 (77,2) < gf‘k(77,’k) 2 9272.072) < K,,, and hence 77,,(t) > 771,1“ Therefore, Vi, k < i S 71, o if \II;‘(t) (_Z. @272“, then Vt 2 t7, + 7,, + T + Tu, by Lemma 5, V77 E [0700)9 {_(77) < gfk+1(77); o if \Ilzjlkfl— — (0 and max{rm 7,71,; }— — (111313 "(’1’ where \Ilj‘(t) = {77*(t)}, and thus V77 6 [771,7 00),g,‘,(77)— — 9f +1(77); o if 33 E \117, — W:;k+l,77l’k < max{r,(t),u,} = a2 < 777;“; let 3 E argminjequna’s and |\II]‘(t)| > 1; gfi(a2)— - gffl(a2) < K,, and thus Vt 2 tk+rd+r+r,,,77, (t) > a’ ,and hence either \II"(t t—) - {s }or s E \II}‘(t ); 1f 11: is the former case, Vt 2 tk+T,7+T+T,,, V77 6 [(12,00 ).g7' ('77) < (77“; +1(77); 39 if it is the latter case, we can repeat the process above till \II7‘7 (t) g \112‘7’7':+1 or |\II7‘7(t)| = 1, and have that Vt 2 tk + 7,7 + Tk+1(r + 717,), Where T7,.“ is a finite positive integer, 35 > 0,V77 E [7777+1 - 6, 00), 912(7)) S 9f,’k+l(77); ,k 1 by Lemma- 6) Vt 2 tic + 7-d + Tk+1(T + Tu)avn E [Oanl’k+7laglt, + (77) = 9:91.107)’ and hence 36. > 0,V7'7 E [777’7+1 — (,777777],g7‘7(77) S gk+1(77) and 7777(t) 2 777’7+1 (3,1. due to 777'7+1 < min{77 : (15:10]) 2 K77}. Thus Vt 2 t7. + Tk+lru + 2rd + Tk+lr,Vs E W77“ — \112‘7‘7k+l,r5777+7(t) 2 max{us,777’k+7} and thus by Lemma 4, Vt Z tk+17 7111+: (t) : nil-H. By induction, we prove the theorem. {:1 Remark 8 One interpretation of the theorem of Global Convergence is that we aggressively mark the unconstrained connections but passively unmark the unconstrained connections. That is, if it is an unconstrained connection with respect to current 77, then it should be recognized immediately when calculating the new 77. If it is a constrained connection with respect to current 77, then it is fine if it is miss-recognized to be a constrained connection within finite time except the one with maximum arrival rate. In the followings, we will consider how to reduce the computation complexity for finding the solution of g(77) = K. Definition 1 A(7)-convergence: Given a sequence (17, b2, with lim,Hoe bk = b“ and a constant 7, 0 < 7 < 1, let j 2' inf{i : b7 2 b‘}. If 40 c j = 1 or b1, b2, ...,b7-_1 is increasing but below b*, and 0 j z 00 or bj,b7-+1, is decreasing, and 0 W > 0,1. #1. — 1~ l’)1+1 — [fl S ’7'Ibz' - (fl, then we say {bk} is A(fl-convergent to b“, and denote the convergence by bk _>A(7) b,“ as k —-) 00. Definition 2 My, (SH-convergence: Given a sequence b1,b2,... with bk 47“,.) b* as k —> 00 and constants 6+ > 0,6‘ > 0, let T = inf{i : b,- E [b* —6‘,b* +6+]}. IfT < 00 and Vk > T,b7c = b*, then we say {bk} is A(7,6i)-convergent to b* and denote the convergence by bk —->A(775i) b". For any \IJ,O < [\Ill < 00, (77),“, (“01911. where Vi E \ll,r,- 2 0,11,- 2 0 and any constant K with K 2 2767, 11,-, we want to find an 77* such that g(77*) = K, where g is defined in (2.4) with \IJ" = {7*} and j" E arg maXiEq; max{w, 7,}. Since the function 9 might not be concave due to the non-zero MCRs, therefore, it is reasonable to find the solution iteratively to avoid the computation overhead. Table 2.2 has the description of notations which will be used in the following analysis. If the starting point 77(0) E [77;‘7’7‘.,min\1171,77(] or 77(0) E [max{O, max \1172777{}, 773777.], then we can simply use the slope information hg7K(77) :2 {i E \11 : u,- < 77 S r,} ll(g(77) < K) (2.5) + {iEqu7S77K) 41 [ parameter description 773K177 max{77 : 9(7)) 2 K} 77M min{n 2 9(77) = K} \177777 {max{rimi} : i E \Il,maX{7‘i,Ui} > 775% \Ilgfi {max{r7,u,-} : i E \Il,max{r,-,ui} < 777'7’7‘K} (53K min @2777 -— 7737K 2:77 777,777 —rmax ‘11:; <1 m min - 17.x, (57_(t) 7777777777 — max \11377777 777(t‘) parameter for link 1 after the last update before time t l£(t) in arg min7€7§ 777(t) ngf’ max{n : 921(7) = K1} C,- {l E E : 7771” S 777" } initially 771"“) min{n : 97(7)) = K1} *We let min0 = 00 and max?) z —00. Table 2.2: The notations used for analysis of Local Convergence. and 77(0) + mull—97:76:33)) 77 will be the solution due to g is continuously piece-wise g, ’ linear. We have the following theorem. Theorem 3 Local Convergence: Consider an update rule. For any \II,O < |\II| < oo,(r,~),-Eq,, (71,-)7”, where Vi E \I',r,- 2 0,11,- 2 0 and any constant K with K 2 2767,11,, the update rule starts from a point 77(0) and generates updated sequence {77(k)}, where Vj > 0, ifg(77(j)) = K, then 77(j+1) 2 77(7), to find a solution for the equation g(77) = K and g is defined in (2.4) with ‘1!“ = {j‘} and j“ E arg maxi“, max{u,,r,-}. o If 37,0 < 7 < 1 and 77*,g(77*) = K such that 77(k) —>A(,) 77* as k ——> 00, then 77(t) ai’ ast—> 00, and . in addition, if 77(1) ~77“, 71K, 77‘, then 3T < oo,Vt 2 T, W) = 77’. 9 g. — — 42 where Vs E \II’,(“1S = a, = a2, and (‘1, and (‘1, are the flows resulted from the assignments 2’. and 77_’, respectively. Before proving the theorem, recall that 7777 = min{n : 9:77:07) 2 K77} and consider the following lemma: Lemma 7 If Vkal S k S n7Vi71 S ’l S k,Vj,k S j S ”7771.- 2 771,77 gab-(7717) = K177 I 3) and 7777 2 7777, then Vs E \II77,a2’ 2: a where a’; is the flow resulted from the assignment 77 z: (7771 , 777,, ..., 777,7). Proof: Let k = 1. Since Vs E ‘1177,a2’ 2 max{us, 7777} = (12, therefore, V77 E [07 777m» it is easy to see 96,7,(77) = 92,7700 Hence, if 33 E \II77, a” > a2, then Ve > 0,gc,77(777}:4 + e) > K7, and thus 7771 S 7772‘. Therefore, a2’ = max{us,7777} = max{us,777‘:‘} = a2 by Lemma 3 (apply 7771 as 777 and 7777’ as 77;). Suppose the statement holds true for some k with 1 S k < 71. Therefore, Vs E \II7,,a2’ : (1’ 8’ where 1 S 1' S k. For l7“, since 77 7 __ 7 77 _ 7 Vs E ‘11777+1 — .gk‘ll77,as 2 1nax{us,7777+7} — as and V8 E $777+, 0 gifting“ — as, 1_ 1_ therefore, V77 E [0, 77717727], it is easy to see gc,77+,(77) 2 9577:2707). If 33 E \117777,a2’ > a I 3) then Ve > 0,967,777,077; + e) > K7”, and thus 7777+1 S 7777‘“. Hence a” = max{u,,777’k+l} = max{us,777‘:21} = a2 by Lemma 3 (apply 777’7+1 as 777 S and 7777‘+1 as 772). Therefore, by induction, we prove the lemma. D Sketch of proof for Theorem 3: Since the proof will mainly follow the proof of Theorem 2, we only show the sketch of the proof. In addition, we will show the part for A(7, (Sig-convergence. The part for A(7)-convergence can be done in the 43 similar way. Let to = 0 and Vi, 1 S i S 71, define t7 :2 t,-_7 + T,’, where T7’ is a finite number. We claim that Vk,l S k S n,Vt 2 tk,Vi,1 S i S k,7777(t) 2 7777gf7(7777(t)) = K77. and Viak < 'i E 717777705) 2 777,7.- For all t 2 7“, V7, 1 S i S 71, by the second paragraph in the proof of Theorem 2, 7777‘(t) 2 777; we need to consider the following two cases: ' if 777.(t-) < 7712"“): then 777.“) Z 711T“) or 777710) — 777.“) < Willi-"(U - Unit—l), since 7777(t) will be updated in the way of A(7)-convergence to 7777 (t) where 7772(t) = 7777"(t). Therefore, let 33 E \II77,7777(t’) S max{rs777,us} < 7777"(t), then after some finite interval 777, 7777(t + T77) > rnax{r,.,77,u,} and thus we have have 7777‘(t + T7,) — 67:(t + T7,) S 7777(t + T77) < 777"(t + T77) and we have 7777(t+T77 +tu) = 777:‘(t+T77 +tu) 2 7777 due to A(7, 67f(t+T77 +tu))-convergence. Therefore, ElT,1 < oo,Vt 2 T7, 7777(t) 2 7777. o By the above statement, we have Vi,1 S 7' S n,Vt 2 T,1 + rd,Vs E \1177,r,77,(t) 2 7777. Therefore, if 33 E \117,,71,.,7,(t) > max{777”,u,}, then V6 > 0,717,077? + 6) > K7, and thus 0 S (7771 (t + T7,) — 7777‘) < 7(777l (t) — 7777"). Hence, 3T3,Vt > T72, let I = [57(t) and 777(t) S 7777” due to A(7,67(t)i)-convergence. Let [:7 <— [I] — {l} and repeat the process, we have 3T7 < oo,Vt 2 T7, 977(777l (t)) = K7,. By the similar argument above, the third paragraph in the proof of Theorem 2 and by Lemma 7, we can prove our claim holds true for every k S 71. By induction, we prove the theorem. E1 Remark 9 One interpretation of Local Convergence is as follows: If current 44 link parameter 77 is less than any 77* such that g(77‘) = K, then in the next update, the link parameter should be increased by at least 7(77* — 77), where 7 is a constant and O < 7 < 1. However, if current link parameter 77 is greater than any 77* such that g(77“) = K, then in the next update, the link parameter should be decreased by at least 7(77 — 77*), but the new 77 cannot be smaller than 77 . We consider an update rule which does not satisfy the condition of Local Con- vergence and leads to the thrashing hazard. Example 3 Given Vi E \IJ, u,- = 0, consider the update rule K—Zi r:‘ll(r7<77(k)) . Z,Eiwfl(r,277(k)) 2f 2191: M73 2 ”(kn > 0: 77(k + 1) <— (2.6) K — 21917 ll(7,~ < 77(k)) + 7,. otherwise. To see that the sequence {77(k)} given by the above update rule is not A- convergent to 77“ where g(77") = K with \II" = {7"}, consider the network in the Figure 2.4. Consider the link parameter 772 for link [2. Initially, 772(1) = 4.3. Notice that ‘1!“ : {s3} and 77.7 = 2.05. If each arrival rate keeps constant, then the sequence generated by the update rule will be 4.3,0.9,1.775,2.0333,205,205,205, ...... Since the sequence bounces across 2.05 in downwards direction, therefore, it is not A-convergence. There ex- ists a thrashing hazard for this update rule when the arrival rate is chang- ing. For example, before obtaining 772(3), it is possible that all arrival rates are 0.9 because of 772(2) 2 0.9 and flow assignment equation (1.4). There- 45 Figure 2.4: The network for the counter-example. fore, 772(3) = 4.3. When determining 772(4), all arrival rates are returned to the original values by the flow assignment equation. Therefore, 772(4) will bounce to 0.9 again and thus it is possible that the sequence {772(k)} becomes 4.3, 0.9, 4.3, , 0.9, ...., 4.3, 0.9, Theorem 3 gives a sufficient condition for convergence to max-min fairness. The condition in Theorem 3 is intuitive and will be used to generate a class of update rules. In addition, we have the following corollary from Theorem 3. Corollary 1 Second Version of Global Convergence: Under the persistent environment, let 777(t) defined as follows: 7770—) if 9i(777(t-)) = K77 777(t) = 77 : g7(77) = K7 otherwise, where ‘1!7‘(t) = {77*(t)} (see Table 2.1). Suppose we use 777(t) as the parameter for link I at time t, and \II7‘(t) is defined as in the Theorem 2. Then 3T < oo 46 such that Vt > T, g(t) : 77”, where Vs E \I",a’s’ = a2 and (if; is the flow resulted from the assignment 3”. 2.3 Distributed Update Rules In the following examples, we will let j := arg mama, max{77, 71,} and \II“ = {j}. The further discussion about the usage of \II“ will be in Chapter 4. In addition, we let 77 : minieq, 11,- When 2191: u, = K. 2.3.1 Slow Update Rule (SUR) We consider the following update rule: K-QMM-ID 77(k) (— 77(k — 1) + 7217 To see this update rule satisfying the condition of local convergence (Theorem 3), suppose 77(0) and 77* are lying on the same linear segment of function 9, where g(77*) = K. If g(77(0)) = K, then 77(0) is what we want. If g(77(0)) 75 K, then let A = 9(7) - g(77(0))- Since lg(77*) - g(77(0))! S I‘I’I X In“ - 77(0)I. therefore. 37,0 < 7 S 1 such that 777* —— 77(k)| = A(l — 7)’°. Therefore, 77(k) —+A(,7 77* as k —> 00. Suppose there is no 77* such that it lies on the same linear segment as 77(0). We only need to prove that 3M < 00 such that 77(M) will across the end point of the linear segment, say 77’, which is nearer to 77*. Suppose g(77(0)) < g(77*). Therefore, 77(0) S 77’ < 77*. Let 6 := g(77*) — g(77’). If g(77(0)) = g(77'), then 3A > 0 47 such that 77(k) — 77(k — 1) = A and it is easily to seen that 3M < 00 such that 77(M) 2 77’. Ifg(77(0)) < g(77’), then let A :2 g(77’) —g(77(0)) and we have Vk such that 77(k) < 77’ and 0 < 7 < 1 satisfying that [77* — 77(k)| = (A + e)(1 -— 7)k. Therefore, 3M < 00 such that 77(M) 2 77’. For the part g(77(0)) > g(77“), we can apply the same technique. Note that in all cases, {77(k)} is monotone sequence and 77(k) 371(7) 77* ask—+00. 2.3.2 Modified Slow Update Rule (MoSUR) We can accelerate the Slow Update Rule by using the following update rule: 17(k _1)_7_ 1\'—9(77(k-1)) } ifg(77(k _1)+ K—(JUKk—lll ) : K, 711ax{l,hg77\-(77(k—— 1)) max{1,hg,lx'(7l(k—llll 7707) +- 77(k — 1) + 517%,7—‘13 otherwise, where I197,» is defined in (2.5). It is easy to see that the sequence generated by MoSUR update rule is A(7, 6:K)-convergent to some 77* where 7 is defined in SUR and g(77*) = K. 2.3.3 Algorithm SHARE The last update rule that we consider is simply obtaining the solution of g(77) = K. We use an iterative algorithm as shown in Figure 2.5. The part from line 1 to 7 is to find a new \IJ“ satisfying 377 such that Vi E ‘11 — \I'",max{u,-,r7} < 77 and 276,7, max{u7,77} = K — 276,774,, max{u,-,r,-}. It is obvious that if letting 77’ = max-6,7,4“. max{u7, 77} and 2797,, max{u7, 77’} > K — ZieW—W" max{u7, 77}, then \II" 48 is what we want. If the above condition cannot be satisfied, we need to put all i such that i E argmax7677_.7,u max{u7, r,} in ‘11". Input: a sequence of non-negative numbers (7‘7)7’eq7, a decreasing sequence with non-negative numbers (71,-)7”, a subset \II“ g \II and a constant K 2 276,7, 71,. and previous 77; // Obtain new \II" 1 K’ <— K - Z max{7,-,u,-}; j <— ——1; 1611—1!" 2 while ( Z max{77, 117} 2 K' and \Il“ ¢ \11) or \II“ = 0 do new" 3 ifj 2 0, then \IJ" <— \II" o {7‘}; 4 j <— arg mam-6.77-1771 max{77, 71,}; 5 77 +— max{rj,u,}; 6 K' <— K' + 77; 7 end while; // Obtain 77 8 j (— argmin{u,~ : i E \II“}; 9 U (— \II“; 10 KL (— K’ " 2191:" “i; 11 do 12 U (— U — {j}; 13 KL <—K7,+uj; 14 77 (— 7391777; 15 jt— arg min{u, : i E U}; 16 While 7’] > U}; 17 return 77. Figure 2.5: The iterative procedure SHARE. Once the new \II“ is obtained, we can focus on finding 77* satisfying 2 max{77*, 717} = K — Z max{u,-,r7}. 16W“ iEW—W“ The right hand side of the above equality is denoted as K’. Since it is clear that 77* S K’ — Z 11,- + min ‘11“, we will set the initial value of 77 to be the right hand iEW“ side of the inequality. As in the first part, we partition ‘1!" into two sets, i.e., U 49 and ‘11“ — U, where U 2:: {i : u,- 2 77,i E ‘11"). If 77 S minU and 77: l—‘I’TK-‘T’l’ where K L = K — 17qu max{u7, 7,}, then 77 is the solution. If the above condition is not iE — “ true, then 77 must be larger than the solution 77*. We then take the element, which is minimum of U, out of U. This operation will cause the next 77 be smaller than the current 77 but larger than the value of the element taken out. We will repeat the procedure until the solution is found. Note that 77* may not be unique only when 219177 u, = K’. Therefore, in this case, we will select 77* = min{v, : i E \II"} to validate the equality (2.4). The part of the algorithm to obtain 77* is shown in line 8 - 17 in Figure 2.5. 2.4 Simulation We implement our flow control algorithm on the NIST ATM simulator and conduct our simulation on a multi-broadband-link network which is similar to that used in [28] for simulation. Before starting the ABR services, we let the trace flowing through the links for fifteen minutes to stabilize the predictor. For each ABR session, we set MCR be zero. Each ABR session is best-effort. Furthermore, in each ABR source, we set RIF to be 0.0625 and peak cell rate to be 149.76 Mbps. Figure 2.6 shows the multi-broadband—link network system. Each link has capacity 149.76 Mbps and the same background trace as mentioned in [44], with different starting point runs through each link ’BBi’. The trace has mean around 126 Mbps. In addition, the output buffer size in each switch is 2000 cells. To decide K7, let Y0, Y7, Y1, Y3, be the time series of VBR and CBR traffic. 2 50 BB1 382 883 884 31771 317772 917173 31174 31775 100Km 100Km 100Km 100Km Wm; 774sz Mm $Km Wm; ka Figure 2.6: The network topology. The session i has source s,- and destination d7. Let Y0 E 0. The variable Y; is the number of bits in the VBR and CBR trafic arriving to the link 1 during the time period ["—;1, 2). Therefore, at time t E [7, 3221) where v is a non-negative integer, K7 2 C7 — 2Y2 — k, where C7 = 149.76 Mbps. We arbitrarily set K. = 1 Mbps. The interval between each two updates for feedback rate is set to be 10ms. Figure 2.7 shows the simulation results. As the simulation results show, the algorithm SHARE has the fastest transient response, and the update rule MoSUR is very similar to SHARE except at time 5.1 second, the response of ACRs of session 4 and 6 is a little bit slow. In most of time, the session 1 and 2 have the minimum ACR. 51 41 7 7 7 Session 1 ----- 34 .. Session 2 """" _ Session 3 a Session 4 ---------- 3 27 - Session 5 —- - g Session 6 ----- 5 20 _2 ............................................. a, <2 ......................................................................... 13 :1- -- -- -. f .................................... 4¥ ------- f: ------------- :- 6 -1—— r '""""""¥'"9—---—-———-—7--———--~~-—— 4 4.5 5 5.5 6 time (sec) (a) ACRs when using SUR. 41 l 1 l Session 1 ----- 34 _ Session 2 ------ _ Session 3 7,; Session 4 ---------- f3- 27 - Session 5 — - g Session 6 ----- ES 20 < ................................................. 13 71---.-- E m. ___________________ F _4.‘_ n 1...: 6 r f ”- ‘fi “— 4 4 5 5 5 5 6 time (sec) (b) ACRs when using MoSUR. 41 7 7 7 Session 1 ----- 34 _ Session 2 ------ - Session 3 7,; Session 4 ---------- 3 27 ~ Session 5 _, g Session 6 ----- 8 20 '.'. ........ < 'w 13 TLW 7— fi:__________________7:"‘"‘"‘"""~‘ 6 ——l__-__.__———I———a__—————'-———"“"'-—I———_.J‘ _-—-_-————I ----- ___. ..... ... 4 4 5 5 5 5 6 time (see) Figure 2.7: (c) ACRs when using SHARE. The simulation results for multi-broadband—link network system. 52 Chapter 3 Bounded-Cell-Loss-Ratio Flow Control Transmitting data with low data loss ratio is a basic requirement for future B- ISDN networks. Likewise, the capability to support a large number of destinations for point-to-multipoint data transmission is strongly dependent of the packet loss ratio. The loss ratio also plays a major role in the multimedia transmission with the quality of service (QoS) guarantee. More precisely, in real-time application, the buffer size in a switch should be restricted to bound the transmission delay. This leads to that the loss ratio will be increased if the data sending rate is not well controlled and thus the quality of voices or pictures will be degraded. More- over, from the viewpoint of the network system, the loss ratio always has great impact on the network effective throughput and thus on the network routing and dimensioning. There are several ways to carry out the low loss ratio property. First, when a 53 available _ _ P 1117937113172 _ loss ratio limiter total. serv1ce 7 rate : residual ABR sessions ABR queue 7 bandWldth 7 prediction l I l VBR and CBR sessions ‘ ‘ ‘ . traffic predictor Figure 3.1: The Components for BLCR flow control. call arrives at the boundary of the network, the network will allocate the buffers and bandwidths along the chosen path according to the traffic description. A call allowed to be set up will be associated with a mechanism in the network entry to police the traffic. In each switch along the route of the call, a trafic shaper in front of the link in the route can be employed [45]. Second, the application can adapt to the network current status to adjust the sending rate, i.e., use flow control, so that the loss ratio can be reduced. The former approach is usually dedicated to the higher priority traffic, and the latter one is designed to enable high network utilization. In this chapter, we study how to bound loss ratio by the flow control. 3. 1 Framework In this section, we give the framework about how the flow control algorithm func- tions. In Figure 3.1, we show the relation between each component which we will discuss as a subsection in the followings. Table 3.1 gives the description of notations which we will use in the followings. 54 ] Label ] Description ] Units Y7 + Cyt fluid process for VBR and CBR traffic cells ”7, Y7; - l“"_7._;_1 cells W7, prediction of W7c cells U7c le/Vk cells U7c prediction of U7c cells U77), truncated version of U7c with degree (1 cells {27,} an i.i.d. process cells 2; prediction error defined as W7c —- W7, cells S7 service fluid process for queue cells A7 arrival fluid process for queue cells k amount of negative drift cells per second* X, St — A7 — kt cells Q7 queue length process cells :7: buffer size cells K total feedback rate cells per second 77 feedback rate to each session cells per second* 71, MCR for session 7 cells per second 7,- CCR for session 7 cells per second <7 current service rate for link 1 cells per second R7 summation of CCR5 of sessions via 1 cells per second ‘117 index set of ABR sessions through link l - 7‘ index set of unconstrained sessions for link I — * (Mbps in simulation) 3.1.1 Bandwidth Predictor: On-line Estimation for FARIMA model Let Y, + Cyt be the fluid process for VBR and CBR traffic, where Vt,lEY7 = 0, and W7, :2 Y; -— 10727, i.e., the aggregated process per 0.5 second. We treat {W7} is an FARIMA(1,d, 0) process and use a simple method for on-line estimating and prediction for the FARIMA(1,d,0) model. Let D be a finite set {% : i E {0, 1, 2, ..., T}}. With each value in D, an expert is associated and the expert uses this value as its degree d in FARIMA(p. d, 0) model. Each expert obtains truncated 55 U7, denoted as U7, as follows 100 U777); = Z 77,-(d) VVk_J-, 7:0 and then treats U777. as an AR(1) process and uses the ordinary weighted least squares estimation [46] for the parameters. Each expert will generate its prediction according to (1.1) with replacing U7c by U777. To conclude the predictions by these experts, we use a technique called Hedge Boosting [47] with B = 0.1. Figure 3.2 shows the autocorrelation function for the trace which we will use in our simulation. As shown in figure, the autocorrelation function for the trace will not decay to zero until the time lag is large. The trace consists of twenty different thirty-minute MPEG traces 1 and each of them will be repeatedly and sequentially read to generate the final trace for thirteen times but with diflerent starting point. When reading the last frame in an MPEG trace, we will wrap around and start to read the first frame. The total expected bandwidth needed for the traces is about 126 Mbps. In Table 3.1, we show the average squared prediction error by each expert. Each expert aggregates twelve frames as its W7. The best degree d is around 0.4. The Hedge boosting appears to be a better predictor since the best d will change during the trace running. We also show the squared prediction error when treating the underlying process {Wk} as a random walk process. Its squared error 1The traces are fetched from the site ftp-inf03.informatik.uni- wuerzburg.de/pub/MPEG. Each item of data in each trace stands for the number of bits per frame. 56 autocorrelation 0 30 60 90 120 1 50 1 80 time lag (sec) Figure 3.2: The autocorrelation function for the trace. is 8% more than that of Hedge boosting. As we will show in the next subsection, the squared error is directly related to the bandwidth utilization. We also show the squared prediction error produced by the best linear predictor generated by the Durbin-Levinson algorithm [22], which needs the autocorrelation function in advance. It indicates that there is still a lot of space to improve the on-line predictor. The last item in Table 3.1 is the average squared error if using the mean as the predictor. The error is almost three times larger than any other predictor. Let W7, be the prediction generated by Hedge boosting for Wk. Figure 3.3 shows the autocorrelation function for the prediction error process {27,} = {W7c — Wk}. As shown in the figure, {27,} is uncorrelated. In the following analysis, we will assume {27,} is i.i.d. 57 0.8 7- - 0.6 - _ 0.4 L — autocorrelation 0.2 t .. 412 I 1 1 l l 0 30 60 90 120 1 50 1 80 time lag (sec) Figure 3.3: The autocorrelation function for the prediction error process by Hedge boosting. 69+06 l I I I 5e+06 » v: —— — - E(Z_1*Z_1)‘21 ----------- ' 4e+06 1 3e+06 squared error 26+06 .I” I \ l 16+06 2 xv' a I O r l 1 1 l tune Figure 3.4: The plot for IEV,2 vs. time lag 1. 3.1.2 Loss Ratio Limiter: The Decision of Linear Drift 71 Let C7 stand for the link capacity. Therefore, we have the relation for service fluid process 57 as follows: 5, —so = (C7 —Cy)t—Y7. In addition, we let Vt, IEY,2 < 00. Let the total feedback rate for ABR sessions at time t to be K7 2: C77 - 2W“, where M 2 [2t]. Therefore, we have the relation for the arrival fluid process A7 as 58 predictor average squared error ] d = 0.0 5441007 d = 0.1 5431205 d = 0.2 5387331 d = 0.3 5371501 d = 0.4 5365298 d = 0.5 5380291 (1 = 0.6 5459099 (1 = 0.7 5542284 d = 0.8 5642833 d = 0.9 5826337 (1 = 1.0 5957649 Hedge boosting 5361959 random walk 5919789 Durbin Levinson (ofl-line) 4431095 mean 16652184 Table 3.1: Squared errors for each predictor. follows: A7—A0 = [KdS-i-thi) iE\II 11’ _2717 M+1( (t— L“)— iE\lI )—2vik+2g, +071, where Vi E 41,112,") = 0. We have the following relation for X7: Xt—XO '2 At—Ao—St'i'SO M = 13—10—2777,,1(7———2vi’7+ k:1 iE‘ll Assume X7 is Gaussian and has stationary increments. 2510+ (CA-CY +Czlt- LetV7::Y7—Yfl— 2 277/77,,(1— %). As Figure 3.4 shows, we can assume that IEV,2 z 2(1— 1‘21)EZ7“. We then have the following theorem: 59 Theorem 4 Assume that the following condition holds and assume that V, is uncorrelated with 27, 22, Proof: 17277.1(, -— X_,) aTmar > 01Vt7 1'E\Ilu 11777.1(, — X_,) z 2114:2771, V (17' ( X7 — X77) IE Y, — 17% — 27777.1(: — — Z 55“] 2 1911 17:7 Z 677 E 17—10—21177+7t—— << E277,,,,,,. (3.1) ,277. We have Vt 2 774,701,. (3.2) 2 -Z ”7: + 2511)“ 258)] iE‘lI iE‘II M M A. 1' 3) + (Wk — Wk) + :57“ k=:1 iE\II 113(l7+kZZ:Z7)2)€77)-)2(21E[11+:Zk)(l026-€((7z))] iE\lI Wk: 71’— 1E\ll M 1EV72 + 1171732,? — 217:](14 + 2 Z7.)(2 £7") — 68'0] k 1 1'qu +114: 65” — 191' 11:17",2 + 171st — €((772)113[(1 +IE(Z 57‘"— 16W“ 2+IE( 60 (’t'i'ZZkl (2511)— 161'“ £515] -£.§"’)‘ (275" 1E‘P— \II“ by the assumption that V, is uncorrelated with 21, 22, ..., 2M and the Assumption 1. Then by Schwartz’s inequality, (3.1) and Assumption 2, we have 1 x7. "r ' ' 2 77,777)“ _ X_,) g 17:17,2 + 171325 + 2 [(1317,2 + 1111327271772 .57") — £5'))2] iE‘lIu +E(Z€fi’.—€‘JL>2+E< Z €5”-€8")2 1E1!u iEW—W“ a: 2E272t, Vt 2 77,707,. If we want to bound the loss ratio above by 6, then, by (1.2) and (3.2), we have the following: KT 8X --—7— :36. 3J3 p] 7721,] .1 < > Our duty is to obtain the smallest k to satisfy the above inequality. Therefore, we should let C A = C7 — Cy — k and let the total feedback rate K :2 CA — 2WM at time t. Recall that 1, ~ 7‘- in (1.3). Therefore, in order to have (3.3), we needs :17 a: (3.4) Tfll-(LIL' We will assume 7mm, as the maximum round trip delay. The reason why we choose 7mm. in this way is simply by observing the experiment results and the proof of Theorem 5 in the next subsection. In practice, we set 7",“, = 0.1 for the interactive 61 application. Suppose x = 2000 cells, then 71 S 20000 cells per second (8.48 Mbps). In our simulation, we will see in general it is the case. 3.1.3 Bounding Total Rate To bound the total rate, we first need to distinguish whether a session is an uncon- strained one. Then we use the algorithm called SHARE, introduced in the previous chapter, which can bound the expected total arrival rates by a given number. In addition, under the persistent environment, i.e., all the sessions are best-eflort and the available link capacity is constant, we prove that the algorithm will converge and the utilization of the bottleneck link will reach the given number. Marking Unconstrained Sessions In previous section, we have discuss the partition of the set of sessions \II7 for link 1 according to the location of bottleneck for each session. That is, if the session’s bottleneck located in the link, then we claim it is a unconstrained for link 1; otherwise, it is constrained for i. We aggressively detect the session to be a unconstrained one. That is, for a fixed number J, e.g., the maximum round trip delay between each pair of source and switch, if r,(t) 2 7_Jr§rigrsit_1n7(k), then the session 3 will be recognized as being unconstrained for 1. Otherwise, session 3 will be constrained. An easy way to implement this concept will be using a shift register 77 for 777. At the step k, register 77 will keep the values 777(k), 777(k — 1), ..., 777(k — i) where t,,, is the time between two steps. Let min 777 denote the minimum value in 777. If r,(t) 2 777*, then session 3 is unconstrained for l at time t; otherwise, it is 62 constrained. Theorem 5 Bounding Total Arrival Rate: Suppose we deal with a single switch network system and there exist N ABR sessions which are all unconstrained. Given K, at time t, we use 777‘ , the solution in Problem 1 with replacing K by K 7, as the feedback rate, then with Assumption 3 and assuming that for each session, the delay for a cell traveling from the source to the switch is bounded, then 36 > 0 such that t. -1 / sts — 6 S A7 — .40 S / K,,.ds + 6 0 0 where A, is the arrival fluid process. Proof: Let (7“) denote the sending rate for session i at time t. Then 27:7 C“) 2 K7, where 7“”) is the delay for sending a BRM cell from the switch t+7(b~‘) to the source for session 7. By Assumption 3, 7“”) is constant. Therefore, t N N t+r(b"l t (smds + (/ Csds —/ Cylds) =/ sts [o 72:; 7:27 t 0 0 Since if the delay for a cell from the source to the switch is bounded, say above by ,an) 7’ we have 1710.111 ’ I t_Tmaa: N / ch‘wssAi—Ao 5] T! T' max {:1 _ max I t+Tmar 1V (yids. (3.5) i-l 63 For the lower bound of (3.5), we have .t—Trlnux N 7 't N 7 Trina): IV _ t N / Z (finds : / Z duds — / Z (yids — / Z (SMdS Trina: i=1 0 1:1 0 i=1 t—T’ mar i=1 t N HAW = /K,ds—2(/ C,ds+/ 0 7:7 1 0 t . +/ C2'lds) l 7’ — ma .1: ,(bn‘) Tint”: 7 C2'lds +/O (Smds Since Vi,Vt,(,(i) is bounded, and we repeat the similar procedure for the upper bound, therefore, the theorem is followed. El Remark 10 It is easy to see that Theorem 5 implies (3.1). Remark 11 Suppose the network has multiple switches. For the uncon- strained sessions for a link, we can still have the same relation as (5) but with replacing K, by K, — 2767,7477, max{77, 717}, where ‘11, and ‘11: are the index sets for ABR sessions and unconstrained ABR sessions for the link at time s, respectively. Therefore, we can have (3.1) and obtain the result in Theorem 4. In this way, the negative linear drift k can be derived to bound CLR. Using this n, we can still have the upper bound for CLR even when Vs, the actual total feedback rate K; S K, - 2797,54,, max{7,,u,-}, i.e., resulting from (1.5), because of Proposition 1. Remark 12 Theorem 5 holds even when 77'," will not converge as t —> oo. 64 The algorithm SHARE has the worst-case time complexity O(|\II|2) due to the ' summations inside the loop. If the time complexity is really an issue, then one can relax the resolution of 77 for finding the solution of (2.4) by binary search. However, the approximated solution 77* should satisfy g(77*) 3 K. The number of search steps can be set to whatever the processor can handle. In the following analysis and our simulation, we use the algorithm SHARE. Backward Congestion Notification by Switch When the available bandwidth decreases, the frequency of the feedback rate back to the source. In this way, the source will keep sending the cells with higher rate for a longer time and thus the buffer will be saturated. To avoid this problem, whenever feedback rate decreases, a timer is set. If the timer is expired and the session has no BRM cell flowing through during the timer ticking down, the switch will generate a BRM cell sent back to the source. 3.1.4 Overall Flow Control Algorithm The overall flow control algorithm is listed in Figure 3.5. 3.2 Two Loss Priority Traffic Stream Suppose a session has traffic with two loss priorities. For example, a traffic stream with the same virtual circuit identifier has cells with difierent loss priorities. In [13], either the relative-rate—based or ER—based flow control is on the data cells with low 65 End of Estimation Interval (e.g., every 0.5 sec) 1 Obtain K according to the previous subsection End of Measurement Interval (e.g., every 10 milli-sec) 2 if 771 < 17, then 3 for each VCEM—Rdo 4 generate BRM cell for V0; // BC’N 5 end for; 6 end if; // detect constrained and unconstrained sessions 7 for each i E C do // C : the set of total sessions 8 if n1ax{r,,u,~} < min 7‘], then ‘11“ (— \II“ — {i}; 9 else \II“ +— \II“ U {i}; 10 end for; // obtain 77 11 \IIe—qtuuMua;//G:={izu,>0} 12 771 +- 77; 13 if K 2 2,60 u,, then 14 77 +— SHAREOD“, {Ti}(i6\l¥), {u,}(,-E\p), K, 7}); 15 else 17 +— 0; 16 end if; 17 push 77 to 1); 18 M <— (l); R <— (2); When a cell with V0 is received 19 M +— M U {VC}; // session V0 is effective When an BRM cell with V0 is received: 20 ERJn_RM_Cell <— min{ER_in_RM-Cell, n}; 21 R <— R U {VC}; When a FRM cell with V0 is received: 22 TVC (— CCRJDEM-C€11. Figure 3.5: The flow control algorithm in the switch. loss priority (CLP = O), i.e., the in-rate cells. The data cell with high loss priority (CLP 2: 1), i.e., the out-of-rate cells, is not allowed. Here we propose that ER- based flow control and relative—rate—based flow control will be on the cells with low loss priority and high loss priority, respectively. We use a simple buffer management to bound the loss ratio of low-loss-priority traffic. Consider two buffer management schemes in Figure 3.6. Let b + h denote the total buffer size where b, h > 0. If a cell with CLP = 0 arrives, then the cell is 66 At _—_> w 0‘ 0 ,. At 5 4 : } ‘ 1 . At _u ,. .. I‘— h —’| Figure 3.6: Two buffer management schemes. allowed to enter into the buffer if there is an empty space in the buffer. However, a cell with CLP = 1 is allowed to enter‘into the buffer only if the buffer length is less than h. To bound the loss ratio for the cells with CLP = 0, we can simply apply the algorithm in Figure 3.5 with only considering the cell with CLP = O. For the flow control of cells with CLP = 1, we can use the binary fields NI and CI. That is, if the buffer length is larger than a positive constant hl which is less than h, then NI 2 1 in the BRM cell. Moreover, if the buffer length is larger than h, then CI 2 1 in the BRM cell. The source will simply check NI and CI fields in the BRM cell and follows the operation specified in [13] for the cells with CLP : 1. Then we can bound CLR for cells with CLP : O by the following theorem: Theorem 6 Consider two bufier management schemes in Figure 3. 6. If A? E A, and Vt g 0,14, :- 0 and A} E 0, then we: > x) 2 M2? > x + h), where Q} and Q? are queue length processes for buffer management scheme 1 67 and 2, respectively. Proof: We claim that Q,‘ 2 Q? — h. First, when Q? g h, then there is nothing to prove. Since Q}, = O and Q3 2 0, therefore, let to defined as follows: t0:=i1‘1f{t :Q,1 2 Qf — h. = l,Q,l_ 2 (2,2- — h =0}. If to : 00, then there is nothing to prove since either Q? — h S 0 always. Suppose to < 00, then let t1 defined as follows: t1 :=i11f{t:Q,1- Z Qf_ — h. =1,Q,12 Qf — h = 0}. Note that t1 could be infinity. Let k0 = Qth— §0+h. Then Vt E [t0, t1], Qfi—Q‘fo-th = k0. If tm, tm+1 < 00 where m 2 0 is even, then we define tm+2 as follows: tm+2 :2 inf{t > tm+1 :Q,1 2 Q? — h :1,Q,1- 2 Q3- — h = 0}. If tm+2 < 00, then we define tm+3 as follows: tm+3 := inf{t > tm+2 : Q}- 2 Qf. — h =1,Q,12 Q3 — h = 0}. Let km+2 : Qfimw — Qfm+2 + h. It is easy to see that Vt E [t,,,+2, t,,,+3], Q,l — f0 + h 2 km”. Therefore, we prove that, by induction, during the period Q? > h,Q} 2 Q? — h. Therefore, we have the claim and the theorem is 68 followed. E] To provide the further fairness, we can discard the cell with CLP = 1 when the queue length is larger than hz, where h, < h; < h, and the arrival rate for cells with CLP : O of the session is larger than 17. We will discuss the application of this scheme in [48, 49] for fault-tolerant and reliable multicast. 3.3 Simulation We implement our flow control algorithm on the N IST ATM simulator and conduct our simulation on a one-broadband-link network system and a multi-broadband- link network. In both simulation, before starting the ABR services, we let the trace flowing through the links for fifteen minutes to stabilize the predictor. For each ABR session, we set MCR be zero. 3.3.1 One-Broadband-Link Network Figure 3.7 shows the one-broadband-link network system. The bandwidth for ’BBl’ is 149.76 Mbps. We use the trace, mentioned in Section 3, with mean around 126 Mbps, as the background traffic through ’BBl’. As in [28], we assume the mean of the background traffic is known in advance. Furthermore, in each ABR source, we set RIF to be 0.0625 and peak cell rate to be 149.76 Mbps. The allowed loss ratios will be 1%, 5%, 10% and 20%, respectively. Figures 3.8, Figure 3.9, and Figure 3.10 show the simulation results. As the results indicated, CLR is bounded above by 69 .. sw1 sw2 lOOKm £Km 6 Figure 3.7: The one-broadband-link network system. The session 1 has source 31 and destination (1,. the given number with a factor about 20 while the link total bandwidth utilization is above 96% since r»: < 5.5 and by the formula 149.76 — K. b d . .1. . = an Width ut1 izatlon 149.76 1.4 1.2 ~ 2000 0.8 L 0.6 F 0.4 - 0.2 r- CLR (°/o) when x time (sec) Figure 3.8: The loss ratio when x = 2000 in the one-broadband—link network. Figure 3.11 and Figure 3.12 show the loss ratios for buffer size being 1000 cells and 5000 cells, respectively. As the results indicate, the CLRs for buffer size being 1000 cells and 5000 cells are similar to that for buffer size being 2000 cells. 3.3.2 Multi-Broadband-Link Network 70 5.5 r I 1 I WW I 1 ...._,..r:""-~-/‘-~-\. . ...l 5 ' """ ‘ ‘ ‘ """ i "'_ 4.5 20% - 10% ----- <0 4 ' 5% ----- - x ____________ - .. 3 r- " q 2.5 t--- ____,__. ...... - ....... ___,‘_"\.. ““““ ‘ ______ : - -~“‘--§,;‘-'~-~-—"- ------------ ""‘--'-su 2 u 1 1.5 W 1 6 11 16 21 26 31 36 41 time (sec) Figure 3.9: The h: when x = 2000 in the one-broadband-link network. 6 l l I l 4 L _ A 2 ~ - (D e o - ...1 ‘2’ 2 E - s -4- ~ 0.. '6 _ .1 -3 - _10 l J l J 1 9 17 25 33 41 time (sec) Figure 3.10: The bandwidth prediction for x = 2000 in the one-broadband-link network. Figure 3.13 shows the multi-broadband-link network system. Each link has capacity 149.76 Mbps and the same background trace with difierent starting point runs through each link ’BBi’. Each ABR session is best-efiort. We set J = 0.1 sec- ond for marking the unconstrained session. Figure 3.14-3.18 show the simulation results. As the results indicate, CLR is again bounded above by the given upper bound which is 1%. As Figure 3.18 shows, the session 1 and session 2 always have the smallest ACRs. In addition, the convergence to the new equilibrium is very fast. We observe that there exists the rate overshoot. It is due to the rate change of constrained sessions. However, for the minimum feedback rate, there will be no 71 2000 CLR (%) when x time (sec) Figure 3.11: The loss ratio when 1: = 1000 in the one-broadband-link network. 1.2 I I l 1 l 8 1 ~ 2 ll 08 .. X C 2 0.6 - 3 g: 0.4 - S o 0.2 '- 0 time (sec) Figure 3.12: The loss ratio when :1: : 5000 in the one-broadband—link network. rate overshoot. This result is implied by the proof of Theorem 2. Around time 5.3, the session 6 raises its rate since the switch ’sw2’ recognizes that the session 1 and 2 are no longer unconstrained for the link ’BBZ’ from ’sw2’. The current bottlenecks of session 1 and 2 are at link ’BB3’ from ’sw3’. 72 881 K Figure 3.13: nation d,. le le 100Km 882 100Km IKm ‘Km The second network topology. The session i has source 3, and desti- sw3 BB3 Mm; 100Km 100Km $Km sw5 O~35 I I I I I I I I I """ sw1—BB1 — 0.3 '- swaggg ..... “ ’3 sw3- ----- 2\’ 0.25 [ """ sw4.BB4 .......... -1 .9 E 0.2 - ,,,,,, ‘ 2’ CASE ~ MT 78 0.1 g ................... .— 0.05 - E ‘ 0 l l l l l :L l J J 1 2 3 4 6 7 8 9 10 11 12 time (sec) Figure 3.14: The loss ratio for multi-broadband—link network system with x = 2000. 5 L--. I I SWI-BB‘P __ I I;—--: I I I I l--- SW2-332 """ E “"1 ---- ------- i--.“ ’«T O. .0 2 (U D. O. (U x 4.4 1 m l l 1 l l 1 1 1 2 3 4 6 7 8 9 10 11 12 time (sec) Figure 3.15: The r: for multi-broadband—link network system with x = 2000. 73 predict (Mbps) I I I I sw1_BB1 _._L_ I I I j p sw2-882 -------- it; """" _ sw3-BB3 l... time (see) Figure 3.16: The bandwidth prediction for multi-broadband-link network system with x = 2000. eta (Mbps) 24 I I I SIW1-BB1I _ I I I I 1 22 _. sw2-332 ----- - 20 ” sw3-BBS ----- 18 . sw4-BB4 .......... 16 . ................. E 1 -------- _ 14 ......... j “””' .................... .. 12 r- .......... 3.--. ---1 ..... j 10 -. ............. I _________ a ,1-.. . 8 .~: ------ e _s a, ,---1 I".---. — 6 F--.—-’----- ---’ .---.-—----- -. -.. ..---. ..-.----. ____3::.-.~:__Jfr-.-.i--_‘-“ 4 l l l l l l l '---f' l - -- l ..... 1 2 3 4 5 6 7 8 9 10 11 12 time (sec) Figure 3.17: The 77 for multi-broadband-link network system with x = 2000. ACR (Mbps) 20 18 16 .................... z I I I I I r I l I ................... 1 g ............ Session 1 ..... —1 593310112; ........ +-| . ~ 3 suon3 d 5 5.5 6 time (sec) Figure 3.18: The ACRs for multi-broadband-link network system with x = 2000. 74 Chapter 4 Error Control for ABR Multicast Lossless data delivery for multicast communication (reliable multicast) is necessary for some applications, such as distributing the information of stock markets. In this chapter, we study how to extend the flow control of ABR multicast for reliable multicast. The output buffer for the ABR streams in the switch is implemented by a single queue, such as the buffer in a virtual path [10]. When the queue is full since the total available bandwidth for the whole ABR streams is suddenly reduced, the incoming ABR cells will be dropped, even those belonging to an ABR stream below the fairshare, and thus a loss will be detected in the downstream receiver. Therefore, though the allowed cell rate for each ABR stream will be reduced according to the max-min fairness, the bufier will not be managed in a fair manner. As a result, the cell loss may occur in the link where it is not the bottleneck for the multicast communication. The above observation leads to the idea of using the virtual connection, a partial connection, which is built by the feedback information for error control, atop the existing connection for the data 75 retransmission. That is, we can retransmit the data only to the receiver requesting it with carefully detecting the status of the link as well as filtering and directing the data by the switch without violating the max-min fairness. Another advantage of using ABR flow control to carry out reliable multicast is that by allowing the resource management (RM) cell, originally dedicated to the flow control, carrying the information for the error control, there is no need to send any other feedback message. In addition, the fault tolerance will be coped with by the flow control algorithm and thus relieving the workload for the error control algorithm. 4.1 The Error Control Algorithm In ATM networks, the resource management information is carried by resource management (RM) cell. To convey the error information, we let the backward RM (BRM) cell carry a non-negative integer SRX (sequence number of retransmitted packet) and an error indication bit EI. If an error is detected in the receiver, then assign SRX with the smallest sequence number of the packet needed to be retransmitted, and set EI <— 1. If there is no error, then assign SRX with the number of which the receiver expects to receive next, and set EI (— 0. The sequence number can be IP packet sequence number. Upon receiving a forward RM (FRM) cell, the destination will assign SRX and EI decided by the associated receiver and then turn the cell back as BRM cell. The switch error control algorithm is the critical part for reliable multicast. 76 We assume all switches in the network implement explicit-rate based flow control algorithm.1 Therefore, the congestion indication (CI) can be used to indicate the current queue situation along the path where error may occur. Upon receiving a BRM cell with El :2 1, the switch error control algorithm should configure the virtual connection accordingly. The algorithm should satisfy the following three criteria to guarantee correctness: deadlock free: Deadlock will occur if there is a permanent wrong configuration in the virtual connection so that some receivers are always unable to get the packet they requested. For example, the receiver r1 requests packet [31 and receiver r2 requests packet p2. The virtual connection will not be changed until r1 has received 1)]. The sender will keep retransmitting 191; however, the virtual connection always directs the packet only to 7‘2. starvation free: Starvation could occur when the error information of the lost packet never reaches the source. livelock free: Livelock could happen if the switch keeps changing the configuration of virtual connection and thus the receiver cannot get the packet it requests within a finite time even under the condition that there is no data loss after the receiver requests the retransmission. Note that under the assumption of no data lost after the receiver requests the retransmission, if these three criteria can be guaranteed, the receiver will always 1The flow control algorithm of large-scale multicast communication cannot only use the binary congestion indication from all links in the connection. Otherwise, due to the unfair buffer management, the allowed cell rate (ACR) of the multicast communication will be around minimum cell rate (MCR). 77 get the packet it requests eventually. To satisfy above three criteria, we implement the strategy called smallest first. That is, the switch always picks up the possible smallest sequence number of the packet requested for retransmission as far as it knows to configure the virtual connection. Therefore, the receiver requests the packet with the smallest sequence number will eventually obtain the packet, and within finite moment, each receiver will have its requested packet with the smallest sequence number. We show a switch error control algorithm in Figure 4.1, which modifies the fourth algorithm in [15] for flow control. The constant 7 is determined by the correlation of two packets being lost. The strategy smallest first is imple- mented in lines 5 and 21. The parameter PCR stands for peak cell rate. MER, MCI, and MN I, being PCR, zero, and zero initially, respectively, are the registers for flow control. MSRX, MEI, MCN (maximum completion number), and CCN (current configuration number), being 5, zero, 6, and fl initially, respectively, are the registers for the error control. We assume the sequence number of any packet is less than [3. For each branch 8, as, which indicates the arrival of BRM cell, and be, which is for the filtration, are the binary registers with initial value zeros. The switch error control algorithm in Figure 4.1 is conservative since it leads to the sender waiting for all receiver’s requests before retransmitting the data (lines 16 and 17). Therefore, it will save the retransmission traffic but the delay of the retransmission will depend on the longest round trip time among all the pairs of source and receiver. 78 For every branch point v: 0 Upon receiving a BRM cell with BN=0 from branch e, H 20 21 22 23 24 25 26 27 MER +— min{MER, ER}; MEI <— (MEI OR EI); if EI : 1, then MSRX +— min{MSRX, SRX}; else MCN (— min{MCN, SRX}; end if; ae <— 1; CCN (— min{CCN,MSRX}; if El 2 1 and SRX g CCN + 7, then be (— 1; MCI <— (MCI OR CI); MNI <— (MNI OR NI); else be <— 0; end if; if for each branch 13', a8: = 1, then for each branch e’ with by = 1, obtain CI and NI of the output buffer to e’; MCI +— (MCI OR CI); MNI +— (MNI OR NI); end for; if MCN < MSRX, then MSRX +— MCN; MEI +- 0; end if; pass the BRM cell to source with ER +— min{MER, min{C(e’) : t(e') = v}}, CI <— MCI, N1 +— MNI, EI (— MEI, and SRX <— MSRX; if for each branch 6', by = 0, then CCN <— [3; else CCN <— MSRX; end if; MER (— PCR; MCI (— 0; MNI <— 0; MEI <— 0; MSRX <— 6; MCN <— {3; for each branch e’, a8: <— 0; else discard the BRM cell; end if. Figure 4.1: The switch error and flow control algorithm. 79 ACR; <— ACRu; if ACE, > ER, then ACRe, <— AC& + AIR; end if; ACR.” <— max{min{ACR,,, ER}, MCR}; if CI = 1, then ACR, +— .4CR,, — ACR, X RDF; else if q, is empty, then 10 ACR,“ (— 0; 11 else 12 ACE, +— ACE, + AIR — max{AC'Ru — ACRL, 0}; 13 ACR” (— min{ACR,,, PCR — ACR“); 14 end if; 15 end if. OOKICSCfloh-OOMH (D Figure 4.2: The decision rules for ACR" and ACR, when a BRM cell is received. The parameters RDF and AIR stand for rate decreasing factor and ACR increasing rate, respectively. Upon receiving a data cell, the switch with single out-going branch will send it via the branch. If the switch is a branch point, then the switch multicasts the data cell to each branch 6 with be 2 1 if it is a virtual cell, and multicasts it to all its branches, otherwise. The destination implements two queues for reassembling, one is for virtual cells and one for the other data cells. Upon receiving a BRM cell, the source will determine the ACR for virtual connection (ACR”) and ACR for underlying connection (ACRQ. The goal for assigning ACE, and ACR,“ is to fully utilize the possible available bandwidth subjective to satisfying the source behavior given in [13]. If there no cells in the retransmitted queue qr, then ACR, = 0 always. The decision rules for ACE, and ACR“ as shown in Figure 4.2. When the received SRX in the source is larger than the previous one, the source returns this number to the sender along with El. When sending an FRM cell, the source always assigns the field current cell rate 80 (CCR) with ACRe. Upon receiving SRX and EI from the source, the outstanding packets with sequence number smaller than SRX in the sender will be taken out from the list in the sender. In addition, when El 2 1, then cells corresponding to packets with sequence number in [SRX,SRX+7] will be put into q, in the source if the packet with sequence number SRX has not been retransmitted. These packets are called retransmitting packets. Before putting the cells corresponding to transmitting packets to qr, the timer will be reset and old cells in q, will be discarded first. When a timeout occurs, if the last EI : 1 and SRX is larger than the sequence number of the first retransmitting packet at the point that the timer was reset in the last time, then the cells corresponding to each packet with sequence number in [SRX,SRX+'y] will be inserted into qr. Otherwise, the cells corresponding to each packet with number in [SRX,SRX+7] will be inserted into qn. In both cases, the timer will be reset again. We allow a retransmitted packet waiting in the q, being preempted to the normal queue q,, if there is no cells in q”. The preemptive operation is not allowed in q,,. The cells corresponding to the packets in q, and those in q,, will be sent via the virtual connection and underlying connection, respectively. In addition, there is a timer associated with qr. If the length of q, jumps from zero, then the timer is reset. When timeout occurs, every cells in q,- will be discarded. Therefore, if network keeps congested, it is highly possible that many receivers will not receive the corresponding packets and using underlying connection will be better than using virtual connection. We show the service model in the source in Figure 4.3. 81 l a: retransmission queue server of I plies. ' ' sender 3: ’2, 33' Virtual connection , (cells With CLP = l) \‘afj , . . , 3,». normal queue server of a: . t ‘ . . 8: . SRX and EI underlying connection (cells with CLP = 0) Figure 4.3: The service model in the source. parameter value parameter value PCR 149.76Mpbs MCR 0.1 Mpbs RIF 1 / 16 RDF 1/ 16 buffer size 3000 (cells) Nrm 32 (cells) packet size 23 (cells) LT 1000 (cells) ADTF 200ms HT 2500 (cells) Table 4.1: The important parameters for the simulation. When there are thirty- two cells in underlying connection being sent after the last RM cell, a new RM cell will be sent. We use ADTF (ACR Decrease Time Factor) as the sleep time of the timer in both source and sender. 4.2 Simulation We modify the NIST switch algorithm [39] in the NIST simulator 3.0 to support reliable ABR multicast. The important parameters for our simulation are listed in Table 4.1. Figure 4.4 shows the network configuration for the simulation. The pair mdl md2 m md4 O t lkm 1km 1km 1km ass BB1 332 ’ BB4 * * swl sw2 SW3 sw4 sw5 500km 500km , 10km 10km T 1 km 0 ms Figure 4.4: The network configuration. The multicast session has source ms and three destinations md1,md2,md3. In addition, for each broadband link BB j, there exists another ABR session 3 j sharing the same link with the multicast session. 82 “ms” to “mdl” will have the longest round trip time. For each link BB j , where j E {1, 2, 3, 4}, the capacity is 149.76 Mbps and a VBR traffic with mean 80 Mpbs and timegrain 2 milliseconds, as well as another ABR stream will flow through it. Therefore, the capacity of each will be almost fully utilized. We compare two difierent retransmission mechanisms. One uses qr, qn, virtual and underlying connections for retransmission, and the other only uses qn, i.e., always let the length of q. = 0 and multicasts the retransmission cells to all the receivers via underlying connection. When '7 = 8 and 16, the retransmission at one time consists of nine and seventeen packets, respectively. The error control protocol in the receiver implements the selective repeats and each lost packet detected in the receiver will be requested for retransmission. In addition, let completion number (CN) be the last SRX observed in the sender and progress number (PN) be the largest sequence number of the outstanding packet in the sender. When retransmission is needed and PN > CN + W, we always send the retransmission data via underlying connection. This is because if the round trip time is long, the cells in virtual connection tend to be discarded due to the congestion, and thus using underlying connection for retransmission is better. We show the simulation results when using the BCLR flow control. The size of each output buffer is 3000 cells. The parameters HT and LT are 2500 cells and 1000 cells, respectively. If the current queue length in an output port of a switch is not smaller than HT or the number of cells with CLP :1 is not smaller than LT, then CI in the BRM cell will be set to one. The switch algorithm and decision rules for ACR" and ACR, remain the same. When a cell with CLP = 1 arrives, 83 it will be allowed to enter into the buffer in the output port of a switch if there is some empty space and the number of cells with CLP :1 is less than LT. The cell with CLP : 0 will enter into the buffer if there is some empty space. The upper bound of cell loss ratio is set to be 20% and by the experience, the exact upper bound will be reduced to 1%. Figure 4.5, 4.6, 4.7, 4.8 show the results. We see that when W is small, the virtual connection is not effective. In addition, when W is large, the virtual connection will affect the loss ratio (the CLR for sw3 in Figure 4.8). This effect can be reduced by decreasing the value of HT. 84 0.8 - 0.7 *- 0.6 - 0.5 r' 0.4 r 0.3 - 0.2 r 0.1 *- cell loss ratio (%) 80 I I I I I I 70 '- 60 ” ACR in s1 -— ACR in $2 ..... 50 _ ACR in $3 ..... 40 - ACR in $4 ----------- ACR in ms --—-_ 30 - VACRinnm 1-2 ACR (Mbps) I 20 - ........ i .."u—o—t::::":F"""""""z'—'::Zil—w-"f'4” ‘C‘. 10 l I fit]. a i ,a 0 1 1 1' I11; 1 2 3 8000 . ,e . , , . 16 . . 7000 - ‘3” ‘f-' ' 14 L 6000 - ~ 5000 - ,. - 4000 — ,r' - 3000 — r' - 2000 ~ - 1000 - - . I.’ ." no. of retransmissions 0164:0300 I l l l l l _l 7 12345678 123456 time (sec) time (sec) Figure 4.5: The simulation results using BCLR flow control when 7 = 8 and Ii’zz 100. 85 cell loss ratio (%) ACR (Mbps) 8000 7000 6000 5000 4000 3000 2000 1 000 0.8 0-7 ’ sw2 — _ sw3 ----- 0.6 ’- sw4 .......... _l 0.5 - q 0.4 - 1 0.3 - '1‘ 0.2 - ,-'_ ........................ .' 0.1 I- ................... _ 0 A L l 1 l l 1 2 3 4 6 7 8 time (sec) 70 , , ‘ T I I 60 L ACR in s1 — E - ACR in $2 ----- 5 50 — ACR in $3 ----- ; q ACRins4 .......... l 40 - ACR in ms ----- 1 VACR in ms ----- I 5 30 - ; I 20 - ...... 5 5 .‘3::'.'.'.'.L2r::::1-‘5'3'33';C'.“:::1-_-.__;.r “6. +4."‘“‘ '- 10 ‘ . i it ....... L e . . :1 1 2 3 4 time (sec) I I I I I 10 I 2 CN — 9 i- -_ (D _ PN .. .5 8 _ _ .3 7 - 5 6 - I— '1' _1 g I" z 5 .- I- ’. -1 e _ _ *5 4 r o' 3 ~ C _ _ 2 P l l L J l 1 l 1 3 4 5 6 7 8 1 2 time (sec) Figure 4.6: The simulation results using BCLR flow control when 7 = W = 100. 86 16 and 1 I I 0.9 L A 0.8 *- 2", 0.7 - 3 0.6 - E w 0.5 — 3 0.4 ~ 3, 0.3 - 0.2 - 0.1 ~ 0 ‘ ' 1 2 3 70 I I l I I I 60 L ACR in s1 —- ACR in $2 ----- A 50 - ACR in $3 ----- a ACR in $4 --------- g 40 - ACR in ms ----- U, VACR in ms ----- a: 30 - 2 20 i- ........ .' '3: 24;: ’2': 11‘5““ 3:112? : :3 --- - i“ ' . 10 ‘ . ' 2 ‘- I. 'r 0 L l 1‘ 1 2 3 5 7 8 time (sec) 8000 I I I I I ' 14 I r I I I 7000 via unde ng --- <3 12 I viav ual ----- I 6000 -§ 10 r. [J 5000 '- ,1, ----- " g 8 r ,"I ' q 4000 5 i .2 6 - 1' 3000 9 1’ l 2000 2 4 I "I I l 1000 c 2 h i I 0 0 1 1 1 1 L 1 5 1 2 3 4 5 6 7 8 time (sec) time (sec) Figure 4.7: The simulation results using BCLR flow control when 7 = 16 and W = 500. 87 0.9 I I I I I 0.8 sw2 -— _ sw3 ----- 2“? 0.7 sw4 .......... d E 0.6 - ‘15} 0.5 ,1 1 8 0.4 .' .0. = 0.3 (1) o 0.2 0.1 O 1 l 2 100 r I I I I 90 2 1 - 80 g .j A 70 E ‘ U) . g 60 ACR in s1 — g g 50 ACR in s2 ----- . ; cc ACR in $3 ----- g i o 40 r ACRins4 ---------- a . 5 < 30 ACR in ms ----- ,5, i i '5‘ VACR in ms ----- l 1; 1 5 131 20 ........ 1 -; i ‘. - “I , ’ T 5., """" 4' ‘i‘fiJL-L‘.j_ '. 11‘5" _.. 10 1‘ I; 1- f 1 {:71 - 0 I l J '9; a! . 11:39:.1 2 3 4 5 time (see) 8000 I I I I 20 I 7000 - CN 18 ' PN -- ‘6’ 16 I- viavirtu I ----- _, 6000 L .9 i _ g 14 - ’1' 4 5000 - ,I'fl’ % 12 ._ ii. 1 4000 - g 10 - _ 3000 - ‘§ 8 L 1 '6 6 - ' 2000 g. 4 P 1000 I- 2 L O l l l l O l l l l L l 1 4 5 6 7 1 3 4 5 6 7 8 time (sec) time (sec) Figure 4.8: The simulation results using BCLR flow control when 7 = 16 and IV = 1000. 88 Chapter 5 Flow Control for ABR Dispersity Multicasting Dispersity routing was first defined by Maxemchuk [50,51]. In dispersity routing, a message is divided into a number of submessages, which are transmitted in parallel over m link-disjoint paths. Due to using link-disjoint paths, fault tolerance is then an inherent property. In addition, as the studies indicated, dispersity routing would essentially equalize the network load and increase the overall network utilization A survey can be found in [52]. Dispersity multicasting is an extension of dispersity routing to multicast (point-to-multipoint) communication. A multicast communication usually uses a subtree with the source as the root and connecting all the destinations to carry the messages. Thus in dispersity multicasting, we consider m arc-disjoint subtrees. We call each subtree as a connection. Consider the dispersity multicasting for the ABR service (A BR dispersity mul- 89 ticasting) with two arc-disjoint connections shown in Figure 5.1. Each of these two arc-disjoint connections is referred to as an underlying connection. As shown in Figure 5.1.(a), links ab, bd, be belong to one underlying connection and links ac, cd, ce belong to the other. In addition, the available bandwidth of each link is shown along with the link. Suppose the bottleneck flow control for multicast communication described above is applied to each underlying connection. Thus, sending rates 6 and 8 are granted for the underlying connections, respectively. For each link, the sending rate of the corresponding underlying connection will be consumed by the connection, as shown in Figure 5.1.(b), and let the resid- ual bandwidth be the result of substracting available bandwidth from the sending rate for the corresponding connection. Let the virtual network be the network induced by all the links in the underlying connections. Moreover, let the available bandwidth of each link in the virtual network be the residual bandwidth of that link. Another connection, i.e., a subtree, called virtual connection, can possibly be established on the virtual network. Figure 5.1.(c) shows a virtual connection using links ab, be, ac, cd with sending rate being one. Figure 5.1.(d) shows the final configuration. The concept of virtual connection can be extended form underlying connections and n virtual connections for multicast communication where m 2 2 and n 2 1. In this chapter, we study the ABR dispersity multicasting. A flow control algorithm is extended from the fourth algorithms in [15,16] to extract a virtual connection for the case in which we have two underlying connections. We also discuss the issues to make the algorithm viable on ATM networks. Simulation 90 (a) on ma] network (b) sending rates (c) virtual network (d) final configuration Wit available . . . . . bandwidths tor underlying connections and Virtual connection Figure 5.1: The concept of virtual connection. studies show that in general, our flow control algorithm enhances the throughput of dispersity multicasting. 5.1 Flow Control Algorithm In ATM networks, the management information is carried by resource manage- ment (RM) cells [13]. Consider the ABR multicasting with a single connection T( V, A, C). As a simplified version of the fourth algorithms in [15,16], to obtain the connection bandwidth, the source generates a forward RM (FRM) cell with the field emplicit rate (ER) being peak cell rate (PCR). Upon receiving an FRM cell, the switch multicasts the cell to all its branches. Then an operation A1(T), defined in Figure 5.2, is performed. Upon receiving a backward RM (BRM) cell, the source adjusts its allowed cell rate (ACR) according to ER in the cell. Consider the ABR dispersity multicasting with two underlying connections and one virtual connection. Each underlying connection has its own virtual channel identifier (VCI). Cells in the virtual connection use the V01 assigned to the under- lying connection where these cells will traverse. Thus, each path from the source to 91 For every destination: Upon receiving an FRM cell, return the cell as BRM cell to source. For every switch v: Upon receiving a BRM cell with ER from branch e, MER <— min{MER,ER}; ae (— 1; if for each branch e’, ae: = 1, then pass the BRM cell to source with ER(— min{MER,min{C(e’) : e’ is a branch of v}}; MERé— PCR; for each branch e’, ae: (— 0; else discard the BRM cell. Figure 5.2: The defintion of A1(T), where T is the rooted tree for backward RM (BRM) cells traversing backwards, MER, being PCR initially, is a register in the switch and ae, being zero initially, is a binary variable associated with the branch 6. [ field representation CCR ACR parameter of the underlying connection ER the path bandwidth ER, relating to the total bandwidth of the underlying and virtual connections 872,, relating to bandwidth of underlying connection Table 5.1: The representation of fields in RM cells. a destination in the virtual connection must be in the same underlying connection. The FRM and BRM cells carry (CCR,ER) and 111i 2 (£72,,6’Re), respectively.1 In the followings, the flow control for the virtual connection is only driven by the BRM cell which is turned around by the destination. That is, the BN field of the BRM cell should be zero. Table 5.1 shows the representation of each field. The idea is letting the destination choose the path in the virtual connection and the switch treat the underlying connections independently. For each underlying 1In next section, we will discuss the issue when OCR and ER in the BRM cell are used for £72, and 57%,, respectively. 92 connection Ti, FRM cells are constantly sent from the source with OCR and ER being ACR for T,- and PCR, respectively, via T,- to all destinations. Upon receiving an FRM cell via T,, the switch multicasts the cell to all its branches in T,. Before delivering the copy of the FRM cell to the branch e, the switch updates ER by min{ER,C(e)} in the copy of the cell. For each i, the destination maintains y: = (6‘, ER'), where e‘ and ERi denote the path bandwidths from the source via T,- to the destination in the virtual net- work and original network, respectively. Upon receiving an FRM cell via T,, the destination updates y: by the rule: (2,312) +- ((ER-CCR)+, ER), (5.1) where (-)+ E max{O, -}. An operation A2(T,-) defined in Figure 5.3, which is ex- tended from A1, is then performed. The descriptions of terms used in Figure 5.3 are as follows: T,- is the rooted tree for BRM cells traversing backwards. N is a number which is larger than PCR. The indicator 1,.) = 1 if (-) is true or 1,.) = 0 otherwise. ME}; = (M8R,, M873“) being (N, PCR) initially, is a register for T,- in the switch. The register ae and be are binary variables associated with the branch 6 with initial value zeros, respectively. Upon receiving a BRM cell from T,, the decision of the ACR for T,- (ACR‘) follows the source behavior of an ordinary ABR service by replacing ER with 872,. In this section, we let ACR“ <— £72,. Then the ACR for the virtual connection 93 For every destination: Upon updating y‘ by Equation 5.1, if i = 1, then return a BRM cell with _E_R_ <— [0, 00). In this section, we use the function gb(a, b) = 1), Va, 0 2 0. A file to be transferred is dynamically configured to three groups which will be sent via two underlying connections and one virtual connection, respectively, and call data cells sent via the latter one virtual cells. Upon receiving a data cell via T ,, the switch performs the filtration by multicasting the cell to every branch e in T,- with be 2 1, if it is a virtual cell; otherwise, the switch multicasts the cell to all its branches in T,. 94 0 ° ACR]: 0 ACR]: 6 <6,6> <9,9> <8.8> (a) original network (b) values 0f Z} a ACRI=6 a a ACR’zo ACR2= 8 ACR2= 8 3 I0 ACRv = I <8,6>8 IOACRv =1 6 c I c<9,3> IO 6] 9 W3 6 d. d e <0,6><1,9> <2.8> <0,8> (d) values of yi (e) 1:313 in BRM cells (1) final configuration Figure 5.4: The example illustrating the algorithm. 5. 1 . 1 Example Figure 5.4 shows an example. In part (a), let T, and T2 be the rooted trees induced by the arc sets {ab, bd, be} and {ac, cd, ce}, respectively. In part (b), FRM cells have arrived at each destination via T1 and T2, and Vi, y: in each destination has been updated by Equation 5.1. In part (c), paths ab, be and ac, cd are chosen in the virtual connection and Vi,A2(T,-) is performed. By Equation 5.2, ACR, = 1. In part (d), another FRM cells have arrived at each destination via T1 and T2, and Vi, a new _y_i in each destination has been obtained by Equation 5.1. In part (e), again, ab, be and ac, cd are chosen as paths in the virtual connection and Vi, A2 (11",) is performed. By Equation 5.2, ACR, = 1. Part (f) shows the final configuration. 95 5.1.2 Correctness of Algorithm A sequence of times Smn 2 0 is defined by So = 0 and when n 2 1, 5,, is the smallest time at which Vi, the first FRM cell sent after S,,_1, from the source via T,, has arrived at all the destinations and the corresponding operation A2(T,-) has been performed completely. Theorem 7 Suppose the available bandwidth of each link is static, and the durations for source and destination operations can be ignored. Then we have 1) at 5,, the bandwidth of underlying connections will be obtained; 2) the bandwidth of the virtual connection will be obtained at S3; and 3) after S3, all bandwidths obtained will not be changed. [:1 Proof: The statement 1 is true since the operation for obtain- ing bandwidths for each underlying connections is the reduction operation R(T(V,A,C), ER,“ M ER“, PCR) for each underlying connection T where PCR is the constant function with value PCR. Note that Ve E A(T), C(e) is the avail- able bandwidth along e in the original network. The statement 2 can be easily verified since after S 1, the bandwidths for both underlying connections are known in the source, and before 52, the information of CCR3 will be obtained in the destination. Then correct ER,1 and ER? in the destination can be obtained by (5.1). Suppose the correct bandwidth for the virtual connection is 13 _>_ 0. Af- ter SQ, there exists an underlying connection T, by the reduction operation R(T(V,A,C),ER,,MER,,I‘) where Ve E A(T),C(e) = L, and 1" stands for the 96 results obtained by (5.1), [3 + ACR“ will be obtained where ACE, is the ACR for the underlying connection. The result for the other connection should be [3’ + ACR], where B’ 2 fl and ACR], is the ACR for the underlying connection. Therefore, by the source operation specified in Equation 5.2, the correct band- width will be ACR, in the source. This operation will be completed at S3. The statement 4 can be easily checked. D 5.2 Implementation Issues To support our algorithm described in the last section on the ATM networks, the switch must distinguish the data cell to be virtual cell or not, so that the filtration can only be applied to virtual cells. Here we propose that the CLP field in the data cell for the ABR connection will be used to provide the filtration. That is, in our case, virtual cells are with CLP = 1. Therefore, the switch can filter out virtual cells if needed. For the BRM cell, CCR and ER could be used for £72, and SR,“ respectively. However, CCR in the BRM cell is not allowed to change by the destination or switch in the current ATM traffic management specification [13]. It is noteworthy that if ABR multipoint-to—point connections are also supported, fairness cannot be achieved if CCR in the BRM cell is used to calculate the available bandwdith [53]. Thus, we expect in the future a more flexible usage of CCR in the BRM cell will be defined. 97 The frequency of RM cells has an impact on the cell loss ratio, bandwidth utilization, and fairness. In our current approach, the frequency of the RM cells is only decided by the parameters, such as the number of cells, for the underlying connection. Thus the frequency of the RM cells is consistent for the underlying connection. 5.3 Simulation We modify the NIST switch algorithm [39] in the NIST simulator 3.0 to support ABR dispersity multicasting. In addition, upon receiving a BRM cell, the switch does MCI <— MCI OR CI and MNI <— MNI OR NI, where CI (congestion indica- tion bit) and NI (no increase bit) are the fields in BRM cell, and MCI and MNI, initially zeros, are the registers in the switch. If the BRM cell will be passed to the source, then let CI ’and NI be MCI and MNI, respectively, and reset MCI and MNI to be zeros. Figure 5.5 shows the network configuration for the first simulation. The distance of 833' for j E {1,2,3,4} is 500 km and the distance of any other link is 10 km. Each link is associated with 155 Mbps bandwidth. The source of the ABR dispersity multicasting, “ms” ”, has two destination ends “mdl” and “md2”. The first underlying connection uses links BB2 and BB3 and the other one uses links 831 and BB4. For each i, The decision of ACR" fol- lows a normal ABR source behavior and the decision of ACR, uses the function ¢(a,b) = min{a+RIFxPCR,b}I(a ei + r. We expect that there is no path swap for “mdl” since the virtual connection will always use link BB4. We check if the cell is consequently received in “md2”. If not, a jump is noted. As shown in Table 5.2, as r is increased, the number of path swaps and the number of jumps are decreased. Note that we can also decrease the number of jumps by returning a BRM cell with 872, = 0 via the currently chosen path in the destination when a path swap is needed, and then A2 is performed upon receiving next set of FRM cells. As a result, ACR, = 0 and then ACR, will be slowly increased. Our future work will study the action and 101 mdl md2 052 Figure 5.10: The second network configuration. scheme received virtual jumps path cells cells swaps w/o VC 507340 - - - T = 0 569310 83562 318 613 7- :- 2Mbps 563877 76208 291 451 T = 4Mbps 565949 76252 244 419 T = 8Mbps 572198 82861 166 324 Table 5.2: The results in “md2” in the second simulation where the simulation time is 3 seconds. condition for path swapping in a more rigorous way. Figure 5.11 shows the network configuration for our third simulation. In this simulation, we add another VBR traffic to link BB4. We expect both “mdl” and “md2” will have path swaps for the virtual connection. The simulation results for r = 8 Mbps listed in Table 5.3 show that we still can have more than 8% performance improvement by using virtual connection. Hence, though for each destination, the expected available bandwidths of all paths via one of the under- 102 mdl md2 Figure 5.11: The third network configuration. T = 8 Mbps w/o VC mdl md2 mdl md2 cells received 518201 513991 473139 473028 virtual cells 62166 58275 - - jumps 155 181 - - path swaps 230 280 - - Table 5.3: The results in the third simulation where simulation time is 3 seconds. lying connections are the same (75Mbps in this case), the virtual connection can still benefit the dispersity multicasting. 103 Chapter 6 Conclusion In Chapter 3, we focus on the max-min fairness convergence when using ER—based ABR flow control. In designing a flow control mechanism, the max-min fairness convergence is a critical constraint. Up to date, it is an open issue to develop an efficient switch algorithm conforming to the standard defined by the ATM Fo- rum to guarantee the convergence of max-min fairness with the fairness criterion ” maximum of MCR and equal share.” We give some sufficient conditions for max- min fairness convergence. The tractability of this suficient conditions are verified by giving three switch algorithms, one of which has finite-time max-min fairness convergence with computation complexity 0(N). One of the future work will be extending our sufficient conditions for the weighted fairness criteria. Another fu- ture work is to prove or disprove that there exists an algorithm with computation complexity 0(1) which has finite-time max-min fairness convergence. We give an algorithm in Figure 3.5 to bound CLR for cells with CLP : 0 under the Gaussianprocess assumption. The convergence is proved and a buffer 104 management scheme for BCLR flow control with two loss priorities is proposed. Our simulation shows that our algorithm bounds CLR successfully, and has good transient response and high link utilization. From our simulation, the ratio of our given upper bound for CLR and actual CLR is around twenty. Therefore, there is some rich information in the traffic we have not explored yet. It will be an interesting topic for our future study. Another important work is to study the loss probability of a cell if its preceding cell is lost. Thus, the QoS will be improved if we can bound this conditional loss probability. In addition, this work will help us to develop an algorithm to bound packet loss ratio. In Chapter 5, we extend the flow control of ABR multicast for error control. By using the virtual connection, a dynamically configured partial connection by error control algorithm, we can reduce the retransmission trafic. In addition, the throughput of the multicast communication can be enhanced. The error control algorithm can be improved under the criterion of reducing the feedback delay. That is, though the receiver with longer round trip time has not informed the switch about its most recent status, the switch can still advise the sender to retransmit the packet according to the current information. Therefore, the receiver with shorter round trip time will recover its lost packets first and if the receiver with longer round trip time requests the packets with the same numbers, the sender will retransmit them again. The prospect of this approach depends on the insight that the less the number of destinations is, the more the available bandwidth tends to be granted. We will study the improved error control algorithm 105 as the future work. For the fault tolerance, we propose a flow control algorithm for ABR dispersity multicasting with two underlying connections and one virtual connection. The simulation results show that our flow control algorithm can enhance the throughput of ABR dispersity multicasting under a variety of conditions. The current flow control algorithm can be improved in many respects, e.g., the generalization of the concept of virtual connection to virtual source/virtual destination (VS / VD) control [13], the prediction of the path bandwidth, and the conditions for path swapping. We will examine the improved algorithm by the criteria of fairness, scalability, stability, and transient response. 106 Bibliography [1] B. Waxman, “Performance evaluation of multipoint routing algorithm,” in IEEE INFOCOM ’93, (San Francisco), pp. 980—986, 1993. [2] P. Hwang and Y. Tanaka, “Multicast routing based on predicted traffic statis- tics," IEICE Trans. Commun, vol. E77-B, Oct. 1994. [3] M. J. Donahoo and E. W. Zegura, “Core migration for dynamic multicast routing,” in ICCCN’96, Sept. 1996. [4] R.-H. Hwang, “Adaptive multicast routing in single rate loss networks,” in IEEE INFOCOM ’95, (Boston), pp. 571-578, 1995. [5] S.-B. Kim, “An optimal VP-based multicast routing in ATM networks,” in IEEE INFOCOM ’96, (San Francisco), pp. 1302-1309, 1996. [6] M. Ammar, S. Cheung, and C. Scoglio, “Routing multipoint connections using virtual paths in an ATM network,” in IEEE INFOCOM ’93, (San Francisco), pp. 98—105, 1993. [7] B. Waxman, “Routing of multipoint connection,” IEEE Journal on Set. Ar- eas in Comm., vol. 9, pp. 1617—1622, Dec. 1988. [8] M. Grossglauser and K. Ramakrishnan, “SEAM: Scalable and efficient ATM multicast,” in IEEE INFOCOM’97, (Kobe, Japan), 1997. [9] M. Veeraraghavan, T. L. Porta, and W. Lai, “An alternative approach to call/ connection control in broadband switching systems,” IEEE Comm. Mag., vol. 33, pp. 90—96, Nov. 1995. [10] K. Liu, D. Petr, and V. Frost, “Desing and analysis of a bandwidth man- agement framework for ATM-based Broadband ISDN,” IEEE Comm. M ag., vol. 35, May 1997. [11] G. Ash and et al., “Special issues in dynamic routing in telecommunications networks,” IEEE Comm. Mag., vol. 33, July 1995. [12] B. Vandalore and et. al., “QoS and multipoint support for multimedia appli- cations over the ATM ABR service,” IEEE Comm. Mag., vol. 37, pp. 53—57, Jan. 1999. 107 [13] The ATM Forum, “The ATM Forum tramc management specification version 4.0,” Apr. 1996. [14] J. Jafie, “Bottleneck flow control,” IEEE Trans. Comm., vol. 29, pp. 954- 962, July 1981. [15] S. Fahmy and et al., “Feedback consolidation algorithms for ABR point—to- multipoint connections in ATM networks,” in INFOCOM ’98, pp. 1104-1113, 1998. [16] W. Ren, K.-Y. Siu, and H. Suzuki, “On the performance of congestion control algorithms for multicast ABR service in ATM,” in IEEE ATM ’96 Workshop, Aug. 1996. [17] K.-Y. Sin and H.-Y. Tzeng, “Congestion control for multicast service in ATM networks,” in IEEE GLOBECOM ’95, pp. 310-314, 1995. [18] J. Choe and N. B. Shrofi, “Supremum distribution of Gaussian processes and queueing analysis including long-range dependence and self-similarity (a short version of this paper is published in IN FOCOM’99),” submitted to Stochastic Model, 1999. [19] W. Willinger, V. Paxson, and M. S. Taqqu, “Self-similarity and heavy tails: Structural modeling of network traffic,” in A Practical Guide to Heavy Tails (R. J. Adler, R. E. Feldman, and M. S. Taqqu, eds.), pp. 27-53, Birkhauser, 1998. [20] M. W. Garrett and W. Willinger, “Analysis, modeling and generation of self- similar VBR video traffic,” in ACM SigComm, Sept. 1994. [21] W. Willinger, M. S. Taqqu, and A. Erramilli, “A bibliographical guide to self- similar traffic and performance modeling for modern high-speed networks,” in Stochastic Networks: Theory and Applications (F. Kelley, S. Zachary, and I. Ziedins, eds.), 1996. [22] P. Brockwell and R. Davis, Time Series: Theory and Method. Springer- Verlag, 1991. [23] P. W. Glynn and W. Whitt, “Logarithmic asymptotics for steady-state tail probabilities in a single-server queue,” Applied Probability, pp. 131-156, 1994. [24] P. R. Jelenkovic, “Long-tailed loss rates in a single server queue,” in INFO- COM ’98, pp. 1462-1469, 1998. [25] N. Likhanov and B. Tsybakov, “Analysis of an ATM buffer with self-similar (”fractal”) input traffic,” in INFOCOM’95, pp. 985-993, 1995. [26] M. Taqqu, W. Willinger, and R. Sherman, “Proof of fundamental result in self-similar traffic modeling,” Computer Communication Review, pp. 5-23, 1997. 108 [27] S. Ross, Stochastic processes. New York: John Wiley 8!. Son, 1983. [28] S. Abraham and A. Kumar, “A stochastic approximation approach for max- min fair adaptive rate control of ABR sessions with MCRs,” in INFOCOM ’98, pp. 1358—1365, 1998. [29] Y. Hou, H.-Y. Tzeng, and S. Panwar, “A generalized max-min rate alloca- tion policy and its distributed implementation using the ABR flow control mechanism,” in INFOCOM ’98, pp. 1366-1375, 1998. [30] T. Lee and G. Veciana, “A decentralized framework to acheive max-min fair bandwidth allocation for ATM networks,” in Globecom’98, 1998. [31] W. Tasi and Y. Kim, “Re-examing maxmin protocols: A funcamental study on convergence, complexity, variations, and performance,” in INFOCOM ’99, pp. 811-818, 1999. [32] D. Towsley, J. Kurose, and S. Pingali, “A comparison of sender-initiated and receiver-initiated reliable multicast protocols,” IEEE Journal on Sel. Areas in Comm., vol. 15, no. 3, pp. 398-406, 1997. [33] J. Lin and S. Paul, “RMTP: A reliable multicast transport protocol,” in IN- FOCOM’96, pp. 1414-1424, Mar. 1996. [34] S. Singhal, H. Holbrook, and D. Cheriton, “Log-based receiver-reliable multi- cast for interactive simulation,” in ACM SIGCOMM’95, pp. 328—341, Oct. 1995. [35] S. Floyd and et al., “A reliable multicast framework for light-weight sessions and application-level framing,” in ACM SIGCOMM ’95, pp. 342—365, Oct. 1995. [36] Y. Zhao, S. Li, and S. Sigarto, “A linear dynamic model for design of stable explicit-rate ABR control schemes,” in INFOCOM’97, Apr. 1997. [37] C. Rohrs and R. Berry, “A linear control approach to explicit rate feedback in ATM networks,” in INFOCOM ’97, Apr. 1997. [38] C. Fulton, S.-Q. Li, and C. Lim, “UT: ABR feedback control with tracking,” in INFOCOM ’97, 1997. [39] N. Golmie, Y. Chang, and D. Su, “NIST ER switch mechanism (an example),” ATM Forum/95-0695, June 1995. [40] S. Kalyanaraman and et. al., “The ERICA switch algorithm for ABR traffic management in ATM networks,” Nov. 1997. [41] M. Bitter, “Network bufier requirement of the rate-based control mechanism for ABR services,” in IEEE INFOCOM’96, pp. 1090-1097, 1996. 109 [42] S. Abraham and A. Kumar, “Max-min fair rate control of ABR connections with nonzero MCRs,” in Globecom’97, pp. 498-502, 1997. [43] A. Charny, D. Clark, and R. Jain, “Congestion control with explicit rate indication,” in ICC ’95, pp. 1954-1963, 1995. [44] W.-K. Liao, A. H. Esfahanian, L. M. Ni, and R. LePage, “Bounded-cell—loss— ratio flow control,” Technical Report, 1999. [45] C.-S. Chang, “On deteriministic tramc regulation and service guarantees: A systematic approach by filtering,” IEEE Trans. Information Theory, pp. 1097—1110, 1998. [46] E. Harman, “The convergence of some recursions,” Annals of Statistics, pp. 1258—1270, 1976. [47] Y. Freund and R. E. Schapire, “A decision-theoretic generalization of on-line learning and an application to boosting,” Journal of Computer and System Sciences, vol. 55, no. 1, pp. 119-139, 1997. [48] W.-K. Liao, A. H. Esfahanian, and L. M. Ni, “Reliable ABR multicast,” Tech- nical Report, 1999. [49] W.-K. Liao, A. H. Esfahanian, and L. M. Ni, “Flow control for dispersity multicast,” Technical Report, 1999. [50] N. Maxemchuk, “Dispersity routing,” in ICC’75, pp. 41—10—41-13, June 1975. [51] N. Maxemchuk, “Dispersity routing on ATM networks,” in INFOCOM ’93, pp. 347—357, 1993. [52] E. Gustafsson and G. Karlsson, “A Literature Survey on Trafic Dispersion,” IEEE Network, pp. 28-36, March/April 1997. [53] S.Fa.hmy and et al., “A switch algorithm for ABR multipoint-to-point connec- tions,” ATM Forum/97-1085, Dec. 1997. 110