한인구.PDF

Size: px

Start display at page:

Download "한인구.PDF"

유미 천
5 years ago
Views:

1 Dynamic Resource Allocation Algorithm for Optimized Bandwidth Utilization

2 Dynamic Resource Allocation Algorithm for Optimized Bandwidth Utilization

3 2001 2

5 i,,,,

6 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

7 i Abstract ii IMT Erlang B iii

8 1,,, IMT-2000(I nternational Mobile Telecommunication 2000) IMT-2000 (conversational/real-time services), (interactive services), (streaming services),,, 1

9 ,, 2 IMT , 4 5 2

10 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) MHz/ MHz 1997 WRC-97 FPLMTS MHz(2GHz) IMT(International Mobile Telecommunication) , 3 IM T

11 , 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

12 ,, [TTAE00] [ 2-1] IMT-2000 (Speech) 16kbps < 14kbps (Simple Messagin g) < 64kbps, G3, G4 (Switched Data),, (Medium Multimedia) kbps, 128kbps (High Multimedia) - 384kbps, 64kbps,, (High Interactive Multim edia) 128kbps, 384kbps 22 [ 99] ( 5

13 ) ( ) [ETRI96,Wro97] B-ISDN(Broadband Integrated Services Digital Network) [Cho98,Van98] QoS(Quality of Service) QoS, [Luc98],,,, 23 2, 6

14 , (Fixed Chann el Allocation), (Dynamic Channel Allocation), (Hybrid Channel Allo cation), Cox-Rendink, (DR), [Woo95] (DR) Call-by-Call Call-by-Call 7

15 Channel Borrowing Call-by-Call, Call Blocking Rate DCA FCA Call Number [ 2-2],, 232 8

16 (CIR : Carrier to Interference Ratio), Hal pern (Re-Use Partitioning) (Dr),, 7 (Dr=46R) 3 (Dr=3R) 3: R ( :Dr), (CIR), [Err97] ARP (Autonomous Reuse Partition) IMT-2000,, 9

17 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

18 [ 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

19 [ 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

20 3,,, 31,, 30%, 13

21 ,, 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

22 ,,,, 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

23 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 = 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

24 312 i ii (incoming handoff) iii (outgoing handoff) iv, EWMA T A t t 1 A dt t t t t t = 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

25 [ 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

26 321 (queue), (Queuing), QoS (Differentiated Service) (Class Based Queuing) [She97] FIFO(First In First Out) (Drop Tail), (Priority), (starvation), 19

27 ,,,,,,, 6,,,, [Rapa99a] [ 3-1] Input Queue Call Type Based Queue Streaming Video Phone Transaction Call Classification [ 3-1] 20

28 [ 3-1] F IFO,, 33 CallType FIFO (weighted round r obin) Erlang 322 (subscriber) - 21

29 -, -, (NMS: Network Management System) (, ) [ 2] Method CallAdmissionControl 22

30 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

31 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

32 , 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

33 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

34 4 3 41, [ 4-1] IMT-2000 (199912) IMT-2000 (199912) ITU ITU [Rapa99a, Rapa99b] [ 4-1] 27

35 RAPA ITU 75 % 73 % 39 % 40 % 14 % 13 % 17 % 15 % 19 % 15 % 22 % 25 % [ 4-2] [ 4-2] (BHCA) (Call Duration) (BHCA, ) (Call Duration, ) [ 4-1] ITU [ 4-2] [ 4-3] [ 4-3] 75 % % % %

36 19 % % %,, 1500, 7000 random [ 4-4] [ 4-1] [ 4-1] X, Y [ 4-3] Attempt Success Success (%) % % % % % % Sum % 29

37 Attempt Success [ 4-1] 413 [ 4-5] [ 4-2] [ 4-2] X, Y [ 4-5] Attempt Success Success (%) % 30

38 % % % % % Sum % Attempt Success [ 4-2] [ 4-3], 40%, 31

39 800% 700% 600% 500% 400% 300% 200% 100% 00% [ 4-3] 32

40 33 5,,, 40% IMT-2000, WLL(Wireless Local Loop)

41 [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 , 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

42 telecommunication review, 9 3,1999 [ 99], CDMA,, 1999 [ 98],, [ETRI96], ( ), [Rapa99a], IMT-2000, [Rapa99b], IMT-2000, wwrapaorkr, [ 00],, All-IP QoS, 7 8S, [ 00a],,, QoS,, [ 00b],,,, QoS,, [TTAE00], IMT GPP, 3G TS v380,

43 ,,,,,,,,,,,,,,,,,,,,,,,,,,

°í¼®ÁÖ Ãâ·Â

°í¼®ÁÖ Ãâ·Â Performance Optimization of SCTP in Wireless Internet Environments The existing works on Stream Control Transmission Protocol (SCTP) was focused on the fixed network environment. However, the number of