Advanced
Near-Optimal Algorithm for Group Scheduling in OBS Networks
Near-Optimal Algorithm for Group Scheduling in OBS Networks
ETRI Journal. 2015. Oct, 37(5): 888-897
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : January 31, 2015
  • Accepted : August 21, 2015
  • Published : October 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Vo Viet Minh Nhat
Nguyen Hong Quoc
Nguyen Hoang Son

Abstract
Group scheduling is an operation whereby control packets arriving in a time slot schedule their bursts simultaneously. Normally, those bursts that are of the same wavelength are scheduled on the same channel. In cases where the support of full wavelength converters is available, such scheduling can be performed on multiple channels for those bursts that are of an arbitrary wavelength. This paper presents a new algorithm for group scheduling on multiple channels. In our approach, to reach a near-optimal schedule, a maximum-weight clique needs to be determined; thus, we propose an additional algorithm for this purpose. Analysis and simulation results indicate that an optimal schedule is almost attainable, while the complexity of computation and that of implementation are reduced.
Keywords
I. Introduction
Optical burst switching (OBS) is considered as an appropriate alternative model for optical packet switching, where the current optical technology has not really matured enough to produce optical buffers and optical packet switching fabrics with nanosecond switching speed [1] . A typical feature of OBS networks is the burst control packet (BCP), which is a packet that is transmitted separately (in terms of both space and time) from its associated data burst. This means that a BCP is sent on a control channel that is separate to the data channel transporting its associated data burst; an offset time is created, since the BCP is sent ahead of its associated data burst. This offset time must be predetermined sufficiently so that the BCP can reserve necessary resources and configure switches just before its associated data burst arrives at each node on the path from source to destination.
The action of resource reservation of a BCP at an OBS core node normally is a part of scheduling operation. There are two approaches for scheduling — online scheduling and group (offline) scheduling [2] [3] . In the case of online scheduling, a BCP arriving at an OBS core node calls a scheduling algorithm (for example, LAUC [4] or LAUC-VF [5] ) to reserve immediately the resources for its following burst. In the case of group scheduling, the BCPs arriving in a timeslot (or a time window) schedule their bursts simultaneously via one of the following algorithms: OBS-GS [4] , MWIS-OS [5] , LGS [6] , heuristics [7] , GreedyOPT [8] , BATCHOPT [8] , or LGS-MC [9] . As proved in [7] [9] and illustrated in Fig. 1 , group scheduling is more effective than online scheduling; however, group scheduling requires more updating operations. Therefore, its complexity is higher than that of online scheduling.
PPT Slide
Lager Image
Comparison based on packet loss probability among LAUC, LAUC-VF, and heuristics with loads from 0.1 to 0.9 Erlangs.
The first three of the aforementioned algorithms, OBS-GS, MWIS-OS and LGS, are for group scheduling on a single channel if wavelength conversion is unavailable on OBS core nodes and the arriving bursts in a time slot are assumed to have the same wavelength; while, the remaining algorithms perform scheduling on multiple channels with the support of full wavelength converters. In this paper, we focus on group scheduling on multiple channels.
Our main contribution is to propose a near-optimal algorithm for group scheduling on multiple channels. Our algorithm is based on finding a maximum-weight clique (MWC), for which we propose a further new approach of finding such a clique on an interval graph that represents the scheduling possibilities of arriving bursts on data channels. Analysis and simulation results indicate that a near-optimal schedule with a minimal packet loss probability is achievable, while the complexity of computation and that of implementation are reduced.
The remainder of this paper is organized as follows. Section II presents some notations of graphs and related components. Section III summarizes previous proposals on group scheduling and their limitations. Section IV presents our algorithms for group scheduling based on finding an MWC. Analysis and simulation results are presented in Section V, and conclusions are given in Section VI.
II. Notations
Let G = ( V , E ) be a graph, where V represents the set of vertices of G and E is the set of edges. For a vertex, u ( u V ), a positive weight, wu , is associated with it, and its set of adjacent vertices is defined as adj( u ) = { v V | ( u , v ) ∈ E }.
A clique in G is a set of vertices, C ( C V ), such that ∀ u , v C , ( u , v ) ∈ E . A maximal clique is a clique that is not a subset of any other clique. A maximum clique is a maximal clique that has maximum cardinality or weight. This paper focuses on the weighted maximum clique problem.
A graph, G , is defined to be an interval graph if there exists a one-one correspondence between its vertices and a family of intervals; any two vertices in G are deemed to be adjacent if their corresponding intervals overlap. This paper considers the opposite case in which two vertices in G are deemed to be adjacent if their corresponding intervals do not overlap.
III. Related Works
The problem of group scheduling, which is related to bursts arriving in a time slot on different data channels, can be formulated as a job scheduling problem, and an interval graph can be constructed to find an optimal scheduling solution [10] . As with job scheduling, the group scheduling of bursts arriving in a time slot is associated with the problem of scheduling with non-identical machines (S-NIM), because there may exist a burst that cannot be scheduled on a certain data channel if its start time is before the latest available unscheduled time (LAUT) of the channel in question. Because of the NP-hard complexity of S-NIM [10] , a possible solution is to use heuristic approaches [7] or to transform the problem from S-NIM to scheduling with identical machines (S-IM) [10] .
The heuristic approaches proposed in [7] consist of Smallest Start-time First (SSF), Largest Interval First (LIF), Smallest-Last Vertex (SLV), and Maximal Cliques First (MCF). The idea expressed in [7] is to first rearrange the order of arriving bursts and then to call LAUC-VF to schedule them.
SSF arranges the arriving bursts based on their start times. This approach is simple, but it does not facilitate the search for an optimal schedule [8] . LIF, an improvement over SSF, sorts the bursts according to their weight (length) and then selects the largest as the first to be scheduled. This approach may achieve a local optimal schedule on each individual channel but not a maximal weight of scheduled bursts over all channels.
In the case of SLV, an interval graph, G , is firstly constructed and any arriving bursts are then arranged in descending order of the degrees of the corresponding vertices. SLV believes that the burst corresponding to the vertex of largest degree is the longest as it overlaps more bursts than any other burst. However, this is not always true (as the example in Fig. 2 shows); so, the scheduling solution of SLV is no better than that for LIF.
PPT Slide
Lager Image
Example of arriving bursts, in which burst b1 overlaps more bursts (b2, b3, b4, and b5) than any other burst; however, it is not the longest (burst b5 is in fact longest): (a) status of arriving bursts and (b) corresponding interval graph.
Similarly, MCF firstly builds an interval graph, G , and then tries to color G by m colors (equal to the number of available data channels). To do this, MCF finds all maximal cliques, the sizes of which are greater than m . With a maximal clique having the earliest of start times, MCF respectively discards those vertices that have the earliest end times until the size of a maximal clique is equal to or smaller than m . This process is repeated until no maximal clique has a size that is greater than m . The efficiency of MCF is mainly determined by the way it discards those vertices that have the earliest end times in a maximal clique. However, such vertices do not correspond to the shortest bursts; thus, an optimal schedule, then, will not be achieved.
Different from heuristic algorithms, the approach common to GreedyOPT and BATCHOPT [8] is one that aims to transform S-NIM into S-IM. Instead of trying to allocate optimally the arriving bursts on the available bandwidths between the scheduled bursts, GreedyOPT and BATCHOPT remove all the scheduled bursts and reschedule them simultaneously with the arriving bursts.
In the case of GreedyOPT, group scheduling is based on a principle of greed, without regard for maximizing the total weight of scheduled bursts. If a burst cannot find a suitable resource on any of the available data channels, then GreedyOPT tries to replace it with the scheduled burst that has the latest end time. This action is designed to allow bursts the opportunity to seek suitable resources. However, a major drawback of GreedyOPT is that there is no mechanism to ensure that all removed bursts are rescheduled. Table 1 shows our simulation results, in which the rates of successful rescheduling of GreedyOPT never achieve 100%; noting that if a removed burst is rescheduled without a change in its placement in the schedule, then it is not considered as a rescheduling because no re-signaling is required.
Rates of successful rescheduling of GreedyOPT with loads from 0.1 to 0.9 Erlangs.
Load Removed bursts Rescheduled bursts Rate (%) of successful rescheduling
0.1 319 276 86.52
0.2 392 327 83.42
0.3 560 481 85.89
0.4 620 537 86.61
0.5 739 646 87.42
0.6 797 692 86.83
0.7 929 803 86.44
0.8 1,072 805 75.09
0.9 1,286 904 70.30
In the case of BATCHOPT, an interval graph that represents both the arriving bursts and the scheduled bursts is firstly built. Next, the algorithm finds all maximal cliques of the graph and arranges them in ascending order of their start times. A flow graph of the arranged maximal cliques is then set in which each arc is characterized by the parameters of cost, throughput capacity, and weight (length). Finally, BATCHOPT finds the flow with minimum cost and eliminates the corresponding arcs.
Clearly, this approach helps BATCHOPT achieve an optimal solution with the remaining maximal flow. Moreover, by assigning an infinite weight value to the removed bursts, BATCHOPT ensures to reschedule all of them. However, the main drawbacks of BATCHOP as well as of GreedyOPT are as follows: system complexity is increased due to the rescheduling of previously scheduled bursts, more control packets are generated to notify the changes of scheduling status, and updates in the signaling protocol are required. The complexity of BATCHOPT is proven to be O( N 2 log( N )) [8] , where N is the total number of arriving and removed bursts.
Another algorithm for group scheduling, called LGS-MC [9] , has a near-optimal scheduling result. With the hope of achieving an optimal schedule on all data channels, LGS-MC tries to optimize group scheduling on each channel. The scheduling optimization on each channel is performed by LGS [6] . Although the scheduling result is approximately optimal, the complexity of LGS-MC is less than that of BATCHOPT. As proved in [9] , the complexity of LGS-MC is O( m × n log( n )), where n is the number of arriving bursts ( n < N ) and m is the number of data channels ( m < N ). Another advantage of LGS-MC is that no rescheduling is required; thus, no complexity is added to the system.
Figure 3 shows a comparison among the group scheduling algorithms. The packets in this case refer to blocks of 64 bytes contained in each burst. The following is the detailed description of our proposed algorithms for group scheduling on multiple channels.
PPT Slide
Lager Image
Comparison based on packet loss probability among LIF (best of heuristics), GreedyOPT, LGS-MC, and BATCHOPT with loads from 0.1 to 0.9 Erlangs.
IV. Algorithm of MWC-GS
Consider a set of BCPs, I = { b 1 , b 2 , ... , bn }, arriving in a time slot that schedules their respective bursts on a set of data channels, W = {1, 2, ... , m }. A burst is characterized by a triplet, ( si , ei , wi ), where si represents the start time, ei the end time, and wi the weight (length) of burst bi , respectively. Two bursts, bi and bj , are scheduled on a channel, k , if they are after the LAUT of channel k ( si > LAUT k and sj > LAUT k ) and do not overlap each other ( si ej or sj ei ). Thus, depending on its position compared to the LAUT of data channels and its overlap with other bursts, an arriving burst can have many scheduling possibilities. For visualization, the scheduling possibilities can be modeled in the form of an interval graph.
Let G ( V , E ) be an interval graph, where each vertex
b i k ∈V
presents the scheduling possibility of burst bi on channel k and each edge
( b i k ,  b j h )∈E
corresponds with one of the two following cases: (a) bursts bi and bj can be scheduled on the same channel ( k = h ) without being overlapped or (b) they can be scheduled on two separate channels ( k h ).
With the arriving bursts in Fig. 4(a) , the interval graph representing their scheduling possibilities on data channels is shown in Fig. 5(a) . The problem of finding an optimal scheduling solution (for example, one with a maximal total of lengths) of the arriving bursts on data channels now becomes the problem of finding an MWC, called C max , in G . The subset of bursts I ′ ⊆ I corresponding with the vertices in C max is the optimal schedule. Figure 5(b) shows a case in which a found MWC corresponds with bursts b 1 (which is scheduled on channel 1) and b 3 and b 6 (both of which are scheduled on channel 2 (see Fig. 4(b) ). Note that each vertex
( b i k )
in I ′ contains the full information about which burst is scheduled for which channel; the scheduling simply only distributes the bursts in I ′ on the channels in W in sequence.
PPT Slide
Lager Image
Example of (a) arriving bursts and (b) optimal schedule on two data channels.
PPT Slide
Lager Image
(a) Interval graph representing scheduling possibilities of arriving bursts in Fig. 4(a) and (b) MWC corresponding to optimal schedule in Fig. 4(b).
Our algorithm for MWC-based group scheduling (MWC-GS) includes the following three main steps (functions).
MWC-GS Algorithm. Input: A set of arriving bursts I = {b1, b2, ... , bn}.           A set of data channels W = {1, 2, ... , m}. Output: A set of scheduled bursts I′ ⊆ I. Begin     // Construct an interval graph of scheduling possibilities 1 G = constructGraph (I, W)     // Find a maximum-weight clique of G 2 C = findMWC(G).     // Schedule the bursts corresponding with the vertices in MWC 3 I′ = scheduleBurstsfromMWC(C). End
- 1. Interval Graph of Scheduling Possibilities
A burst bi I is considered to be scheduled on a channel k W if its start time ( si ) is after the LAUT of channel k ( si > LAUT k ). The scheduling possibility is represented by a vertex on the interval graph G with a weight that is the length of burst
b i ( w i k = e i − s i )
. An edge between two vertices shows the possibility in which two bursts are scheduled on two separate channels ( k h ) or on the same channel ( k = h ) without being overlapped ( si > ej or ei > sj ). The function constructGraph( I , W ) is described as follows.
Function constructGraph(I, W). Input: A set of arriving bursts I = {b1, b2, ... , bn}.           A set of data channels W = {1, 2, ... , m}. Output: Graph G(V, E). Begin 1     For each burst bi in I 2       For each channel k in W 3         If si > LAUTk 4           Create a vertex b i k with the weight w i k = e i s i , 5            VV{ b i k }; 6           For each b j h in V and ij 7             If (kh) or ((k = h) and (si > ej or ei > sj)) 8               Create an edge ( b i k ,  b j h ); 9                EE{ ( b i k ,  b j h ) }; 10             End if; 11           End for; 12         End if 13       End for; 14     End for; 15   Return G(V, E); End
The function constructGraph( I , W ) has complexity O( n × m × | V |) or O(| V | 2 ).
- 2. MWC
The popular idea of finding an MWC is based on a comparison of the weights of all found maximal cliques; however, the problem of finding all maximal cliques is difficult. With a regular interval graph, it is possible to find an MWC by using some of the algorithms proposed in [11] ; these algorithms have a complexity of only O( n log( n )). However, the above constructed interval graph of scheduling possibilities has a particular feature; that is, each burst is represented by m vertices that correspond to m intervals with the same start/end time and the same length. Therefore, there is no criterion to choose which of the m intervals is the most suitable if the algorithms in [11] are used. This paper, therefore, proposes a new algorithm to find an MWC with the following lemma.
Lemma . Given an edge, ( u , v ), and a set V cad = adj( u ) ∩ adj( v ), if a set V ′ ⊆ V cad exists to be a clique then V ′ ∪ { u , v } is also a clique.
Proof . According to the definition of a clique given in Section II, all the vertices in a clique are adjacent. So, if V ′ ⊆ adj( u ) ∩ adj( v ) is a clique, then all vertices in V ′ are adjacent and also adjacent to two vertices { u , v }; therefore, V ′ ∪ { u , v } is also a clique.                                      ■
Corollary . Given an edge ( u , v ) and a set V cad = adj( u ) ∩ adj( v ), if a set V ′ ⊆ V cad exists to be a maximal clique, then V ′ ∪ { u , v } is also a maximal clique.
Our proposed algorithm comes from an arbitrary edge, ( u , v ), which is also the original clique C (u, v) = { u , v }, and we calculate its set of adjacent vertices V cad = adj( u ) ∩ adj( v ). First, the algorithm takes a vertex u ′ ∈ V cad and adds it to C (u, v) . After that, the algorithm removes all vertices v ′ ∈ V cad that are not adjacent to u ′. This action ensures that all remaining vertices in V cad are adjacent to all of the vertices in C (u, v) . The process is repeated until V cad = ∅, which signifies that all the adjacent vertices in V cad have been added to C (u, v) . The clique C (u, v) is now maximal. The detailed description of the function findMWC( G ) is as follows.
Function findMWC(G). Input: a Graph G(V, E). Output: the clique CmaxG. Begin 1     For each uV 2         adj(u) ← {vV | (u, v) ∈ E}; 3     End for; 4     For each (u, v) ∈ E 5         L(u, v) ← false; 6     End for; 7     Cmax ← ∅; Wmax ← 0; 8     For each (u, v) ∈ E and L(u, v) = false 9           C(u, v) ← {u, v}; W(u, v)wu + wv; 10          L(u, v) ← true; 11          Vcad ← adj(u) ∩ adj(v); 12          While Vcad ≠ ∅ 13             u′ ← the first element of Vcad; 14             C(u, v)C(u, v) ∪ {u′}; W(u, v)W(u, v) + wu′; 15             L(u′, u) ← true; L(u′, v) ← true; 16             VcadVcad\{u′}; 17             For each v′ ∈ Vcad 18                 If (u′, v′) ∈ E 19                     L(u′, v′) ← true; 20                 Else 21                     VcadVcad\{v′}; 22                 End if; 23             End for; 24           End while; 25        If Wmax < W(u, v) 26           CmaxC(u, v), WmaxW(u, v); 27           End if; 28      End for; 29    For each uV and adj(u) = ∅ 30        If Wu > Wmax 31           Cmax ← {u}; WmaxWu; 32        End if; 33    End for; 34    Return Cmax; End
The complexity of the function findMWC( G ) depends on the following four steps:
  • 1) Find the set of adjacent vertices of all vertices inG(lines 1–3) that have a complexity of O(|V|2).
  • 2) Initiate the label for all edges inG(lines 4–6) that have a complexity of O(|E|).
  • 3) Find all maximal cliques inG(lines 8–28) that have a complexity of O(|E| × |V| log|V|).
  • 4) CompareCmaxwith the weight of all independent vertices (lines 29–33) that have a complexity of O(|V|).
Then, the final complexity of function findMWC( G ) is O(| E | × | V | log| V |).
Note that each edge ( u , v ) of G is attached a label, L (u,v) . By setting L (u,v) = true for each validated edge, the number of available edges for constructing the maximal cliques hereafter is much less. For a graph G with | V | vertices, the total number of maximal cliques of G , in which each maximal clique contains at least one edge, is at most | V |/2. Therefore, the code part of finding all maximal cliques in G (lines 8–28) actually has a complexity of O(| V | 2 log| V |).
- 3. Scheduling Bursts Corresponding with Vertices in MWC
Since each vertex
( b i k )
of C max contains the full information on which channel its corresponding burst will be scheduled, the function scheduleBurstsfromMWC( C ) only distributes burst bi on channel k . Therefore, its complexity is O(| V |). In summary, the complexity of MWC-GS is O(| V | 2 log| V |).
- 4. Extension of MWC-GS with Void Filling
In the MWC-GS algorithm, the scheduling is performed without void filling, in which the start time of an arriving burst is compared with the LAUT of data channels. However, in the case with void filling, the idle bandwidth (void), which is generated between the scheduled bursts, is also considered. Namely, the MWC-GS with void filling, called MWC-GS-VF, first tries scheduling an arriving burst on one of the voids. In the unsuccessful case, the condition in line 3 of function constructGraph( I , W ) is considered.
With regards to the arriving bursts in Fig. 6(a) , an interval graph representing the scheduling possibilities with void filling is constructed (see Fig. 7(a) ). An MWC is then found (see Fig. 7(b) ) that corresponds with the optimal schedule featured in Fig. 6(b) .
PPT Slide
Lager Image
Example of (a) arriving bursts and (b) optimal schedule with void filling on Channel 2.
PPT Slide
Lager Image
(a) Interval graph, which represents scheduling possibilities with void filling of arriving bursts in Fig. 6(a), and (b) MWC that corresponds to optimal schedule in Fig. 6(b).
The extension of MWC-GS-VF mainly affects the construction of the interval graph, in which the condition in line 3 of function constructGraph( I , W ) is replaced by ( si > e 1 k and ( si + wi ) < s 2 k ) or ( si > LAUT k ). The functions of findMWC( G ) and scheduleBurstsfromMWC( C ) do not have any changes.
V. Simulation and Analysis
MWC-GS and MWC-GS-VF are implemented in NS2, with the support of the package obs0.9a [12] , on a PC of 2.4 GHz Intel Core 2 CPU, 2G RAM. We compare their efficiency, based on the packet loss probability and the computational time, with that of BATCHOPT. The simulation parameters are as follows: the timeslot is 700 μs; the arrival of bursts is modeled as a Poisson process with loads from 0.1 to 0.9 Erlangs; and the burst length, which is an integer multiple of the block (packet) of 64 bytes, has an exponential distribution.
We consider two cases of simulation networks. The first one is a dumbbell (see Fig. 8 ) that has ten edge nodes ( Ei , i = 0, 1, ... , 9) linked to two core nodes ( C 0 , C 1 ). The links connecting the edge nodes to the two cores have a bandwidth of 10 Gbps; whereas, the single link that connects the two cores has a 30 Gbps bandwidth. All the links include one control and four data channels. We set the bursty traffics between the pair of edges ( Ei , E i+5 ), i = 0, 1, … , 4, to investigate the efficiency of the group scheduling algorithms at C 0 .
PPT Slide
Lager Image
Simulation network of dumbbell.
The second simulation network is an NSFNet (see Fig. 9 ) with 10 Gbps bandwidth links in which each also has one control and four data channels. The distances in kilometers are considered to be the propagation delays (μs). The bursty traffics are set between the pairs of nodes. Without loss of generality, node 9 is chosen to investigate the efficiency of the group scheduling algorithms.
PPT Slide
Lager Image
Simulation network of NSFNet with 14 nodes.
Figures 10 and 11 show that MWC-GS has a packet loss probability approaching that of BATCHOPT, while the efficiency of MWC-GS-VF is equivalent to that of BATCHOPT. The reason for this is that in BATCHOPT all the previous scheduled bursts are removed and rescheduled with the new arriving bursts simultaneously. This approach helps rearrange the position of scheduled bursts more optimally and generate new idle spaces for newly arriving bursts; whereas, both MWC-GS and MWC-GS-VF do not consider scheduled bursts. Namely, MWC-GS only considers the available bandwidth after the LAUT of data channels. With MWC-GS-VF, it firstly attempts to schedule arriving bursts into the voids[0] between the scheduled bursts; if it is unable to do so, then MWC-GS is called instead for scheduling. Therefore, BATCHOPT reaches the minimal packet loss probability, whereas our proposals only obtain near-minimal ones.
PPT Slide
Lager Image
Comparison based on packet loss probability among MWC-GS, MWC-GS-VF, and BATCHOPT with dumbbell network and loads from 0.1 to 0.9 Erlangs.
PPT Slide
Lager Image
Comparison based on packet loss probability among MWC-GS, MWC-GS-VF, and BATCHOPT with NSFNet network and loads from 0.1 to 0.9 Erlangs.
However, in BATCHOPT, if a burst is rescheduled to a new position that differs from the initial scheduled position (that is, on a different wavelength channel), then it is considered as a rescheduling. Then, a BCP must be generated and sent to its downstream nodes to remove the resources that were reserved by the previous BCP. After that, the BCP looks for a new schedule for its burst. This means that more BCPs would be generated to notify the changes of scheduling status, and more updates in the existing signaling protocol would then be required; thus, system complexity is increased. On the contrary, our proposals do not have these drawbacks.
With regards to the computational complexity, as proved in Section IV, MWC-GS (and MWC-GS-VF) has a complexity of O(| V | 2 log| V |), | V | = m × n , where n is the number of arriving bursts and m is the number of data channels. Since m is constant, MWC-GS then has a complexity of O( n 2 log( n )). Therefore, the complexity of MWC-GS is smaller than that of BATCHOPT, O( N 2 log( N )), where N ( N > n ) is the total number of arriving and removed bursts. This is also illustrated in our simulation results in Fig. 12 .
PPT Slide
Lager Image
Comparison based on computational time (ms) among MWC-GS, MWC-GS-VF, and BATCHOPT with loads from 0.1 to 0.9 Erlangs.
To investigate the impact of timeslot size on the efficiency of the scheduling algorithms, we implement timeslot sizes ranging from 600 μs to 1,000 μs. The simulation results show that there is a slight decrease in the packet loss probability (see Fig. 13 ) and an increase in the computational time (see Fig. 14 ) as the timeslot size is increased. This is understandable, because when there are more bursts to be scheduled then there are more burst arrangements and then more opportunities to reduce the lost packets. However, timeslot size cannot be expanded arbitrarily, because it depends on the allowed delay in which a burst transits at each node. Regardless of the timeslot size, MWC-GS and MWC-GS-VF always approach an optimal solution.
PPT Slide
Lager Image
Comparison based on packet loss probability among MWC-GS, MWC-GS-VF, and BATCHOPT with timeslot sizes from 600 μs to 1,000 μs.
PPT Slide
Lager Image
Comparison based on computational time (ms) among MWC-GS, MWC-GS-VF, and BATCHOPT with timeslot sizes from 600 μs to 1,000 μs.
VI. Conclusion
In this paper, near-optimal algorithms for group scheduling on multiple channels have been proposed. Our approach was to formulate the group scheduling in terms of the problem of finding a maximum-weight clique (MWC) from an interval graph. Our proposed algorithms (MWC-GS and MWC-GS-VF) almost reach an optimal solution without rescheduling, as in BATCHOPT. Additionally, we proposed a new method to find such an MWC. The approach has a complexity of O(| V | 2 log| V |), which is equivalent to that of the current best algorithms.
BIO
Corresponding Author vvmnhat@hueuni.edu.vn
Vo Viet Minh Nhat received his MS degree in communication engineering from the Francophone Institute for Computer Science, Hanoi, Vietnam, in 2000 and his PhD degree in cognitive informatics from the University of Quebec, Montreal, Canada, in 2007. His research interests include optical packet/burst-based switching, quality of service, optimization, and traffic engineering.
nhquoc@hueuni.edu.vn
Nguyen Hong Quoc received his MS degree in computer science from the Faculty of Sciences, Hue University, Vietnam, in 2010. His research interests are in the fields of all-optical networks with emphasis on packet/burst-based switching, scheduling, and quality of service.
nhson_dhkh@hueuni.edu.vn
Nguyen Hoang Son received his PhD degree in database theory from the Information Technology Institute, Ho Chi Minh, Vietnam, in 2006. His main research interests include computation and combinatorial problems in database theory; computational complexity theory; and discrete mathematics.
References
Chen Y. , Qiao C. , Yu X. 2004 “Optical Burst Switching: A New Area in Optical Networking Research,” IEEE Netw. 18 (3) 16 - 23
Charcranoon S. “Group-Scheduling for Optical Burst Switched (OBS) Networks,” IEEE Global Telecommun. Conf. Dec. 1–5, 2003 5 2745 - 2749
Zheng H. , Chen C. , Zhao Y. “Optimization Scheduling for Optical Burst Switching Networks with Wavelength Conversion,” Int. Conf. Commun. Technol. Guilin, China Nov. 27–30, 2006 1 - 4
Turner J.S. 1999 “Terabit Burst Switching,” J. High Speed Netw. 8 3 - 16
Xiong Y. , Vandenhoute M. , Cankaya H.C. 2000 “Control Architecture in Optical Burst-Switched WDM Networks,” IEEE J. Sel. Areas Commun. 18 (10) 1838 - 1851    DOI : 10.1109/49.887906
Quoc N.H. , Nhat V.V.M. , Son N.H. “A New Algorithm of Group Scheduling in OBS Core Nodes.” Int. Conf. Adv. Technol. Commun. Ho Chi Minh, Vietnam Oct. 16–18, 2013 592 - 596
Kaheel A. , Alnuweiri H. “Batch Scheduling Algorithms: A Class of Wavelength Schedulers in Optical Burst Switching Networks,” IEEE Int. Conf. Commun. May 16–20, 2005 3 1713 - 1719
Figueiredo G.B. , Xavier E.C. , da Fonseca N.L.S. 2012 “Optimal Algorithms for the Batch Scheduling Problem in OBS Networks,” Comput. Netw. 56 (14) 3274 - 3286    DOI : 10.1016/j.comnet.2012.06.005
Quoc N.H. , Nhat V.V.M. , Son N.H. 2013 “Group Scheduling for Multichannels in OBS Networks,” REV J. Electron. Commun. 3 (3–4) 134 - 137
Arkin E.M. , Silverberg E.B. 1987 “Scheduling Jobs with Fixed Start and End Times,” Discrete Appl. Math. 18 (1) 1 - 8    DOI : 10.1016/0166-218X(87)90037-0
Bertossi A.A. , Gori A. 1988 “Total Domination and Irredundance in Weighted Interval Graphs,” SIAM J. Discrete Math. 1 (3) 317 - 327    DOI : 10.1137/0401032
OBS-ns Simulator, Optical Internet Research Center http://www.wine.icu.ac.kr/obsns/index.php