is the sum of a l l backlogged F E C s ' weights at the output l ink, and r is the output l ink capacity. Admis s ion control po l icy need to be applied to insure that the sum of rates of a l l flows belonging to Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 93 a certain F E C does not exceed its reserved bandwid th share. If it exceeds its bandwid th share, only the misbehaving F E C w i l l be affected due to the isolation property of the F P Q algorithms. 6.3.3 Delay guarantees In our architecture, the tota l delay that a packet, belonging to F E C i, encounters in its pa th from ingress to egress is composed of six components: burst assembly delay (dati) i n ingress O B S node, queueing delay i n ingress node before being processed by the reservation manager (dqf), burst offset t ime (T0ii), packet transmission delay (dt,i), l ight propagation delay (d;^) and the queuing delay at the output of the egress O B S after the burst de-assembly process (de^). Thus the to ta l delay (Di) for packets belonging to F E C i is A = da*l. (6.4) Note that the propagation delay di^ depends only on the to ta l l ight pa th length, while T0ti is proport ional to the number of O B S core nodes on that path . Therefore, d^i and TQ:i are uncontrollable quantities i n our architecture. In the following, we derive expressions for each of the delay components. The packet arr ival process to F E C i is assumed to be Poisson process w i t h mean value Aj packets/sec, and the packet size is assumed to have an average length of L bits . T h e average burst assembly delay can then be calculated as follows: Chapter 6. Quantitative QoS Guarantees in Labeled OBS Networks 94 d, 1 N i 1 k=i (6.5) (6.6) (6.7) where dk is the assembly delay for packet number k i n the assembly queue, and N is the average number of packets i n a data burst belonging to F E C i. T h e variable N can have one of two possible values depending on the arr ival rate Aj, the F E C ' s m a x i m u m burst size (BmaXii) and the F E C ' s burst assembly t imeout (Tmaxi). In order to calculate the value of Ni we need to consider two possibilit ies: one is that TmaX:i is reached first, and the other is that B m a X t i is reached first, ff the t imeout is reached first, then Ni = \\Tmax^. ff the m a x i m u m burst size is reached first, then N = [ m £ x - ' j . Thus , Equa t ion 6.5 can be rewrit ten as: ft is clear from Equa t ion 6.8 that da Nitdb *

* = interval corresponding to e; c <— c \\ t>; e n d i f (e is a right point) and (eprev is a right point) t h e n Let v = interval corresponding to e; c <— c \\ v; e n d e n d Repor t C ; A l g o r i t h m A . l : M A X I M A L - C L I Q U E S a lgor i thm 160 Append ix B Offline Opt imal Scheduling A lgo r i t hm Authors i n [1] gave an a lgor i thm for finding an op t ima l feasible schedule of intervals while max imiz ing the to ta l weight of the selected intervals. T h e scheduling problem is formulated as instance of minimum-cost flow problem [43]. 1. Represent the problem i n the form of an interval graph. 2. Identify al l m a x i m a l cliques qi,... ,qr of the interval graph. Order the m a x i m a l cliques according to t ime. 3. Const ruct a directed graph G as follows: (a) Create nodes VQ,. .. ,vr and arcs (i>j, t>i_i) for i = 1 , . . . , r . T h e costs on these arcs equal 0 and their capacities are infinite (each arc represents a clique). (b) For each interval , i f f is i n cliques qj,..., qj+i, add an arc (VJ_I,VJ+1) of cost Wi and capacity f. (c) For each clique j that is not of m a x i m u m size, we add an arc (VJ-I,VJ) of cost Appendix B. Offline Optimal Scheduling Algorithm 161 0 and capacity equal to (maximum-clique-size - size-of-g.,-). (d) Consider node v0 to be a source S, and vT to be a sink T. 4. We require a flow from 5 to T of (maximum-clique-size - k), where k is the number of available wavelengths. A n op t imal solut ion to this m i n i m u m cost flow problem is i n fact an op t imal solution to our original problem. If an arc corresponding to interval f has a non-zero flow on it in the min-cost flow solution, then we do not process this interval . Thus , we do not process a subset of intervals such that a l l remaining cliques are of size k or less. Th i s subset is of smallest possible value since it corresponds to a min-cost flow solution. To find the min-cost flow we used the a lgor i thm described i n [11]. A n example for this construct ion is shown i n F igure B . l . The m a x i m a l cliques i n the graph can be found using the a lgor i thm described i n A p p e n d i x A i n O ( n l o g n ) , where n is the number of intervals. T h e complexi ty of the m i n i m u m cost flow algori thm described i n [11] is equal to (required flow x complexi ty of the shortest pa th algori thm). In our case the required flow is 0(n), and the complexi ty of the shortest path a lgori thm is O ( n l o g n ) . Therefore, the to ta l complexi ty is 0 ( n 2 l o g n ) . Appendix B. Offline Optimal Scheduling Algorithm 162 | W ; = ; C \\v=h 1 ! i 1 1 I ! W = 1 1 !• . ! J j 1—™ 1 I 11 w =i d\\ w — e • i i a. The intervals. w = cost w= b, p = 1 w=0, p =1 b. The corresponding graph. Figure B . l : E x a m p l e for m i n i m u m cost flow construct ion "@en ;
edm:hasType "Thesis/Dissertation"@en ;
vivo:dateIssued "2005-11"@en ;
edm:isShownAt "10.14288/1.0099850"@en ;
dcterms:language "eng"@en ;
ns0:degreeDiscipline "Electrical and Computer Engineering"@en ;
edm:provider "Vancouver : University of British Columbia Library"@en ;
dcterms:publisher "University of British Columbia"@en ;
dcterms:rights "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en ;
ns0:scholarLevel "Graduate"@en ;
dcterms:title "Analysis and design of optical burst switching networks"@en ;
dcterms:type "Text"@en ;
ns0:identifierURI "http://hdl.handle.net/2429/17181"@en .
*