The burst contention problem is resolved based on a comparison between
ATi and ABi to determine whether the incoming burst is in an overrate
(overloaded) flow. If ATi > ABi, the incoming burst is in an overrate flow and
will be dropped to reserve resources for the bursts in an underrate
(unoverloaded) flow. Conversely, if ATi < ABi, the arrival burst is in underrate
flow and the ratio ATi /ABi will be considered. If the value of ATi /ABi is smaller
than that of ATj/ABj, the scheduled burst will be dropped. Conversely, if the
value of ATi /ABi is greater than ATj/ABj, the incoming burst will be dropped.
27 trang |
Chia sẻ: honganh20 | Ngày: 01/03/2022 | Lượt xem: 347 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Research of the fairness control in optical burst switching networks, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
s inherited the advantages from the two others, where no optical buffer
and high-speed optical switche are needed.
1.2 Communication principle of OBS networks
In OBS networks, different types of incoming data are aggregated into data
bursts before being sent (Figure 1.2a). At egress nodes, the bursts will be
disassembled into original packets which are then delivered to their destination
(Figure 1.2b).
Figure 1.1 The process of assembling and disassembling at the edge OBS nodes
1.3 Operations within OBS networks
1.3.1 Assembling
Burst assembling is a method of aggregating packets (such as IP packets,
ATMs, etc.) from different access networks into larger burst at ingress nodes
of the OBS network.
1.3.2 Signaling
There are two main types of signaling protocols in OBS networks: JIT and
JET, in which JET is the signaling protocol implemented for most OBS
networks because it makes better use of the bandwidth.
5
1.3.3 Scheduling
When a control packet arrives at a core node, a scheduling algorithm is
called to schedule its following burst on an output link. There are three main
scheduling mechanisms: (1) scheduling without void filling; (2) scheduling
with void filling and (3) group scheduling.
1.3.4 Contention resolution
As with any packet-switched network, contention also appears in OBS
networks. That is when two burst simultaneously dispute the same resource at
the same link (wavelength). Possible solutions to contentions in OBS networks
include: wavelength conversion, using FDL, deflection routing and
combination of the above solutions.
1.4 Fairness issues in OBS networks
1.4.1 The fairness concept in OBS networks
According to Denda et al. [38], fairness is known as the satisfaction of
individuals in the process of resource allocation. In the OBS network, fairness
issues are distinguished by: delay fairness, throughput fairness and distance
fairness, which are considered at edge and core nodes (Figure 1.7).
FAIRNESS IN OBS NETWORKS
EDGE NODES CORE NODES
DELAY FAIRNESS
THROUGHPUT
FAIRNESS DISTANCE FAIRNESS
Figure 1.7 Fairness classification based on consideration location
1.4.2 Delay fairness
Fairness delay refers to establishing fairly a buffering delay (including
assembling delay and offset time) for bursts of different QoS classes.
6
1.4.3 Throughput fairness
Throughput fairness refers to the fair allocation of bandwidth between flows which
share the same link.
1.5 Summary chapter 1
This chapter has introduced an overview of OBS networks and its
operations, in which the burst assembly at the ingress node is focused on
analysis because it plays an important role in the fairness of entire network.
This chapter has also analyzed and evaluated the methods of fairness control
that have been published so far. That is the basis for the thesis to identify the
research objectives, as well as propose the improved architecture of ingress
node with additional functional modules to ensure the implementation of the
fairness solutions proposed by the thesis.
1.5.1 Distance fairness
Distance fairness refers to dealing with contentions fairly (as measured by
the data loss rate) based on the path length (number of hops) from source to
destination.
1.6 Research objectives
The thesis focuses on the fairness issues at the ingress node to improve the
efficiency of delay and throughput fairness, with four main objectives:
1. Improving and proposing new solution of burst assembly for delay
reduction that applies to each individual queue.
2. Improving and proposing new solution of delay fairness control that
applies to multiple queues with different QoS levels.
3. Improving and proposing new solution of throughput fairness control
that applies to flows of Poisson and Non-Poisson distribution.
4. Proposing new solutions of burst padding to improve communication
performance.
7
CHAPTER 2: BURTS ASSEMBLY FOR DELAY REDUCTION
AND DELAY FAIRNESS
2.1 Model of burst assembly for delay reduction
2.1.1 Issue of the burst assembly delay
The end-to-end delay of a burst transmitted over an OBS network is mainly
caused by four components: (1) the assembly delay at ingress node, (2) the
offset time for resource reservation of the control packet, (3) burst switching
delay at core nodes and (4) propagation delay over core network. Two first
delays are collectively formed a common element which há the name the
buffering delay; two latters usually do not change corresponding to a given
implemented protocol. Therefore, the proposals usually focus on reducing the
buffering delay.
2.1.2 Related works
2.1.2.1 Analysis of the published methodes of burst assembly for delay
reduction
There are 6 published methodes of burst assembly for delay reduction as
shown in Table 2.1.
Table 2.1 Comparison of the published methodes of burst assembly for delay reduction
IE-BADR POQA JK-BADR BADR-EAT MTBA-TP BASTP
Burst
assembly
method
Timer-based Timer-
based
Timer-
based
Timer-based Hybrid Hybrid
Assembly
threshold
fixed fixed fixed fixed fixed addaptivei
Estimation
method
Based on the
average speed
of packets
arriving in the
estimated
time period
Based on
the
length of
the last
M bursts
Based on
the
estimated
error of the
previous
assembly
Based on the
density of
the last M
packets
Based on the
arrival speed
of the last
packet
Based on
M last
burst
assemblies
Reduced
delay
To To To To t1 + To – Ta To
8
2.1.2.2 Comparison and analysis of simulation results
Simulation is done with the following objectives:
Comparing the average estimattion error rate (Formula 2.8) between
the methodes of burst assembly for delay reduction.
(2.8)
where M is the number of assembly times, e
jL and Lj are the
estimation size and the completed size of burst j.
Comparing the number of redundant packets transferred for the next
burst of 100 consecutive assembly times between the methodes of
burst assembly for delay reduction.
Analyzing the way to select the thresholds for BASTP, the best
methode of burst assembly for delay reduction.
The simulations are installed on a PC with 2.4 GHz Intel Core 2 CPU, 2G
RAM. Packets arriving at the ingress node have a Poisson distribution with
exponentially random size in the range of [500, 1000] bytes. Traffic loads
ariving at the queues varies from 0.1 to 0.9. Simulations are performed in 1
second). Data were extracted from NS2 [71] with support package obs-0.9a.
Other parameters include Ta = 6 ms, To = 2 ms
a. Comparison of the average estimation rate
Figure 2.3 shows a comparison of the average estimation error between the
methods of burst assembly for delay reduction. The simulation results show
that the estimation error of the statistical-based methods such as BASTP,
BADR-EAT and POQA being lower than that of other methods.
Figure 2.3 Comparison of the average estimation error rate of IE-BADR, JK-BADR, POQA,
BADR-EAT, MTBA-TP and BASTP with normalized load to 0.5
M
LLL
R
M
j j
e
jj
E
1
/
9
b. Comparison of the number of redundant packets transferred for the
next burst
Figure 2.6 Comparison of the number of redundant packets in 100 consecutive assembly times.
c. Analizing the way to select the thresholds for BASTP
As described in Figures 2.3 and 2.6, BASTP always gives the best
simulation results. However, these results is often accompanied by a pairs of
suitable selected threshold value (Lmin, Lmax).
2.1.2.3 Comments
The above analysis, comparisons and evaluations (published in [CT1]) are
the basis for proposing the improvements of burst assembly for delay reduction
which are presented in the following sections.
2.1.3 Method of burst assembly for delay reduction iBADR
2.1.3.1 Introduction to the incoming traffic estimation method TW-EWMA
To estimate the incoming traffic at a queue, Salad et al. [23] proposed the
TW-EWMA method. Unlike other estimation methods that often count
incoming packets at continuous observation intervals (estimation cycles), TW-
EWMA only counts in a smaller estimation time window (Tw) to reduce the
calculation cost (Figure 2.7).
TW1 TW2 TW3 TWn
Times
a estimated cycle a estimated cycle
Figure 2.1 The estimation time windows in TW-EWMA
2.1.3.2 Method of burst assembly for delay reduction iBADR
The iBADR (improved Burst Assembly for Delay Reduction) method is
also based on the idea of sending the control packet early at the time
oa TTt 1 (Ta > To) and the corresponding burst is sent at the time aTt 2
10
; As a result, the delay of packets carried in the current burst is reduced a period
To. The thesis uses TW-EWMA [23] to estimate the arriving packet rate,
thereby estimating the completed burst size.
The authors in [23] set α to a fixed value (equal to 0.3), which does not in
fact reflect the abnormal changing nature of the incoming traffic; The result is
a significant estimation error. The thesis proposes to change α in a flexible way
according to the ratio of current rate (cur) and average rate (λavg) of incoming
packets as Formula 2.12.
curavg
cur
avg
cur
1
(2.12)
In order to increase the accuracy of the estimation, the thesis flexibly adjusts
the time threshold based on the average estimation error of the previous burst
assembly times according to Equation 2.13.
L
LL
RR
e
E
)(
)1(
(2.13)
2.1.3.4 Comparison and analysis of simulation results
The simulation parameters for this part are similar to Section 2.1.2.2.
a. Comparison of the average estimation error rate
The results in Figure 2.8 show that iBADR has the smallest estimation error
rate.
Figure 2.8 Comparison of the average estimation error rate between iBADR and previous
methods
b. Comparison of the number of redundant packets in 100 consecutive
assembly times
Figure 2.10 shows a comparison on the number of redundant packets
11
between iBADR and previous methods, where the number of redundant bursts
of iBADR is significant.
Figure 2.10 Comparison of the number of redundant packets in 100 consecutive assembly
times.
2.1.3.5 Comments
Based on simulation results, iBADR achieved a estimation error rate lower
than that of BASTP, but it generates relatively many redundant packets as
shown in Figure 2.10. The method of burst asembly for delay reduction iBADR
has been published in [CT2].
2.1.4 Method of burst assembly for delay reduction OBADR
2.1.4.1 Description
The OBADR (Optimal Burst Assembly for Delay Reduction) method is an
improvement of iBADR, in addition to applying the burst length estimation
method TW-EWMA with flexibly adjusted , the burst assembly process is a
combination of the 2 assembly stages:
Stages 1: When the first packet arrives at a queue, the timer of the
queue is triggered. The control packet is only sent to the core network
when the timer reaches the threshold Tw, which is the size of the time
window. The estimated length (
eL ) is also calculated based on TW-
EWMA with flexibly adjusted .
Stages 2: The burst assembly process continues, but now based on the
estimated length threshold. The burst is only completed when the
number of packets arriving in the queue reaches the threshold
eL .
2.1.4.3 Comparison and analysis of simulation results
The simulation parameters for this part are similar to Section 2.1.2.2.
12
a. Comparison of the average estimation error rate
Figure 2.11 shows that the average estimation error rate ( ER ) of OBADR
is lower than that of all previous methods.
Figure 2.11 Comparison of the average estimation error rate between OBADR and previous
methods
b. Comparison of the number of redundant packets in 100 consecutive
assembly times
Figure 2.13 Comparison of the number of redundant packets in 100 consecutive assembly
times.
As shown in Figure 2.13, OBADR does not generate redundant packets.
This is due to the estimated lengths used as the length threshold in burst
assembly.
2.1.5 Effect of the factor α on OBADR
2.1.5.1 Investigating the variation of α depending on the load changes
With the normalized load changing from 0.1 to 0.9 and α changing from 0.1
to 0.9, the simulation results show that the estimation error is minimum when
α has a distribution in the range of (0.4, 0.6). Thus, the fixed α setting is clearly
not suitable when arriving load is varied.
13
2.1.5.2 Comparing the burst assembly efficiency when α is fixed and varied
Simulation results show that dynamic α results in a better average
estimation error than fixed α (α = 0.5) when the assembly time is small (from
2.5 ms to 5.5 ms).
2.1.5.3 Comments
Based on the simulation results, flexible adjustment of α values (such as
Equation 2.12) depending on the incoming traffic rate has increased the
efficiency of estimating the complete burst length. This result also confirms
the effect of flexible adjustment of α according to the incoming traffic rate.
The results of this study were published in [CT4].
2.1.6 Effect of OBADR on scheduling
2.1.6.1 Analyze the effect of OBADR on scheduling based on Engset method
2.1.6.2 Comparison of the analysis model and simulation result
As shown in Figure 2.19, OBADR achieves a lower probability of burst
loss compared to the traditional model in theory and simulation.
Figure 2.2 Comparison on the probability of burst loss between OBADR and traditional
model
2.1.6.3 Comments
Based on the analysis and simulation results, OBADR has proven to be the
most efficient burst assembly method in term of low estimation error, reduced
delay and minimized burst loss rate. The method of burst assembly for delay
reduction OBADR was published in [CT3].
2.2 Model of burst assembly for delay fairness
2.2.1 Related works
The models of burst assembly for delay reduction share a common idea of
sending the control packet early before the burst is completed. Among these
14
models, only POQA [69] is associated with service differentiation.
Specifically, the authors in [69] have set different offset times for bursts with
different priority classes and adjusted the assembly times so that the higher
priority burst is, the shorter the buffering time. As the example shown in Figure
2.21, the burst with the highest priority class class0 has the smallest assembly
time Ta(0) and the largest offset time To(0), while the lowest priority class
class2 has the longest assembly time Ta(2) and the smallest offset time To(2).
class0
class1
class2
Ta(2)
To(2)
Ta(1)
To(1)
Ta(0)
To(0)
Figure 2.3 An example of time thresholds and offset times for 3 classes
2.2.2 Method of burst assembly for delay fairness BADF
2.2.2.1 Introduction to the delay fairness in OBS networks
With the concept of delay fairness proposed in [69], higher priority burst
will have a shorter buffering time. However, this interpretation has not yet
shown the nature of the fair response to individuals in the notion of fairness.
Therefore, the thesis supplements the concept of delay fairness as follows:
Delay fairness is the satisfaction on delay between different priority bursts,
such that the average ratio of the end-to-end delay to their limited delay is
approximative. In addition, in order to meet the requirement for prioritizing
delays in OBS networks, the following two constraints were added.
1. The higher the priority is, the lower the end-to-end delay is; and
2. The end-to-end delay of a burst is not greater than its limited delay
(Example: RTT of IP packets carried in a burst).
Thus, the concept of "delay fairness" added by the thesis implies the
concept of delay fairness proposed in [69].
2.2.2.2 Index of delay fairness
Let D(i) be the average delay that packets must wait in queue i before being
aggregated into a burst and Ta(i) is the assembly time of queue i, xi = D(i)/Ta(i)
will reflect the delay of the packets in queue i. The thesis proposes a formula
to calculate the DFI delay fairness index for different priority bursts based on
15
Jain's formula in [39] as follows:
n
i ii
n
i ii
xn
x
DFI
1
2
2
1
)(
(2.22)
Fairness will increase as DFI approaches 1, and equals 1 when
nn xxx ...2211 , where i is the weight of xi, 0 < i < 1 and
1
1
n
i i
.
2.2.2.3 Method of 2-stage burst assemly
The Burst Assembly for Delay Fairness (BADF) method is also based on
the idea of sending control packets early (see Section 2.1.3 and 2.1.4), but
adding new points in the 2-stage assembly model. Stage 1 is a estimated time
threshold-based burst assembly and Stage 2 is a estimated length threshold-
based burst assembly. The 2-stage assembly model is in detail as follows:
Stage 1: when the first packet arrives at queue i, the timer is triggered. The
control packet is only sent when the timer reaches the estimated time threshold
Te(i) = Ta(i) – To(i). The estimated burst length is calculated based on the TW-
EWMA method [23]:
)()()())(1()()( iiiiiTiL curavgae (2.25)
During this period, the value of α(i) is adjusted to increase/decrease
depending on the rate of packet arrival at queue i, calculated by α(i) =
cur(i)/(avg(i) + cur(i)), instead of being fixed as in [23]
Stage 2: the burst assemly algorithm continues until either the length
threshold )(iL
e
or time threshold Ta(i) is reached.
2.2.2.5 Comparison and analysis of simulation results
Assuming that incoming packets belong to three priority classes (K = 3),
have Poisson distribution and have exponential distribution sizes in the range
[500, 1000] bytes; three priority queues 1, 2 and 3 are therefore used with the
offset times set to 0.3, 0.2 and 0.1 (ms), respectively.
Simulation objectives include:
Comparing the DFI index between BADF and POQA;
Analyzing the impact of the delay fairness on the assembly time
Ta(i) and the buffering delay;
16
Comparing the estimation error (Formula 2.8) between BADF and
POQA.
a. Comparison of the DFI index between BADF and POQA
Figure 2.4 Comparison of the DFI index between BADF and POQA
b. Analyzing the impact of the delay fairness on the assembly time Ta(i)
and the buffering delay
As shown in Figure 2.25, the assembly time Ta(i) decreases as the incoming
traffic of packets increases, with class0 during the simulation period [0.4, 0.6]
and with class2 during the simulation period [0.7 , 0.9].
Figure 2.5 Comparison of Ta(i) between 3 priority classes with BADF
c. Comparison of the estimation error between BADF and POQA.
Figure 2.60 Comparison of the estimation error between BADF and POQA
17
Figure 2.30 shows a comparison of the estimation error rate (Formula 2.8)
between BADF and POQA, where the estimation error of BADF is much
smaller than that of POQA.
Figure 2.7 Comparison of the bandwidth wasting rate between BADF and POQA
Figure 2.8 Comparison of re-send rate between BADF and POQA
2.2.2.6 Comments
The BADF algorithm has been proven to effectively control the delay
fairness between different QoS queues, based on DFI index, estimation error,
and re-send rate. One drawback of BADF, however, is the high bandwidth
wastage rate about 12% on average (Figure 2.31). However, if compared with
the re-send rate of POQA (about 30% on average), BADF is better. The BADF
algorithm and the above results have been published in [CT5].
2.3 Summary chapter 2
This chapter presents two proposed models of delay reduction iBADR
[CT2] and OBADR [CT3], and a model of delay fairness BADF [CT5]. Based
on simulation results, iBADR and OBADR achieve lower delay than previous
proposals. BADF also achieves the delay fairness which is almost optimal,
while reducing the delay and minimizing the estimation error on the queues.
18
CHAPTER 3: THROUGHPUT FAIRNESS
BASED ON BANDWIDTH ALLOCATION AND BURST PADDING
3.1 Model of bandwidth allocation with throughput fairness
3.1.1 Introduction to fair bandwidth allocation
Fair bandwidth allocation, also known as rate fairness, refers to allocating
bandwidth for connections proportional to the provided bandwidth to the
available bandwidth [53].
3.1.2 Related works
So far, the models of fair bandwidth allocation in OBS networks are based
on the max-min fair bandwidth allocation model in IP networks [16], such as
MMFP and RFP.
3.1.3 Bandwidth allocation with throughput fairness TFBA
3.1.3.1 Architecture of the ingress node supporting QoS
Consider an ingress node with an architecture as shown in Figure 3.3.
Figure 3.1 Architecture of the ingress node supporting QoS
3.1.3.2 Maximum bandwidth ratio for each link in OBS networks
Table 3.1 Maximum throughput rate per link with different normalized loads
Normalized load 0.5 0.6 0.7 0.8 0.9 1.0
Maximum throughput 0.48616 0.572186 0.67152 0.72123 0.7213 0.71945
3.1.3.3 Description of TFBA
The idea of TFBA is to adjust actual throughput close to the fair allocation
bandwidth to ensure fair bandwidth allocation between flows.
The process of allocating bandwidth with fairness throughput includes 4
steps:
Step 1: Determine the fairness rate Fi for each connection
19
If the incoming traffic of flow i varies significantly, the bandwidth is first
divided among the connections, the ratio Fi of each connection is determined
as the minimum of the actual throughput (Ai) and the fairly allocated
bandwidth. Connections with actual throughput less than the allocated
bandwidth will not participate in the redundant bandwidth sharing process in
the next time. The allocation is continued until the allocated bandwidth (m)
does not change from the previous time (m = mprev) or all connections are
satisfied (m = 0).
Step 2: Determine the fairly allocated bandwidth ABi for each connection
Let Bw be the maximum output bandwidth, the fair allocation bandwidth for
connection i is determined by Equation 3.4
BwFAB ii (3.4)
where Fi is the fairness ratio determined in Step 1.
Step 3: Measure the actual throughput ATi of each connection
Actual throughput is determined by Formula 3.5
)(/)( iTipAT wwi (3.5)
where pw(i) is the number of packets arriving in the time window Tw(i).
Step 4: Handling burst contention
The burst contention problem is resolved based on a comparison between
ATi and ABi to determine whether the incoming burst is in an overrate
(overloaded) flow. If ATi > ABi, the incoming burst is in an overrate flow and
will be dropped to reserve resources for the bursts in an underrate
(unoverloaded) flow. Conversely, if ATi < ABi, the arrival burst is in underrate
flow and the ratio ATi /ABi will be considered. If the value of ATi /ABi is smaller
than that of ATj/ABj, the scheduled burst will be dropped. Conversely, if the
value of ATi /ABi is greater than ATj/ABj, the incoming burst will be dropped.
3.1.3.4 Index of throughput fairness
The fair bandwidth allocation approach proposed by the thesis also comes
from the idea of max-min fairness, but based on the ratio between actual
throughput and provided bandwidth, instead of probability of loss. as in [67],
[53]. Specifically, set yi = ATi / ABi is the ratio between the actual throughput
(ATi) and the fair allocation bandwidth (ABi) of flow i. Based on Jain's formula
in [39], the thesis proposes the throughput fairness index (TFI) as follows:
20
n
i ii
n
i ii
yn
y
TFI
1
2
2
1
)(
(3.6)
where σi is the weight that represents the actual used bandwidth compared to
the provided bandwidth between the flows, 0 < σi < 1 and 1
1
n
i i
.
3.1.3.6 Comparison and analysis of simulation results
Simulation objectives include:
- Comparing the byte loss rate between connections and the average byte
loss rate among TFBA, MMFP and RFP
- Comparing the fairness based on TFI among TFBA, MMFP and RFP.
Because the simulation objective only considers the byte loss rate of the
connections which share the same (or group of) output link(s), the Dumbbell
simulation network as shown in Figure 3.5 is sufficient to evaluate the
effectiveness of the proposed algorithm.
Figure 3.2 Simulation network topology
a. Comparison of the byte loss rate between connections
Figure 3.3: Comparison of the byte loss rate between 3 connections with TBFA in 2 cases: (1)
The total load does not exceed the link capacity and (2) the load of connection 3 spikes
beyond the link capacity
21
Figure 3.4 Comparison of the average byte loss rate on 3 connections of TFBA, RFP and
MMFP
b. Compar
Các file đính kèm theo tài liệu này:
- research_of_the_fairness_control_in_optical_burst_switching.pdf