Abstract
Hop-based burst-cluster transmission has been proposed to improve fairness in optical burst switching networks, and a burst-cluster is generated from multiple bursts. By arranging bursts from the smallest number of hops to the largest one, the burst loss probability for a small (large) number of hops increases (decreases), improving fairness. However, depending on the amount of traffic on each link, the burst loss probability for a small number of hops becomes larger than that for a large number of hops for some source nodes. Therefore, all source nodes can not always improve fairness. In this paper, an adaptive burst reordering algorithm for the hop-based burst-cluster transmission is proposed. Here, each source node calculates the burst loss probability for each number of hops from the number of received ACK and NACK messages. Next, the source node changes the order of bursts within a burst-cluster dynamically. The performance of the proposed method has been evaluated in tandem networks and mesh networks such as NSFNET and ARPA2 by simulation. Numerical examples show that the proposed method is effective for improving the local fairness for each source node regardless of the amount of traffic on each link.
Keywords
Introduction
With the increasing growth of bandwidth sensitive and bandwidth-hungry multimedia applications, wavelength division multiplexing (WDM) has been proposed as an effective choice to meet the increasing bandwidth demands [1–4]. Optical Burst Switching (OBS) [5,6] is an optical switching scheme that carries IP traffic over WDM and backbone networks [7]. In OBS, the unit of transmission is a burst, which is assembled from multiple IP packets using various schemes [8]. A control packet first reserves wavelength resources and then a burst is transmitted. Here, the control packet reserves wavelength resources using immediate reservation or delayed reservation protocols. In the immediate reservation technique [9], the wavelength resources are reserved immediately after the control packet is processed. On the other hand, in the delayed reservation technique [10], the wavelength resources are reserved only for the duration of the burst transmission. Moreover, technologies have been proposed in order to decrease the switching time of the optical switch [11] and the packet processing time [12–14] thanks to the advancement of signal processing technology. Therefore, the performance of immediate reservation protocols approaches that of delayed reservation protocol [14]. Furthermore, due to its easy implementation, the immediate reservation is more likely to be utilized in the future.
In OBS networks, a burst is lost if its control packet cannot reserve a wavelength at a link from source to destination [15]. Here, the burst loss probability is defined as the ratio of the number of lost bursts over the total number of requested transmissions of bursts. In OBS networks with immediate reservation, the burst loss probability becomes large (small) as the number of hops increases (decreases), resulting in unfairness in terms of the burst loss probability [16,17]. In the literature, there has been extensive research work in order to improve fairness in OBS networks. In [18], if a burst with a number of hops larger than a predefined number α cannot reserve a wavelength, the burst can preempt another burst if the number of hops of the preempted burst is smaller than α. Hence the loss probability of burst with high number of hops is decreased, improving fairness. In [19], adaptive routing is used to improve fairness. If the link congestion is high, the burst may change the initial route and search for an alternative route with available wavelengths. hence, fairness improved because wavelengths are used more effectively. In [20], the burst assembly time of bursts with high burst loss probability. is decreased, hence improving fairness. In [21], the proposed scheme improves fairness using priority rules. A burst with a high (low) number of successful transmissions is given a low (high) priority. Here, when congestion occurs, bursts with high priority are transmitted and bursts with low priority are dropped, improving fairness. In [22], congestion occurs when the amount of traffic at links is high, increasing the burst loss probability and unfairness. Therefore, the control packet can reserve wavelengths with a higher probability if the arrival rate is decreased. Here, the arrival rate for bursts with the same destination node is decreased (increased), if the amount of traffic at the links until the destination node is larger (smaller) than a predefined arrival rate. Hence, wavelengths are used more effectively and fairness is improved.
Most of the methods discussed above are effective in improving fairness, but the overall burst lost probability is increased. In [23], hop-based burst-cluster transmission has been proposed. In this method, a burst-cluster is generated from multiple bursts, and bursts are arranged within the burst-cluster in order from the smallest number of hops to the largest one. In hop-based burst-cluster transmission, each control packet performs the wavelength reservation process only at its last-hop link. Hence, the number of wavelength reservations for any burst in the burst-cluster is one regardless of the number of hops, improving fairness. Moreover, the overall burst probability is decreased because no burst preemption is performed. However, in this method, a burst is dropped at an intermediate node if the amount of traffic on its last-hop link is high. Here, the control packet of the next burst in the burst-cluster will attempt wavelength reservation again, and may succeed in reserving the wavelength if the congestion has cleared. Hence, the burst loss probability for a small number of hops becomes larger than that for a large number of hops, and the number of wavelength reservation per burst is larger than one. As a result, hop-based burst-cluster transmission does not improve fairness if the amount of traffic at the last-hop link is high [24].
In this paper, we propose an adaptive burst reordering algorithm for hop-based burst-cluster transmission in order to improve fairness regardless of the amount of traffic at the last-hop link. In the proposed method, an ACK (NACK) message is received at the source node if a burst transmission has succeeded (failed). Here, each source node calculates the burst loss probability for each number of hops from the number of ACK or NACK messages. Based on the calculated loss probabilities, the source node changes the order of bursts within a burst-cluster dynamically. Here, a burst with a larger loss probability is positioned behind a burst with a smaller one. This is because a burst in the rear part of a burst-cluster can reserve a wavelength with a higher probability. Therefore, it is expected that burst loss probabilities are almost the same regardless of the number of hops for each source node. The performance of the proposed method is evaluated in tandem networks, NSFNET as well as ARPA2 by simulation, and the effectiveness of the proposed method is investigated.
The rest of the paper is organized as follows. Section 2 summarizes the hop-based burst cluster transmission, and Section 3 explains adaptive burst reordering. Simulation results are shown in Section 4 and Finally, conclusions are presented in Section 5.

Hop-based burst-cluster transmission for an OBS network with six nodes.
Overview
Hop-based burst-cluster transmission [23] was proposed in order to improve fairness of the burst-cluster transmission [25]. Figure 1 considers the case of an OBS network with six nodes, and the source node is the leftmost node. This node has one link and five destination nodes. Here, for each source node’s output link, a burst-cluster is generated. At the source node, for each output link, six bursts are assembled simultaneously and ordered from the smallest numbers of hops to the highest number of hops. Here, each burst has its own control packet. Then, a hop-based burst-cluster is generated from the assembled bursts and is transmitted to destination nodes with the control packets. As shown in Fig. 1, a burst for each destination node is assembled, therefore the number of bursts in a burst-cluster is the same as the number of destination nodes. If there are multiple destination nodes at two or more hops, the order of these bursts is determined at random. Note that each burst has its own control packet.

Hop-based burst-cluster transmission when the amount of traffic is high on links 2 and 4.
The fundamental difference between the hop-based burst-cluster transmission and the original immediate reservation is that the preceding control packet reserves a wavelength not only for its own burst but also for the following bursts within the burst-cluster. An example of hop-based burst-cluster transmission when the amount of traffic is high at some links is illustrated in Fig. 2. In this figure, a wavelength on link 1 is reserved by the control packet of the one-hop burst for the transmission of the one-hop burst and the following bursts (two-hop, three-hop, four-hop and five-hop bursts). Therefore, the control packets of these remaining bursts do not perform wavelength reservation and are forwarded directly to node A. At node A, the one-hop burst is extracted from the burst-cluster because it arrived to its destination node. Similarly, the remaining bursts at the burst-cluster will be extracted at nodes B, C, D and E. If the control packet of the one-hop burst cannot reserve a wavelength on link 1, the one-hop burst is dropped In this case, the wavelength reservation process at link 1 is performed again by the control packet of the two-hop burst. As illustrated in this figure, each control packet reserves only one wavelength its last hop link, if wavelength reservations succeed. Consequently, the number of wavelength reservations for each burst is one regardless of the number of hops, hence improving fairness. Moreover, hop-based burst-cluster transmission reduces the redundant wavelength reservation which is required in the original immediate reservation, decreasing the overall burst loss probability.
Moreover, hop-based burst-cluster transmission requires a void between two consecutive bursts. Figure 3(a) shows a case where there is no void. As shown in this figure, when two bursts are forwarded to different output links, a preceding burst is preempted by the next one. Therefore, a void is used for avoiding an undesirable preemptions. In Fig. 3(b), the size of each void can be determined from the number of hops of the next burst, the processing time of a control packet δ, and at which transmission hop the two bursts are switched to different output links. In order to decrease the redundant wavelength reservation, the accurate size of each void is required, and hence the information about the route of each burst is required.

The impact of void on burst preemption.
As shown in the previous subsection, it is expected that the number of wavelength reservations is only one regardless of the number of hops. This means that the wavelength reservation for each burst is performed only at its last-hop link. Figure 2 shows a tandem network where the amount of traffic on link 2 and link 4 is high. In this network, link 1, link 2, link 3, link 4 and link 5 are the last-hop link of the one-hop, the two-hop, the three-hop, the four-hop, and the five-hop bursts, respectively. On link 1, the control packet for the one-hop burst can reserve a wavelength easily due to low traffic, and the transmission of the one-hop burst succeeds. However, on link 2, the control packet of the two-hop burst cannot reserve a wavelength due to congestion, and the two-hop burst is lost. Nevertheless, the control packet of the three-hop burst can reserve a wavelength on link 2 because the congestion has been resolved. Moreover, the control packet for the three-hop burst can reserve a wavelength on link 3 easily due to low traffic. Similarly, the four-hop burst cannot be transmitted due to congestion at link 4 and the five-hop can be transmitted because the congestion has been resolved.
From the above, the loss probability of the three-hop burst becomes smaller than that of the two-hop burst, and the loss probability of the five-hop burst becomes smaller than that of the four-hop burst. Therefore, the hop-based burst-cluster transmission can not always improve the local fairness for all source nodes.
Adaptive burst reordering
In this section, we propose an adaptive burst reordering algorithm for hop-based burst-cluster transmission in order to improve fairness regardless of the amount of traffic at the last-hop link. In the proposed method, a burst-cluster is assembled and transmitted from the ingress node to its egress node, with multiple control packets. Here, each control packet reserves a wavelength from the corresponding burst to the rearmost burst, at each intermediate node. Therefore, our method improves fairness by changing the method of wavelength reservation. Hence, our method is available at the signaling phase, and can be used for any reservation protocol. However, it is more effective for immediate reservation. This is because burst-cluster transmission can decrease the redundant wavelength utilization time that is caused by explicit wavelength reservation. As a result, our method can be used as a wavelength reservation protocol for OBS networks.

Assignment of burst number for computing burst loss probabilities.

Adaptive burst reordering with ACK and NACK messages.
As illustrated in Fig. 4, there is a total of N burst-clusters and L bursts in the network, and each burst has a unique number. In the proposed method (see Fig. 5), we implement the use of ACK and NACK messages, which are received by a source node. As shown in this figure, if the burst transmission succeeds, an ACK message is sent to the source node. Conversely, a NACK message is sent if the wavelength reservation for the burst fails. Each ACK and NACK message correspond to a specific burst transmission. Let h denotes the number of hops information for a burst, and bursts with the same source and destination nodes are denoted as l. Also let

Adaptive burst reordering based on the calculated burst loss probabilities.
Then, the burst loss probability for a burst with identifier l within a burst-cluster,

Hop-based burst-cluster transmission with adaptive burst reordering.
In the proposed adaptive burst reordering, the source node determines the order of bursts in a burst-cluster based on
Moreover, in our proposed method we introduce a void (see Fig. 3) between two consecutive bursts in order to avoid an undesirable burst preemption. As shown in Fig. 7, a burst-cluster is forwarded from a source node when adaptive burst reordering is used. Here, N denotes the number of destination nodes.
When all nodes have only one output link, all bursts within a burst-cluster follow the same route. Therefore, there is always one burst for each hop in a burst-cluster. However if nodes have more than one output link and if an intermediate node between a source and its destination has more than one output link, then all the bursts within the burst-cluster will follow the same route until that intermediate node. After that, bursts will take different routes until the destination node. Consequently, it is often the case where there is more than one burst for each hop. In this situation, at that intermediate node, one output link may have a have a high traffic load while the other output link a low traffic load. Therefore, in the proposed method, if there are multiple burst with the same number of hops in a burst-cluster, each burst’s loss probability is computed independently. Hence, adaptive burst reordering is independent of the network topology, and fairness is improved regardless of the number of output links.
Here, computing the average burst loss probability for each hop, would not take into consideration the difference in traffic loads at the output links of the intermediate node. For the proposed method is efficient in determining the bursts’ order within a burst-cluster, it is necessary to have an accurate burst loss probability.

Network topologies.
In this section, the performance of the proposed adaptive burst reordering is evaluated in a tandem network, NSFNet, and ARPA2 by simulation. Figure 8(a) shows a tandem network with five nodes and four links. The number of wavelengths on each link is eight and the transmission speed of a wavelength is 10 Gbps. The length of each link is 200 km. In addition, the processing time of a control packet is equal to 1.0 μs and the optical switching time is 1.0 μs. As for NSFNET and ARPA2, shown in Figs 8(b) and (c), there are 16 wavelengths per link and the length of each link is from 300 km to 2800 km. The remaining parameters have the same value as the ones of the tandem network.Here, IP packets arrive at the tandem network according to the Poisson process with rate 200 [packets/μs]. Source and destination nodes of an arriving IP packet are selected at random. The size of an IP packet is set to 1,250 bytes. From the arriving IP packets, a burst-cluster is generated according to the timer/threshold based assembly algorithm, where the timeout value is 10 ms and the maximum burst-cluster size is 60 Mbits. The order of bursts is determined by using adaptive burst reordering, and the generated burst-cluster is transmitted from the source node. The time interval between consecutive burst-cluster transmissions at the source node is exponentially distributed with rate λ [clusters/ms].
For the performance comparison, the performance of the conventional hop-based burst-cluster transmission is also evaluated. In this method, adaptive burst reordering is not used. In addition, the performance of the original immediate reservation is evaluated. For this method, the maximum burst size is set to 20 Mbits, so that the burst sizes for the three methods are almost the same.

Burst loss probability vs. arrival rate (node 0 and link 0) in tandem networks.

Burst loss probability vs. arrival rate (node 3 and link 2) in tandem networks.
First, the impact of adaptive burst reordering on fairness is investigated. Figure 9 shows the burst loss probability of each number of hops for both the conventional hop-based burst-cluster transmission and the proposed method at node 0 with output link 0. For the conventional method, the burst loss probabilities of one-hop and four-hops are smaller than those of two-hops and three-hops (see Fig. 9(a)). This is because the amount of traffic on link 0 and 3 are small, which are the last-hop links for one-hop burst and four-hop burst, respectively. Therefore, the conventional hop-based burst-cluster transmission can not improve fairness. However, as shown in Fig. 9(b), the proposed method can improve the fairness so that the burst loss probabilities of two-hops and three-hops never exceed that of four-hops. Figure 10 shows the burst loss probability of each number of hops for the burst-cluster transmission from node 3 with output link 2. Note that there is no burst transmission of four-hops. From Fig. 10(a) and (b), the conventional method cannot improve the fairness but the proposed method can provide almost the same burst loss probability for each number of hops. Figure 11 shows the fairness index [20] against the overall burst loss probability for some pairs of source node and output link. Here, when the fairness index is close (not close) to one, this index denotes that fairness is improved (not improved). From this figure, for all three cases, the fairness index of adaptive burst reordering is much closer to one compared to that of the conventional hop-based burst-cluster transmission. Therefore, adaptive burst reordering is effective for improving fairness.

Fairness index for tandem networks.

Overall burst loss probability for tandem networks.
The largest burst loss probability for each pair of source node and output link when
In this subsection, the effect of the burst loss probability on the arrival rate is investigated for both the proposed and the conventional methods. Figure 12 shows the overall burst loss probabilities for the proposed method, the conventional hop-based burst-cluster transmission, and the original immediate reservation. From this figure, the overall burst loss probability for the proposed method is slightly larger than that for the conventional hop-based burst-cluster transmission. This is because by changing the order of bursts in a burst-cluster, the loss probabilities of bursts increase in order to improve fairness. Nevertheless, the proposed method can provide a smaller overall burst loss probability than the original immediate reservation. Table 1 shows the largest burst loss probabilities and its number of hops for some pairs of source node and output link. From this table, it is shown that with the proposed method, each source node can decrease the largest burst loss probability among the ones for all destination nodes further than the conventional hop-based burst-cluster transmission. These results denote that all bursts can use wavelengths more fairly.

NSFNET topology.

ARPA2 topology.
In this subsection, the performance of both the conventional hop-based burst-cluster transmission and the proposed adaptive burst reordering are evaluated in the NSFNET and ARPA2 topologies. The results are shown in Figs 13 and 14. Figure 13 shows the burst loss probabilities for each hop for both the conventional and the proposed method at node 5 with output link 8 in the NSFNET topology. For the conventional method, as shown in Fig. 13(a), the burst loss probability of one hop is smaller than those of two-hops and three-hops. This is because the amount of traffic on the last-hop links for two-hops and three-hops is high. Therefore, the conventional hop-based burst-cluster transmission can not improve fairness. However, as shown in Fig. 13(b), the proposed method can improve the fairness so that the burst loss probabilities of one-hop, two-hops and three-hops are almost the same. Similarly, Fig. 14 corresponds to the results obtained in ARPA2 at node 5 with output link 13. The burst loss probabilities for each hop for the conventional method are shown in Fig. 14(a) and those for the proposed method are illustrated in Fig. 14(b). Note that there is no burst transmission of six-hop and seven-hops. This is because, the maximum number of hops for a shortest path with starting from node 5 along output link 13 is five. From these two figures, the discrepancies between the burst loss probabilities are bigger in the conventional method than those of the proposed method. This implies that the proposed method is more effective in improving fairness.
Conclusion
In this paper, adaptive burst reordering has been proposed in order to improve the fairness for each node regardless of the amount of traffic on each link. The performance of the proposed method has been evaluated by simulation for tandem networks, NSFNET and ARPA2. From the numerical examples, it is shown that the burst loss probabilities become almost the same for each source node by using the proposed method. In addition, the fairness index for the proposed method is closer to one compared to the conventional hop-based burst-cluster transmission. Although the proposed method increases slightly the overall burst loss probability, each source node can decrease the largest burst loss probability among the ones for all destination nodes further than the conventional hop-based burst-cluster transmission. Therefore, wavelengths are used more fairly among all pairs of source and destination nodes.
