共查询到20条相似文献,搜索用时 15 毫秒
1.
Xiaowen Chu Bo Li 《Networking, IEEE/ACM Transactions on》2005,13(3):704-715
Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion. 相似文献
2.
Harai H. Murata M. Miyahara H. 《Selected Areas in Communications, IEEE Journal on》1998,16(7):1051-1060
Previous analytic approaches for all-optical networks have only allowed a random wavelength assignment policy in spite of the fact that network performance can be improved by other wavelength assignment policies such as first-fit wavelength assignment. We develop an approximate analytic method to allow flexible wavelength assignment policies by virtue of a layered-graph approach. Our analysis is also applicable to the networks that wavelength conversion is limitedly provided. By comparing with simulation results, we show that our analytic approach has good accuracies when the number of wavelengths is not large. We also show that our analysis is applicable to general network topologies 相似文献
3.
For the purpose of reducing the complexity and cost of optical large-scale cross-connect, wavelengths are grouped into wavebands
or fiber to be switched as a single entity, which is called multi- granularity switching. However, it introduces more complexity
into the routing and wavelength assignment problem. In this paper, we propose a novel graph model for describing the states
of the multi-granularity switching WDM networks. Based on the model, the dynamic routing and wavelength assignment problems
for multi-granularity traffic can be solved jointly, and different on-line wavelength grooming policies can be achieved simultaneously.
By simulation, we compared the performance of our algorithms under different policy and different percent of fibers for fiber
switching. The result proved that our algorithms yield better performance than those deal with the routing and wavelength
assignment separately.
This work was supported in part by NSFC Project No. 90104003, 60272023, 60372025 and National 863 project No. 2005AA122310. 相似文献
4.
Shao Ziyu Yan Dongbin Li Zhengbin Wang Ziyu Xu Anshi 《Photonic Network Communications》2007,13(2):195-205
Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the
optical fiber. Wavelength conversion technology and wavelength converters play an important role in enhancing fiber utilization
and in reducing the overall call blocking probability of the network. In this paper, we develop a new analytical model to
calculate the average blocking probability in multi-fiber link networks using limited-range wavelength conversion. Based on
the results obtained, we conclude that the proposed analytical model is simple and yet can effectively analyze the impact
of wavelength conversion ranges and number of fibers on network performance. Also a new heuristic approach for placement of
wavelength converters to reduce blocking probabilities is explored. Finally, we analyze network performance with the proposed
scheme. It can be observed from numerical simulations that limited-range converters placed at a few nodes can provide almost
the same blocking probability as full range wavelength converters placed at all the nodes. We also show that being equipped
with a multi-fiber per-link has the same effect as being equipped with the capability of limited-range wavelength conversion.
So a multi-fiber per-link network using limited-range wavelength conversion has similar blocking performance as a full wavelength
convertible network. Since a multi-fiber network using limited-range wavelength conversion could use fewer converters than
a single-fiber network using limited range wavelength conversion and because wavelength converters are today more expensive
than fiber equipment, a multi-fiber network in condition with limited-range wavelength conversion is less costly than a single-fiber
network using only limited-range wavelength conversion. Thus, multi-fiber per-link network using limited-range wavelength
conversion is currently a more practical method for all optical WDM networks. Simulation studies carried out on a 14-node
NSFNET, a 10-node CERNET (China Education and Research Network), and a 9-node regular mesh network validate the analysis. 相似文献
5.
We consider routing and wavelength assignment in ring, torus, and tree topologies with the twin objectives of minimizing wavelength usage and maximizing optical bypass. The P-port dynamic traffic assumption is used, which allows each node to send and receive at most P calls. For rings we show that PN/4 wavelengths are necessary and sufficient, and provide a four-hub ring architecture that requires only half of these wavelengths to be locally processed. We extend this approach to develop RWA and bypass algorithms for both tori and trees by embedding virtual rings within these topologies and applying the ring algorithms. For an R×C torus, we embed R+C rings onto the torus and provide an approach to RWA and banding based on solving disjoint RWA/banding problems for each ring. Our RWA algorithm is more wavelength efficient than any currently known algorithm and uses the minimum number of wavelengths for R≥2C. Our subsequent banding algorithm allows half of these wavelengths to bypass all but 4R hub nodes. Finally, we give a RWA for trees that embeds a single virtual ring and uses the ring to obtain a RWA that requires no more than PN/2 total wavelengths; this figure is shown to be optimal for balanced binary trees. A banding algorithm follows that allows half these wavelengths to bypass all non-hub nodes. 相似文献
6.
Narula-Tam A. Lin P.J. Modiano E. 《Selected Areas in Communications, IEEE Journal on》2002,20(1):75-88
Through the use of configurable wavelength-division-multiplexing (WDM) technology including tunable optical transceivers and frequency selective switches, next-generation WDM networks will allow multiple virtual topologies to be dynamically established on a given physical topology. For N node P port networks, we determine the number of wavelengths required to support all possible virtual topologies (PN lightpaths) on a bidirectional ring physical topology. We show that if shortest path routing is used, approximately N wavelengths are needed to map N lightpaths. We then present novel adaptive lightpath routing and wavelength assignment strategies that reduce the wavelength requirements to [(N/2)] working wavelengths per port for protected networks and [(N/3)] wavelengths in each direction per port for unprotected networks. We show that this reduced wavelength requirement is optimal in the sense that it is the minimum required to support the worst case logical topology. Furthermore, we prove that a significant number of logical topologies require this minimum number of wavelengths. We also develop joint routing and wavelength assignment strategies that not only minimize the number of wavelengths required to implement the worst case logical topologies but also reduce average wavelength requirements. Finally, methods for extending these routing and wavelength assignment results to general two-connected and three-connected physical topologies are presented 相似文献
7.
We compute analytically burst blocking probabilities in an OBS switch when limited-range wavelength conversion is employed.
Two separate queueing models are proposed and analyzed approximately; one for the case where the degree of conversion d is 1 or 2, another for large values of d. The arrival process of bursts is assumed to be an IDLE-ON process. The accuracy of these queueing models was tested against
simulation. We show numerically that in order to keep the burst blocking probability within an acceptable level, the utilization
of each wavelength has to be low. 相似文献
8.
9.
The next generation multimedia applications such as video conferencing and HDTV have raised tremendous challenges on the network design, both in bandwidth and service. As wavelength-division-multiplexing (WDM) networks have emerged as a promising candidate for future networks with large bandwidth, supporting efficient multicast in WDM networks becomes eminent. Different from the IP layer, the cost of multicast at the WDM layer involves not only bandwidth (wavelength) cost, but also wavelength conversion cost and light splitting cost. It is well known that the optimal multicast problem in WDM networks is NP-hard. In this paper, we develop an efficient approximation algorithm consisting of two separate but integrated steps: multicast routing and wavelength assignment. We prove that the problem of optimal wavelength assignment on a multicast tree is not NP-hard; in fact, an optimal wavelength assignment algorithm with complexity of O(NW) is presented. Simulation results have revealed that the optimal wavelength assignment beats greedy algorithms by a large margin in networks using many wavelengths on each link such as dense wavelength-division-multiplexing (DWDM) networks. Our proposed heuristic multicast routing algorithm takes into account both the cost of using wavelength on links and the cost of wavelength conversion. The resulting multicast tree is derived from the optimal lightpaths used for unicast 相似文献
10.
Presents a heuristic algorithm for effectively assigning a limited number of wavelengths among the access stations of a multihop network wherein the physical medium consists of optical fiber segments which interconnect wavelength-selective optical switches. Such a physical medium permits the limited number of wavelengths to be re-used among the various fiber links, thereby offering very high aggregate capacity. Although the optical connectivity among the access station can be altered by changing the states of the various optical switches, the resulting optical connectivity pattern is constrained by the limitation imposed at the physical level. The authors also study two routing schemes, used to route requests for virtual connections. The heuristic is tested on a realistic traffic model, and the call blocking performance of new requests for virtual connections is studied through extensive simulations and compared against the blocking performance of an ideal infinite capacity centralized switch (lowest possible call blocking caused exclusively by congestion on the finite capacity user input/output links, never by the switch fabric itself). Surprisingly, the authors find that, for a wide range of parameters, the blocking performance of the lightwave network is almost the same as that of the ideal centralized switch. From these results, they conclude that the heuristic algorithm is effective and the routing scheme is efficient 相似文献
11.
Zhenghao Zhang Yuanyuan Yang 《Communications, IEEE Transactions on》2006,54(8):1473-1480
All optical communication is attracting more and more attention because of the huge bandwidth of optics. In this paper, we study the performance of bufferless optical wavelength-division multiplexing (WDM) packet switching networks with limited-range wavelength conversion capabilities. We first introduce an optimal scheduling algorithm that maximizes the throughput of the switch. We then derive an analytical model to evaluate the performance of the switch in terms of packet-loss probability. Our model is the first accurate analytical model for a bufferless WDM packet switch with variable conversion distances, and can be used to quantitatively determine the maximum load for a given conversion distance or the minimum conversion distance for a given traffic load. We also conducted simulations to validate the analytical model. Both the analytical and simulation results reveal that limited-range wavelength conversion can achieve almost the same performance as full-range wavelength conversion. 相似文献
12.
13.
We consider the problem of wavelength assignment in reconfigurable WDM networks with wavelength converters. We show that for N-node P-port bidirectional rings, a minimum number of /spl lceil/PN/4/spl rceil/ wavelengths are required to support all possible connected virtual topologies in a rearrangeably nonblocking fashion, and provide an algorithm that meets this bound using no more than /spl lceil/PN/2/spl rceil/ wavelength converters. This improves over the tight lower bound of /spl lceil/PN/3/spl rceil/ wavelengths required for such rings given in if no wavelength conversion is available. We extend this to the general P-port case where each node i may have a different number of ports P/sub i/, and show that no more than /spl lceil//spl sigma//sub i/P/sub i//4/spl rceil/+1 wavelengths are required. We then provide a second algorithm that uses more wavelengths yet requires significantly fewer converters. We also develop a method that allows the wavelength converters to be arbitrarily located at any node in the ring. This gives significant flexibility in the design of the networks. For example, all /spl lceil/PN/2/spl rceil/ converters can be collocated at a single hub node, or distributed evenly among the N nodes with min{/spl lceil/P/2/spl rceil/+1,P} converters at each node. 相似文献
14.
In this letter, we consider the problem of maximizing the number of lightpaths that may be established in a wavelength routed optical network (WRON), given a connection matrix, i.e., a static set of demands, and the number of wavelengths the fiber supports. The problem of establishing all the connections of the connection matrix using the fewest number of wavelengths has been investigated in Banerjee and Mukherjee (1996) and Baroni et al. (1998). We call the former problem max-RWA (problem of maximizing the number of lightpaths) and the latter problem min-RWA (minimizing the number of wavelengths). In this letter, we only consider WRONs with no wavelength conversion capabilities. We formulate the max-RWA problem when no wavelength conversion is allowed as an integer linear programme (ILP) which may be solved to obtain an optimum solution. We hope to solve the ILP exactly for small size networks (few nodes). For moderately large networks (tens of nodes) we develop algorithms based on solutions obtained by solving the LP-relaxation of the ILP formulation. Results obtained for networks such as NSFNET and EONNET are presented 相似文献
15.
16.
We have developed a new layered-routing approach to address the problem of all-optical multicast over wavelength-routed wavelength
division multiplexing (WDM) networks. We model the WDM network as a collection of wavelength layers with sparse light- splitting
(LS) and wavelength conversion (WC) capabilities. We apply the degree constraint technique to solve the problem. The approach
is capable of completing multicast routing and wavelength assignment (MCRWA) in one step. We propose two generic frameworks
to facilitate heuristic development. Any heuristic that is derived from either Prim’s or Kruskal’s algorithm can be easily
imported to solve the MCRWA problem. One example is given for each framework to demonstrate heuristic development. Extensive
simulations were carried out to measure the performance of heuristics developed from the frameworks. The results show that
the STRIGENT scheme is suitable for hardware design and it is advisable to deploy light splitters and wavelength converters
to the same node for better performance. 相似文献
17.
WDM全光网自适应路由和波长分配算法 总被引:4,自引:1,他引:3
研究了无波长转换WDM全光网的路由和波长分配算法(RWA)。通过对已有算法的分析和比较,提出了一种自适应最小跳数路由算法(ADMH)。此算法以最小跳数路由为基础,同时考虑网络状态的变化,因而不仅能尽量少使用网络资源,也能使网络资源的分布保持均衡。计算机模拟仿真的结果表明,这种算法性能在各种网络参数条件下优于或等于已有算法。 相似文献
18.
This paper addresses multicast routing in circuit-switched multihop optical networks employing wavelength-division multiplexing. We consider a model in which multicast communication requests are made and released dynamically over time. A multicast connection is realized by constructing a multicast tree which distributes the message from the source node to all destination nodes such that the wavelengths used on each link and the receivers and transmitters used at each node are not used by existing circuits. We show that the problem of routing and wavelength assignment in this model is, in general, NP-complete. However, we also show that for any given multicast tree, the wavelength assignment problem can be solved in linear time. 相似文献
19.
Ying Wang Tee Hiang Cheng Meng Hiot Lim 《Communications Letters, IEEE》2005,9(9):841-843
Static routing and wavelength assignment (RWA) is usually formulated as an optimization problem with the objective of minimizing wavelength usage (MWU). Existing solution methodologies for the MWU problem are usually based on a two-step approach, where routing and wavelength assignment are done independently. Though this approach can reduce computational cost, the optimality of the solution is compromised. We propose a novel tabu search (TS) algorithm, which considers routing and wavelength assignment jointly without increasing the computational complexity. The performance of the proposed TS algorithm is compared with the integer linear programming (ILP) method, which is known to solve the MWU to optimality. The results for both small and large networks show that our proposed TS algorithm works almost as well as the ILP solution and is much more computationally efficient. 相似文献
20.
全光网静态路由选择和波长分配的分层图算法 总被引:1,自引:0,他引:1
文章提出一种将路由选择和波长分配结合起来的启发式的路由选择和波长分配(RWA)算法.通过这种新的分层图算法和限制光跳距的加权系数来优化全光网的静态路由选择和波长分配,使建立光连接时所需的波长数达到最少.最后对实际的ARPANet等5种光网络进行了计算机仿真,证明了本算法比以前的算法有更好的性能. 相似文献