Abstract

The resource contention problem is critical in Just-Enough-Time (JET) based optical burst switching (OBS) networks. Although deflection routing (DR) reduces the contention probability in some degree, it does not give much improvement under heavy traffic load. This paper analyzed the inducement causing contention in OBS networks, and proposed Resource Information Sharing Enhancement (RISE) scheme. Theoretical analysis shows that this scheme achieves shorter length of the detour path than normal DR. We simulated this scheme on both full mesh network and practical 14-node NSFNET. The simulation results show that it gives at best 2 orders magnitude improvement in reducing the burst contention probability over its previous routing approaches.

© 2005 Optical Society of America

1. Introduction

1.1 JET based OBS networks

The bursty nature of the Internet introduces the evolution of the optical backbone network from circuit switching to optical packet switching. Constrained by immature optical information storage and optical signal processing technology, optical burst switching (OBS) attracts more and more attention as a transitional application in WDM optical networks. The idea of JET based OBS [1, 2] is to aggregate a set of IP packets into a burst at the edge router and transmit it through a time-specified channel in the optical domain. Before the burst, a control packet will be sent offset time length ahead to reserve resource along specified route, configuring the cross-connect when the burst arrives at each node. To achieve low end-to-end latency of transmission, no acknowledgment is expected during connection setup in JET based OBS networks. Different from circuit switching, as the lifetime of a connection is rather short (for instance, at the magnitude of 10 milliseconds), there is no resource reservation information flooding in the network, like link state advertisement (LSA) in automatically switched optical networks (ASON) [3]. Two factors result in the resource contention problem, unacknowledged connection setup and fix routing for no dynamic resource information exchange. When a burst arrives at a node without enough resources at the specified output port, the burst will be dropped (usually the source node will be informed to retransmit it). Under heavy traffic load, frequent retransmissions caused by contentions will degrade the network performance, increasing the average end-to-end delay and the total traffic load.

1.2 Deflection routing

To resolve the resource contention problem, some ideas based on deflection routing (DR) have been proposed to reroute the burst from the congested node to its destination [410]. DR has its advantage at relatively light network traffic load, when a detour path is easily to be found and thus fewer retransmissions are needed. However, its disadvantages are obvious as follows. First, when the burst is deflected to a detour, the number of total hops may increase notably in some topology, and the offset time will not be enough for the control packet to setup the connection. Second, as each node has no knowledge of the resource information at other nodes, the deflection is blindfold. Therefore, DR degrades the network performance in heavy traffic load conditions [9, 10].

1.3 Our contribution

In this paper, we propose a new scheme called Reservation Information Sharing Enhancement (RISE) to resolve the resource contention problem. RISE consists of information exchanging mechanism and routing selection algorithm for contention avoidance. In this scheme, we designed partial spread of the reservation information, which can be used to predetermine if an incoming burst will be blocked at its next-hop node. We simulated RISE scheme on 3×4 mesh networks and 14-node NSFNET. The results show that RISE gives at best 2 orders magnitude improvement in reducing the contention probability.

The rest of the paper is organized as follows. Section 2 discusses the issues in the current resolutions for resource contention in JET based OBS network. Section 3 describes our RISE scheme for resolving resource contention. Section 4 evaluates the performances of our scheme and Section 5 concludes the paper.

2. Related work

2.1 JET reservation protocol

Myungsik Yoo et al. in [2] designed the reservation protocol JET for OBS, where the control packet is released from the edge node offset time ahead of the burst. Along the specified shortest path, control packet reserves the wavelength resources and configure the optical cross-connect at each node to direct the burst to its destination. When the resource is not available at one node when the burst arrives, the resource contention occurs. In JET protocol, postponing technology is considered for contention resolution using Fiber Delay Line (FDL) [6]. If the destined output port of burst A has been occupied by burst B, FDL can temporarily buffer burst A in the optical domain until a reservation can be made on the link that is in contention. But FDL is expensive and can give a delay within the measure of µs, which can not totally solve the contention problem.

2.2 Issues analysis of DR

As no mature optical storage can totally resolve the contention problem, DR has been reported to be a viable method for resolving contention in relatively low to medium traffic load [410]. In DR, the congested node can reroute the burst to another unoccupied output port, trying to find a detour path. The main issue of DR is that it only works well under the condition of low to medium traffic load and the high connection degree of network. Because each node has no knowledge of the current resource information at its next hop, the deflection has to randomly select an unoccupied output port. Considering from routing aspects, the detour path will have more hops than the original shortest path. Take the 14-node NSFNET for instance as shown in Fig. 1, the shortest path between the Source and Dest(ination) has 2 hops, namely Source-A-Dest. But if the link from A to Destination is congested when the burst comes in, DR will reroute the burst to the potential detour path Source-A-B-C-D-E-Dest, with total 6 hops. While if the burst is just simply dropped and retransmitted from the source node through the second shortest path Source-F-G-E-Dest, the total number of hops is only 4. In case of heavy traffic load, more hops will notably increase the burst contention probability and degrade the performance of the OBS network. If we define the network connection degree Dc as the average number of links per node: Dc =Nl /Nn , where Nl is the total number of links and Nn is the total number of nodes in the network, we can see that with Dc decreasing, the number of hops of the second shortest path will increase, and the contention probability reduction by DR will be decreased.

 

Fig. 1. Performance degradation of DR in practical topology

Download Full Size | PPT Slide | PDF

3. Reservation information sharing enhancement

The essence distinguishes OBS from circuit switching is the capability to handle the real-time bursty traffic. This requires unacknowledged connection setup and no resource information flooding through the network, which ultimately results in the resource contention problem. If a control packet can be transmitted to its neighbor and processed in much shorter time than burst transmission duration, it is effective to avoid contention by sharing reservation information between neighbors.

Shared resource information can be used to avoid sending bursts to congested neighbors, which reduces burst contention probability. Based on this idea, we have designed RISE to resolve contention. In this scheme, when a control packet is issued to reserve resource and setup an optical channel, each node along the path will send a corresponding message to inform that to its neighbors. Thus, all the nodes maintain a resource information database of their neighbors, and use it to predict the right route of their outgoing bursts. In the next part, the information exchanging implementation will be introduced, and the congestion precognition mechanism will be presented. At last, the improvement of RISE will be proved and the scalability problem of RISE will be discussed.

3.1 Information sharing between neighboring nodes

In the circuit switching network, resource reservation information flooding in the whole network is a necessary mechanism. All routing and wavelength assignment (RWA) algorithms are based on the current link state of the network. However, in OBS network, as the lifetime of an optical connection is rather short, there is no time for flooding the resource reservation information to the whole network. That is to say, when the information is received by a remote node in the network, the resource reserved may already be released. So whole-network flooding the reservation information is meaningless. But analysis shows that, for relatively long bursts, there is still enough time to share the information between neighboring nodes. In RISE, the information exchanging process is simpler than legacy circuit switching network, as no complicated LSA flooding is needed. We can use the same mechanism as circuit switching and configure the time-to-live (TTL) to be one hop.

There are still differences in information exchange process between OBS and circuit switching. In circuit switching, both the setup and teardown process of a connection are explicit with some certain signals. While in JET based OBS network, the teardown of a connection is generally implicit by estimating the time of the burst transmission duration [11]. Moreover, the basic parameters such as starting and ending transmission time are necessary for checking the admission control of a burst. So a timer is required to manipulate the database of the resource information from neighbors. When an information packet is received, the peer delay of the packet and processing time must be considered before inserting the reservation item into the database. When a burst is transmitted completely at its neighbor, the corresponding reservation item in the local database will be deleted automatically by the timer.

3.2 Congestion precognition mechanism

Information sharing between neighboring nodes makes it possible to check the resource availability of the next hop along the route. In this part, we present the congestion precognition mechanism to avoid burst contention. This mechanism consists of the admission control function and the dynamic routing algorithm.

The admission control function determines whether a burst has enough resource to be transmitted through certain output port. The input parameters of this function include the OFFSET time between the control packet and its burst, and the transmission DURATION of the burst. The details of this function are listed as below.

The essence of the function is to determine whether the current burst overlaps with former burst. The inequation offset[j] >OFFSET+DURATION indicates that the current burst will be transmitted completely before the arrival of the former burst in the jth Reserve_item; while OFFSET>offset[j]+duration[j] indicates the opposite. Otherwise, the bursts will overlap. For sake of reliability, we can add a small gap µ between two consecutive bursts to avoid bursts overlapping because of inaccuracy of the timer. And if FDL can be applied in the network, the longest delay interval DFDL should also be considered. Thus, the determination condition can be written as: (offset[j]+DFDL >OFFSET+DURATION+µ) and (OFFSET+DFDL >offset[j]+duration[j]+µ).

Definitions:

Nw : the number of wavelengths multiplexed in the output fiber port; Reserve_seq[w]: the resource reservation sequence of the wavelength w; Reserve_item i: the ith reservation item in the Reserve_seq; offset[j]: the offset time of the jth Reserve_item; duration[j]: the burst duration of the jth Reserve_item.

Function:

ADMISSION_CONTROL (time OFFSET, time DURATION)

{

FOR (wavelength w=0 to Nw -1)

{

IF (Reserve_seq[w] is NULL) Return TRUE;

ELSE FOR (each Reserve_item j in Reserve_seq[w])

{

if ((offset[j] > OFFSET+DURATION) OR

(OFFSET > offset[j]+duration[j]))

Return TRUE;

}

}

Return FALSE;

}

The dynamic routing algorithm finds the best available route according to the current resource available at local and neighboring nodes. If one selected best route in the process can not pass the admission control check at either the local node or the next hop node, the corresponding output port will be disabled to form a new topology, where the next best route will be found and checked. The same process is repeated until an appropriate route is found, or no route is found and the burst is dropped. The flowchart of the algorithm is shown in Fig. 2.

 

Fig. 2. Flowchart for RISE scheme

Download Full Size | PPT Slide | PDF

3.3 Improvement analysis of RISE

In this section, the improvement of RISE will be proved. In case of congestion, the burst will be redirected to a detour path. The longer detour path will result in larger contention probability in the topology. The length of detour path in RISE is no more than DR is proved as below (Fig. 3).

Given each source-destination pair (S,D) in topology G(E,V), where E is the link set and S,DV is the node set, the route set R(S,D)G contains all the routes from node S to D within topology G. The shortest path SP : (S-A-B-D) ∊ R(S,D)G can be calculated with Dijkstra’s algorithm. Using DR scheme, if the link l between node A and B is congested, the burst will be deflected to a detour path. Given =G(Ē,V), where Ē=E-{l}, the detour path can be calculated as the shortest path from A to D in , namely SP 1̄ : (A-A 2-D) ∊ R G ̄(A,D). Because the link S-A is also within , the final route between (S,D) pair is

(SAA2D)R(S,D)G¯

If using our RISE scheme, node S can foresee the congestion in the next hop l, and find the alternate shortest path SP̄ : (S-A 1̄D) between (S,D) in topology , or the shortest route in RG ̄(S,D). From formula (*), we know that (S-A-A 2-D) is within the route set RG ̄(S,D). So the detour in RISE SP : (S-A 1-D) has number of hops is less than or equals to that of the detour in DR(S-A-A 2-D).

 

Fig. 3. Length of detour path comparison between RISE and DR

Download Full Size | PPT Slide | PDF

3.4 Scalability consideration

In the normal connection setup process in OBS network, the control packet will be handed on along the specified route and processed. In our new scheme, after each intermediate node reserves resources and configures the optical cross-connect, it should also share this information with its neighbors excluding the upstream and downstream node along the route. The information transmission adds the total traffic load of the signaling network. In this part, the scalability problem is considered for the incremental signaling traffic versus network scale.

Given a connection in the OBS network with L intermediate nodes, and Ni the number of neighbors belonging to the i th intermediate node, the incremental signal traffic can be formulated as Tinc=i=1L(Ni2). As we defined earlier, the network connection degree Dc =Nl /Nn can be treated as the average number of neighbors of each node Ni¯ in the network. So we get average incremental traffic Tinc¯=L¯¯(Dc2), where is the average length of connections. In mesh networks, we can approximately educe the relation between and the network scale N, namely =O(N 1/2). Dc is a constant parameter reflecting the network property, so we get Tinc¯=O(N12), which denotes that the average incremental signaling traffic per connection is proportional with N 1/2. Under the same burst traffic load, the total connection request is also proportional with N1/2. So the average incremental signaling traffic caused by RISE per link is proportional with (N 1/2×N 1/2)/N=1. Above analysis shows that, in RISE, the average incremental traffic load per link will not increase with the network scale.

4. Performance evaluation

To evaluate the performance of RISE scheme, we develop a discrete-event simulation tool based on the NS-2 platform [12]. We implement the contention resolution models, including normal fixed routing protocol, DR scheme and RISE. We focus on the burst contention probability parameter in the three models. To compare the performances in arbitrary topologies, the simulation is conducted on both the 3×4 mesh network and the 14-node NSFNET. Each link in the network is supposed bidirectional and the number of wavelengths on each fibre is set to be eight. Wavelength conversion capability is premised available in the network. The bursts arrival rate at each node according to a Poisson process, and the burst duration is negative exponentially distributed with the mean value 10 milliseconds. Each node has the same probability as others to be selected as the source or destination of a burst. The signalling propagation delay and processing time is set to be around 1 millisecond. The switch setup time is presumed as 1 millisecond.

 

Fig. 4. Simulation on 3×4 full mesh network topology

Download Full Size | PPT Slide | PDF

In the first series of tests, we compare the performance of above three models in 3×4 mesh network as shown in Fig. 4 (a). The burst contention probability comparison is shown in Fig. 4 (b). The traffic load here refers to the average load on each node of the network. From this figure we can see that when the traffic load is relatively light, for instance below 6 Erlangs, DR has as about half of the contention probability as normal OBS protocol. On the contrary, if the traffic load is heavier than about 9 Erlangs, DR degrades the performance of the network with higher contention probability. This proves that the disadvantage of DR in heavy traffic load. It is clear that RISE has much lower contention probability than the previous two schemes. RISE achieves about two orders magnitude lower contention probability in case of light traffic load and about one order lower in case of heavy traffic load. When the traffic load reaches 12 Erlangs, neither DR nor RISE could enhancement. However, in such case the contention probability has been in the measure of one tenth, which is too high and not common in practical case.

Although 3×4 full mesh network can give an example to evaluate the performance, it has larger network connection degree Dc than practical network. So we also simulate the three models on 14-node NSFNET as shown in Fig. 1. Because of less Dc in 14-node NSFNET, the second shortest path becomes longer and the performance improvement effect by routing protocol is weakened. The simulation result is shown in Fig. 5, where DR can not enhance the network contention performance. However, our new scheme still works well form light to relatively heavy traffic load with certain improvement. Also, RISE does not work under very high loads (for instance, when contention probability is over 0.1).

 

Fig. 5. Burst contention probability comparison in 14-node NSFNET

Download Full Size | PPT Slide | PDF

5. Conclusion

In this paper, we present a new scheme called Reservation Information Sharing Enhancement (RISE) to solve the resource contention problem in JET based OBS networks. As unacknowledged connection setup and no information sharing in the network, resource contention is a critical problem in designing OBS protocol. We surveyed the previous approaches for contention resolution. DR performs well in light to medium traffic load, but it can not deal with heavy traffic load network. From analysis we find that it is effective to share resources information between neighbouring nodes for advance routing decision. We present the RISE scheme and analyze its improvement and scalability. Our simulation results show that RISE gives at best 2 orders magnitude improvement in reducing the contention probability, compared with the previous routing schemes for both full mesh network and practical 14-node NSFNET.

Acknowledgments

This work is supported by Tsinghua & Bell Labs Research China Joint Lab, NNSF of China (60132020, 90104003), and 863 Program (2003 AA 122220).

References and Links

1. C. Qiao and M. Yoo, “Optical burst switching (OBS)-a new paradigm for an optical Internet,” J. High Speed Networks , 8, 69–84 (1999).

2. Myungsik Yoo et al., “Just-Enough-Time (JET): A High Speed Protocol for Bursty Traffic in Optical Networks,” in proceeding of IEEE/LEOS Conf. on Technologies for a Global Information Infrastructure (1997), pp. 26–27.

3. ITU-T Rec. G.8080/Y.1304, “Architecture for the Automatically Switched Optical Network,” (Geneva, 2001).

4. X. Wang et al., “A Deflection Routing Protocol for Optical Bursts in WDM Networks,” in proceeding of Fifth Optoelectronics and Communications Conference (Makuhari, Japan, 2000), pp. 94–95.

5. X. Wang et al., “Burst optical deflection routing protocol for wavelength routing WDM networks,” Opt. Net. Mag , 3, 12–18 (2002).

6. M. Yoo et al., “A comparative study of contention resolution policies in optical burst switched WDM networks,” in proceeding of Conf. on Terabit Optical Networking (2000), 4213, pp. 124–135.

7. S. Kim et al., “Contention resolution for optical burst switching networks using alternative routing,” in proceeding of IEEE Int. Conf. Communications (New York, 2002), pp. 2679–2681.

8. Ching-Fang Hsu et al., “On the deflection routing in QoS supported optical burst-switched networks,” in proceeding of ICC’02 (2002), pp. 2786–2790.

9. Yang Chen et al., “Performance Analysis of Optical Burst Switched Node with Deflection Routing,” in proceeding of ICC’03 (Anchorage, USA, 2003), pp. 1355–1359.

10. S. Lee et al., “Contention-Based Limited Deflection Routing in OBS Networks,” in proceeding of the IEEE Globecom (San Francisco, 2003), pp. 2633–2637.

11. C. Qiao et al., “Choices, features and issues in optical burst switching,” Opt. Net. Mag , 1, 36–44 (2000).

12. Network Simulator, NS-2, available at http://www.isi.edu/nsnam/ns.

References

  • View by:
  • |

  1. C. Qiao and M. Yoo, �??Optical burst switching (OBS) - a new paradigm for an optical Internet,�?? J. High Speed Networks, 8, 69-84 (1999).
  2. Myungsik Yoo et al., �??Just-Enough-Time (JET): A High Speed Protocol for Bursty Traffic in Optical Networks,�?? in proceeding of IEEE/LEOS Conf. on Technologies for a Global Information Infrastructure (1997), pp. 26-27.
  3. ITU-T Rec. G.8080/Y.1304, �??Architecture for the Automatically Switched Optical Network,�?? (Geneva, 2001).
  4. X. Wang et al., �??A Deflection Routing Protocol for Optical Bursts in WDM Networks,�?? in proceeding of Fifth Optoelectronics and Communications Conference (Makuhari, Japan, 2000), pp. 94-95.
  5. X. Wang et al., �??Burst optical deflection routing protocol for wavelength routing WDM networks,�?? Opt. Net. Mag., 3, 12-18 (2002).
  6. M. Yoo et al., �??A comparative study of contention resolution policies in optical burst switched WDM networks,�?? in proceeding of Conf. on Terabit Optical Networking (2000), 4213, pp. 124-135.
  7. S. Kim et al., �??Contention resolution for optical burst switching networks using alternative routing,�?? in proceeding of IEEE Int. Conf. Communications (New York, 2002), pp. 2679-2681.
  8. Ching-Fang Hsu et al., �??On the deflection routing in QoS supported optical burst-switched networks,�?? in proceeding of ICC�??02 (2002), pp. 2786�??2790.
  9. Yang Chen et al., �??Performance Analysis of Optical Burst Switched Node with Deflection Routing,�?? in proceeding of ICC'03 (Anchorage, USA, 2003), pp. 1355-1359.
  10. S. Lee et al., �??Contention-Based Limited Deflection Routing in OBS Networks,�?? in proceeding of the IEEE Globecom (San Francisco, 2003), pp. 2633-2637.
  11. C. Qiao et al., �??Choices, features and issues in optical burst switching,�?? Opt. Net. Mag, 1, 36-44 (2000).
  12. Network Simulator, NS-2, available at <a href="http://www.isi.edu/nsnam/ns/">http://www.isi.edu/nsnam/ns/</a>

Conf. Terabit Optical Networking 2000 (1)

M. Yoo et al., �??A comparative study of contention resolution policies in optical burst switched WDM networks,�?? in proceeding of Conf. on Terabit Optical Networking (2000), 4213, pp. 124-135.

ICC 2002 (1)

Ching-Fang Hsu et al., �??On the deflection routing in QoS supported optical burst-switched networks,�?? in proceeding of ICC�??02 (2002), pp. 2786�??2790.

ICC 2003 (1)

Yang Chen et al., �??Performance Analysis of Optical Burst Switched Node with Deflection Routing,�?? in proceeding of ICC'03 (Anchorage, USA, 2003), pp. 1355-1359.

IEEE Globecom 2003 (1)

S. Lee et al., �??Contention-Based Limited Deflection Routing in OBS Networks,�?? in proceeding of the IEEE Globecom (San Francisco, 2003), pp. 2633-2637.

IEEE Intl. Conf. Communications 2002 (1)

S. Kim et al., �??Contention resolution for optical burst switching networks using alternative routing,�?? in proceeding of IEEE Int. Conf. Communications (New York, 2002), pp. 2679-2681.

IEEE/LEOS Tech. Global Info. Infra. 1997 (1)

Myungsik Yoo et al., �??Just-Enough-Time (JET): A High Speed Protocol for Bursty Traffic in Optical Networks,�?? in proceeding of IEEE/LEOS Conf. on Technologies for a Global Information Infrastructure (1997), pp. 26-27.

J. High Speed Networks (1)

C. Qiao and M. Yoo, �??Optical burst switching (OBS) - a new paradigm for an optical Internet,�?? J. High Speed Networks, 8, 69-84 (1999).

Opt. Net. Mag. (2)

C. Qiao et al., �??Choices, features and issues in optical burst switching,�?? Opt. Net. Mag, 1, 36-44 (2000).

X. Wang et al., �??Burst optical deflection routing protocol for wavelength routing WDM networks,�?? Opt. Net. Mag., 3, 12-18 (2002).

Optoelec. Commun. Conf. 2000 (1)

X. Wang et al., �??A Deflection Routing Protocol for Optical Bursts in WDM Networks,�?? in proceeding of Fifth Optoelectronics and Communications Conference (Makuhari, Japan, 2000), pp. 94-95.

Other (2)

ITU-T Rec. G.8080/Y.1304, �??Architecture for the Automatically Switched Optical Network,�?? (Geneva, 2001).

Network Simulator, NS-2, available at <a href="http://www.isi.edu/nsnam/ns/">http://www.isi.edu/nsnam/ns/</a>

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (5)

Fig. 1.
Fig. 1.

Performance degradation of DR in practical topology

Fig. 2.
Fig. 2.

Flowchart for RISE scheme

Fig. 3.
Fig. 3.

Length of detour path comparison between RISE and DR

Fig. 4.
Fig. 4.

Simulation on 3×4 full mesh network topology

Fig. 5.
Fig. 5.

Burst contention probability comparison in 14-node NSFNET

Equations (1)

Equations on this page are rendered with MathJax. Learn more.

(SA A 2 D) R (S,D) G ¯

Metrics