تخصیص پهنای باند با ازدحام ذرات متا هیوریستیک برای شبکه های نوری منفعل اترنت
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|8054||2010||6 صفحه PDF||سفارش دهید||5619 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computer Communications, Volume 33, Issue 4, 1 March 2010, Pages 526–531
This paper considers the bandwidth allocation problem for an Ethernet Passive Optical Network (EPON). An EPON is one of the best options for high-speed access networks. This paper formulates the optimal bandwidth allocation problem with an analytical model to maximize throughput and weighted fairness simultaneously. First, the optimal solution under certain conditions is characterized. Then, two heuristic algorithms are devised which optimize the allocation problem under general conditions. One heuristic is a straightforward constructive one while the one use the Particle Swarm Optimization (PSO) meta-heuristic, the first known application of PSO to the EPON bandwidth allocation problem. The heuristics are tested and compared with previously published results. The computational experience shows that our algorithms are both effective and efficient in allocating bandwidth on an EPON.
This paper considers the bandwidth allocation problem on an Ethernet Passive Optical Network (EPON), where there is one common fiber connecting several access points which share the bandwidth of the fiber. To provide service, two types of passive components are used. One is the Optical Line Terminal (OLT) and the other is the Optical Network Unit (ONU). The OLT provides connection between the backbone and access networks at a central office, and the OLT allocates the common bandwidth according to requested demands from the connected access points. The requests for bandwidth occur from ONUs located on the access side of the network. The ONU has buffer memory for incoming traffic from customers and for outgoing traffic to the OLT, and considers the transmission priority of the packets waiting in the buffers. To transmit the traffic from OLT to ONU, OLT broadcasts the traffic and then each ONU receives the packets. However, channels must be classified for transmission of the packets from ONUs to an OLT since there are many ONUs and there are conflicts when ONUs try to transmit packets simultaneously. EPON uses the Time Division Multiple Access (TDMA) method to resolve conflicts. The bandwidth allocation problem is to find a mechanism for sharing the common bandwidth without conflict. Many studies have been published on how to allocate the common bandwidth to the ONUs. For example, Kramer et al.  and Bai et al.  developed bandwidth allocation algorithms of interleaved polling with adaptive cycle time (IPACT), and Kramer et al.  developed a two-stage buffer mechanism to reduce the light-penalty problem of IPACT. Assi et al.  suggested an Enhanced Dynamic Bandwidth Allocation (EDBA) algorithm. An et al.  developed a Hybrid Slot-Size/Rate (HSSR) algorithm, and Yang et al.  presented a burst polling algorithm for bandwidth allocation. A good survey on these methods is given by Zheng and Mouftah . These papers all address finding good heuristic solutions with respect to some specific measure such as throughput, fairness or delay time. For example, Bai et al.  developed a weighted-based bandwidth algorithm (W-DBA) to improve fairness, delay time and link utilization. W-DBA assigns the excess bandwidth to each ONU proportionally to each relative weight. The authors showed that W-DBA is superior to another published algorithm (M-DBA) for randomly generated asymmetric traffic. Our paper formulates the allocation problem as a nonlinear mathematical one and develops bandwidth allocation algorithms which maximize throughput and weighted fairness simultaneously. Characterizing the optimal allocation under certain conditions is one goal of this paper. The other goal is to develop an effective optimizer to the problem under general conditions. This paper is structured as follows: Section 2 describes and formulates the bandwidth allocation problem. The bandwidth allocation problem is characterized, and two heuristic algorithms are developed in Section 3. These algorithms guarantee an optimal solution under a specific condition derived in Section 3. Section 4 carries out a number of numerical tests to evaluate the proposed algorithms by considering throughput, fairness, and computation time. Finally, Section 5 contains concluding remarks.
نتیجه گیری انگلیسی
This paper considers an EPON system which uses a fiber for each direction of traffic. An efficient bandwidth allocation method is required to use the common fiber. This paper formulates the bandwidth allocation problem to maximize throughput and weighted fairness simultaneously. The optimal allocation is characterized, and two heuristic algorithms are designed based upon the characterization. The first algorithm is a very fast heuristic one, which is optimal under certain restricted conditions, and the second one is a PSO meta-heuristic. This is the first known application of PSO to the EPON bandwidth allocation problem. We test both heuristics and compare to recent results from the literature. The results show that the heuristic algorithms perform well over a range of problem instances and types (symmetric versus asymmetric and different load values and varying numbers of ONU’s). The PSO nearly dominates a standard method from the literature (W-DBA from ). Even though this paper considers the multiplicative objective function form of throughput and fairness, other forms such as throughput plus fairness could be also solved with our algorithms by modifying Eq. (7) of the PSO. As another avenue of research, for a given amount of allocated bandwidth to each ONU, the sequencing rule of Weighted Shortest Processing Time (WSPT) could be used to reduce delay time. But, bandwidth allocation and scheduling of packets need to be considered simultaneously, which is complicated.