Dynamic Resource Allocation Algorithm for Optimized Bandwidth Utilization 2001 2
Dynamic Resource Allocation Algorithm for Optimized Bandwidth Utilization 2001 2
2001 2
i,,,,
Abstract Wireless network systems providing convenience with people have serious problems with limited frequency resources These problems are increased in next-generation wireless communication system that provides multimedia services such as on-demand video, visual telephone, and internet connection going out of voice-oriented communication pattern So it is essential to improve utility of wireless resources for supporting multimedia services that satisfy more and more people with limited frequency resources In this study, we propose two methodologies to improve utility of wireless resources that can be applied for next-generation wireless communication services The first methodology is algorithm calculating available bandwidth for dynamic channel allocation technique using exponential weighted moving average formula The second methodology queuing algorithm and controlling call accept rate using statistical prediction technique The proposed resource allocation algorithm enables dynamic allocation of wireless resources It can improve bandwidth utility with acceptance of more call enactment request enabling to allocate more flexible resource allocation than fixed resource allocation method In addition, it is applied for next-generation wireless communication network existing various traffic through processing and classifying call enactment request with traffic unit ii
i Abstract ii 1 1 2 3 21 IMT -20003 22 5 23 6 231 7 232 8 233 10 234 Erlang B 11 3 13 31 13 311 14 312 17 32 18 321 19 322 21 33 24 4 27 41 27 411 27 412 29 413 30 5 33 34 iii
1,,, IMT-2000(I nternational Mobile Telecommunication 2000) IMT-2000 (conversational/real-time services), (interactive services), (streaming services),,, 1
,, 2 IMT 2000 3, 4 5 2
2, Erlang 21 IMT-2000 ITU(International Telecommunication Union) 1985 (, WL L ) FPLMTS(Future Public Land Mobile Telecommunication Serv ice, ), 1992 WRC(World Radio Conference )-92 (roaming) 18852025MHz/21102200MHz 1997 WRC-97 FPLMTS 2 000 2000MHz(2GHz) IMT(International Mobile Telecommunication)-2000 1 2, 3 IM T-2000 3
, Uu Gp Intra-PLMN Backbone network (IP based) Node B GPRS INFRASTRUCTURE Serving GPRS Gn Support Node(SGSN) Border Gateway(BG) RNC Iu Iu Intra-PLMN Backbone network (IP based) Gn Serving GPRS Support Node(SGSN) MSC Gs Gr Gs Gd GiIP Data Network (Internet) PSTN SS7 Network Gr MAP-F HLR/AuC SMS-GMSC Router EIR Corporate 2 Corporate 1 Local area network Router Local area network [ 2-1] IMT-2000 IMT-2000,,, [ 00] IMT-2000 [ 2-1], 4
,, [TTAE00] [ 2-1] IMT-2000 (Speech) 16kbps < 14kbps (Simple Messagin g) < 64kbps, G3, G4 (Switched Data),, (Medium Multimedia) - 2000kbps, 128kbps (High Multimedia) - 384kbps, 64kbps,, (High Interactive Multim edia) 128kbps, 384kbps 22 [ 99] ( 5
) ( ) [ETRI96,Wro97] B-ISDN(Broadband Integrated Services Digital Network) [Cho98,Van98] QoS(Quality of Service) QoS, [Luc98],,,, 23 2, 6
, (Fixed Chann el Allocation), (Dynamic Channel Allocation), (Hybrid Channel Allo cation), 231 1971 Cox-Rendink, (DR), [Woo95] (DR) Call-by-Call Call-by-Call 7
Channel Borrowing Call-by-Call, Call Blocking Rate DCA FCA Call Number [ 2-2],, 232 8
(CIR : Carrier to Interference Ratio), Hal pern (Re-Use Partitioning) (Dr),, 7 (Dr=46R) 3 (Dr=3R) 3:1 5 7 13 R ( :Dr), (CIR), [Err97] ARP (Autonomous Reuse Partition) IMT-2000,, 9
233 ( ) [ 99] DCA(Distributed Call Admission Control),, DCA PQoS( ) RA-DCA, RA(Re strictedaccess) Call Setup Yes RealTime No Yes TrafficSize <BW 1 UB Yes No HandOff No No CallSetup RequirementSaitif y Yes Yes HandOff No HandOff No SUCCESS FAIL SUCCESS FAIL 10
[ 2-3] RA-DCA Erlang B 234 Erlang B Erlang (Erlang's B loss formula) pure loss λ Poission process µ λ 1 / (sec), 1/ µ Erlang k, k=0,1,,m [ 2-1] λ, λk = 0, µ k = kµ, k < m k m k = m, m = S1,, S n S : Service type [ 2-1] Birth-Death process steady-state probability Pk [ 2-2], [ 2-2] [ 2-3] P k = P λ k 1 i 0 i= 0 µ i + 1, k = 01,,2, [ 2-2] P k = P k 1 0 i= 0 λ, ( i + 1) µ k m [ 2-3] 11
[ 2-1] [ 2-2] [ 2-3] [ 2-4] k λ 1 P0, Pk = µ k! 0, k > m 1 P0 = k m λ 1 k= 0 µ k! k m [ 2-4] Erlang m, P = m BUSY k, E rlang (Call Blocking Ratio) [ 2-5] P m λ 1 k λ 1 µ m! = ( m, λ / µ ) = P0 = [ 2-5] k m µ k! k= m λ 1 k= 0 µ k! m Erlang 0 P k = m P = m k 12
3,,, 31,, 30%, 13
,, 311 ( ) ABW = T A where ABW : Available BandWidth T : Total BandWidth ( constant ) A : Sum of current allocated BandWidth ABW = T ( 1 W ) A where ABW : Available BandWidth T : Total BandWidth ( constant ) A : Sum of current allocated BandWidth W : Weight (Reserve Rate) 14
,,,, t where t HOBW dt 1 t t 1 t t 1 2 HOBW HOBW dt dt HOBW : HandOff BandWidth t : current time t-n : past of n unit time t-1, (EWMA: Exponential Weighted Moving Average) t-1 15
02~03, t 07~08 t+1 W D = Ew t 1 t 2 + (1 Ew) HOBW dt t t 1 t 1 t 2 HOBW dt HOBW dt t t 1 t 2 t 3 HOBW HOBW dt t 1 t 2 HOBW dt dt W S t t 1 MT dt t t t 2 3 1 = Ew + ( 1 Ew) 1 t 2 t 2 MT dt MT dt t t MT dt t 1 t t 1 2 MT dt MT dt where W S : change rate of number of mobile station in overlap zone MT : number of Mobile Terminal E w : Exponential Weight ABW = T ( 1 W ) A W = 0 WHEN Handoff ELSE W = + WS WD 16
312 i ii (incoming handoff) iii (outgoing handoff) iv, EWMA T A t t 1 A dt t t t t t 2 3 1 = Ew + (1 Ew) t 1 t 2 2 A dt A dt A dt t 1 t t 1 2 A dt A dt where T A : Tendency of Allocation A : Sum of allocated BandWidth at that time [ 1] 17
[ 1] Method GetAvailableBandWidth t : current time unit station_id : deltat : time interval ratio : weight HOBW Begin Method TB := GetTotalBandWidth(station_id); // total bandwidth HOBW := GetHandOffBandWidth(t, station_id); HOBW1 := GetHandOffBandWidth(t - deltat, station_id); HOBW2 := GetHandOffBandWidth(t - deltat * 2, station_id); numofservice := GetServiceCount(station_id); A := GetAllocatedBandWidth(station_id); // get sum of bandwidth currently allocated WD := (1 - ratio) * (HOBW1 - HOBW2) / HOBW1 + ratio * (HOBW - HOBW1) / HOBW; // calculate total weight of dynamic allocated services currently used WS := GetWeightFrom(NMS, station_id); // get weight of long-term statistical analysis result ABW := TB * (1 - (WS + WD)) - A; // calculate available bandwidth Return ABW; End Method; 32,, 18
321 (queue), (Queuing), QoS (Differentiated Service) (Class Based Queuing) [She97] FIFO(First In First Out) (Drop Tail), (Priority), (starvation), 19
,,,,,,, 6,,,, [Rapa99a] [ 3-1] Input Queue Call Type Based Queue Streaming Video Phone Transaction Call Classification [ 3-1] 20
[ 3-1] F IFO,, 33 CallType FIFO (weighted round r obin) Erlang 322 (subscriber) - 21
-, -, (NMS: Network Management System) - - - (, ) [ 2] Method CallAdmissionControl 22
required_bw : Bandwidth alloc_bw : Bandwidth ABW : Bandwidth alloc_tendency : call_id : ID t : Begin Method ABW := GetAvailableBandWidth(t); alloc_tendency := GetAllocTendency(t); With required_bw Case < ABW : If alloc_tendency < 0 then alloc_bw := upgrade(call_id, required_bw); If (alloc_bw < ABW) and (svc_level!= 3) then alloc_bw := upgrade(call_id, alloc_bw); End If Else alloc_bw := required_bw; End If Break; Case == ABW : If alloc_tendency <= 0 then alloc_bw := required_bw; Else alloc_bw := degrade(call_id, required_bw); End If Break; Case > ABW : If alloc_tendency <= 0 then alloc_bw := degrade(call_id, required_bw); If (alloc_bw > ABW) and (svc_level == 1) then alloc_bw := degrade(call_id, alloc_bw); End If End If If alloc_bw > ABW then 23
alloc_bw := 0 End If Break; End With Return alloc_bw; End Method; 33,,,, (zero -one knapsack), n 2 n, Greedy, n m m 24
, m,, 1 [ 3] n, C1, C2,, Cn ABW, [ 3] Method AllocateQueuedCalls ABW : C[] : n : P[][] : Begin Method AscendingSort(C[]); assign GetGreatestCommonDivisor(C[]s and ABW) to Unit; For each call number i For each j Units when j less then ABW/Unit 25
Initialize each component in P End For End For For each call number i For each j Units when j less then ABW/Unit If C[i] > ABW then assign P[i-1][j] to P[i][j]; Else assign Maximum of P[i][j] and 1 + P[i-1][ABW/Unit C[i]/Unit] to P[i][j]; End If End For End For For i := n downto 1 If P[i][ABW/Unit] > P[i-1][ABW/Unit] then Allocate(C[i]); ABW = ABW C[i]; End If End For End Method 26
4 3 41, 5 411 [ 4-1] IMT-2000 (199912) IMT-2000 (199912) ITU ITU [Rapa99a, Rapa99b] [ 4-1] 27
RAPA ITU 75 % 73 % 39 % 40 % 14 % 13 % 17 % 15 % 19 % 15 % 22 % 25 % [ 4-2] [ 4-2] (BHCA) (Call Duration) (BHCA, ) (Call Duration, ) 253 094 066 153 120 104 058 09 031 3 3 3 022 021 012 144 138 135 05 036 011 2529 2137 2233 027 011 006 2603 2165 2227 024 011 007 161 141 156 [ 4-1] ITU [ 4-2] [ 4-3] [ 4-3] 75 % 138 125 39 % 179 3 14 % 018 139 17 % 097 2300 28
19 % 044 2332 22 % 014 153 412 30%,, 1500, 7000 random [ 4-4] [ 4-1] [ 4-1] X, Y [ 4-3] Attempt Success Success (%) 724 486 731% 494 253 563% 115 4 52% 21 0 48% 58 3 34% 17 2 176% Sum 1429 768 573% 29
800 700 600 500 400 300 Attempt Success 200 100 0 [ 4-1] 413 [ 4-5] [ 4-2] [ 4-2] X, Y [ 4-5] Attempt Success Success (%) 724 529 731% 30
494 278 563% 115 6 52% 21 1 48% 58 2 34% 17 3 176% Sum 1429 775 573% 800 700 600 500 400 300 Attempt Success 200 100 0 [ 4-2] [ 4-3], 40%, 31
800% 700% 600% 500% 400% 300% 200% 100% 00% [ 4-3] 32
33 5,,, 40% IMT-2000, WLL(Wireless Local Loop)
[Woo95] M Woo, N Prabhu, A Ghafoor, Dynamic Resource Allocation for Multimedia Services in Mobile Communication Environments, IEEE Journal on Selected Areas in Communications, vol 13, No 5, pp 913-922, June 1995 [Err97] Errin W Fulp and Douglas S Reeves, On-line Dynamic Bandwidth Allocation, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), 1997 [Cho98] Byung Kyu Choi, Riccardo Bettati, Bandwidth Reservation for Real Time Traffic in Wireless Mobile Environment, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, 1998 [Van98] Bobby Vandalore, Raj Jain and Sonia Fahmy, AQuaFWiN: Adaptive QoS Framework for Multimedia in Wireless Networks and its Comparison with other QoS Frameworks, Proceedings of the 24th Conference on Local Computer Networks, 1998 [Luc98] Luca Abeni, Giuseppe Lipari and Giorgio Buttazzo, Constant Bandwidth vs Proportional Share Resource Allocation, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II, 1998 [She97] S Shenker, C Partidge and R Guerin, Specification of Guaranteed Quality of Service, RFC 2212, Sept 1997 [Wro97] J Wroclawski, Specification of the Controlled-Load Network Element Service, RFC 2211, Sept 1997 [ 99],,, " 34
telecommunication review, 9 3,1999 [ 99], CDMA,, 1999 [ 98],, 26 8 19988 [ETRI96], ( ), 199612 [Rapa99a], IMT-2000, http://wwwrapaorkr, 199912 [Rapa99b], IMT-2000, http://w wwrapaorkr, 199912 [ 00],, All-IP QoS, 7 8S, 20008 [ 00a],,, QoS,, 200010 [ 00b],,,, QoS,, 200010 [TTAE00], IMT-2000 3GPP, 3G TS 22105 v380, 20003 35
,,,,,,,,,,,,,,,,,,,,,,,,,, 2000 12