Mathematical Model for Dynamic Pump-Wavelength Selection Switch ()
1. Introduction
Optical packet switched (OPS) networks are emerging as a serious candidate for the evolution of optical telecommunication networks needed to support high-throughput services such as voice over IP (VoIP) and high quality video streaming on demand. In an optical packet network with OPSs interconnected with optical fibers running wavelength division multiplexing (WDM), packets are transmitted from source to destination without any optical-electrical-optical (O/E/O) conversion.
In an OPS, an optical fiber carries several wavelengths to transmit packets. An input fiber may carry as many packets as wavelengths, which could be destined to one or several output fibers. In an OPS, output contention occurs when multiple packets from different input fibers share the destination of a single output fiber even though they use the same wavelength at the same time. Only one of the contending packets is forwarded to the output fiber, the others are dropped. To select packets (and wavelengths), a switch configured by a scheduler can be used. In an OPS, the set of aggregated wavelengths coming from an input fiber is optically demultiplexed into individual wavelengths and each wavelength is assigned to an input port of the switch fabric that connects outputs to inputs. The outputs of the switch fabric are assigned different wavelengths. Therefore, each input port of the switch fabric can be connected to an output port of the same wavelength. The set of individual wavelengths of an output fiber are then aggregated before they egress the switch. In the switch fabric, the scheduler decides which inputs and outputs to interconnect for each wavelength by performing a matching process (i.e., the assignment of one input to one output). The case wherein several inputs of the same wavelength have packets for the same output is said to be output contention.
Some methods proposed for resolving output contention use 1) optical buffering through fiber delay lines (FDLs) [1] [2] to store packets. Unfortunately, feasible FDLs are delays smaller than those the packets would need to secure contention-free transmission; 2) deflection routing [3] , which can reduce the need to buffer packets. In this approach, one packet is sent to the designed output while the others are sent to any available output as alternative routes. However, the network control demanded by this approach is overly complex and packet re-sequencing is required as packets may arrive out of order at the destination.
A practical approach to avoiding contention is to use wavelength conversion [4] . A signal with one wavelength is converted to another wavelength. The wavelength of a contending packet that will not be selected is converted into another available wavelength and connected to the same output fiber. A full wavelength converter (FWC) [5] can convert a wavelength to any other wavelength. However, this approach is too expensive for practical applications as dedicated FWCs must be provisioned. To reduce cost of wavelength conversion, the so-called share per node (SPN), in which all converters at the switching node are shared, is considered to be a cost-effective solution [6] [7] . Tunable wavelength converters may be used. However, conversion capability is not be efficient since only one wavelength can be converted at a time.
A parametric wavelength converter (PWC) [8] is an alternative approach to wavelength conversion because multiple wavelengths, multiple channels, can be converted simultaneously. To define both the original wavelength, , requiring conversion, and the new wavelength, , a continuous pump-wavelength, , is set to. That is, the selection of defines the conversion pair of and. Because a conversion wavelength pair comprises the set of wavelengths converted from and converted to, each wavelength can play either role, the source wavelength or the converted wavelength in a time slot. For example, if is set to convert to/from, where and are transmission wavelengths, then can be selected to be the original wavelength and can be selected to be the converted wavelength or vice versa, with the condition that just one direction is possible at a time. Note that each pair in the set can have independent conversion directions at a given time. Figure 1 shows examples of the wavelength conversion pairs in a PWC. There are seven
Figure 1. Example of wavelength conversion pairs in PWC.
wavelengths in this example, to. When, the conversion pairs in the PWC are, , and, which can be used in either direction. The set of conversion pairs using the same pump-wavelength is called a conversion pattern. Setting different pump-wavelengths yields different conversion patterns.
Multiple wavelength conversion based on a parametric process appears to be becoming feasible. The simultaneous multiple wavelength conversion of over 30 channels has been reported using fiber [9] and LiNbO3 waveguides [10] . A high-capacity field transmission experiment using multi-wavelength conversion has also been demonstrated [11] . Moreover, the parametric process is fully transparent to various types of advanced modulation formats such as DPSK [12] and QPSK [13] . These studies show that guard bands can be provided with a suitable channel spacing. With this in mind, this paper assumes that guard bands are provided in the adopted channel spacing, such that they are assumed to be provisioned in the remainder of this paper.
Several studies describe OPSs that use PWCs [14] -[20] . A dynamic pump-wavelength selection (DPS) switch was proposed as an alternative approach to pump-wavelength selection [17] [18] . The set of pump-wavelengths is dynamically changed in every time slot depending on the conversion pairs needed, so that the total number of successful packets can be maximized. The DPS switch combines a matching scheme to connect input ports, output ports and dynamic pump-wavelength selection.
A heuristic matching algorithm was introduced for the DPS-based OPS [17] [18] . Simulation results showed that the DPS switch provides low packet loss rates. However, there is no guarantee that the heuristic matching algorithm does provide the optimum solution. Moreover, the performance offset from the optimum solution has not been confirmed.
In this paper, a mathematical model for the DPS-based OPS is proposed as a reference with which to confirm the performance of the heuristic matching algorithm in [18] . Mathematical modeling is a convenient tool for solving optimization problems. After proposing a mathematical model, the optimum solution of the DPS switch can be obtained. The objective of the mathematical model is to maximize the number of successful packet requests, which in turn minimizes the number of packet losses. The result shows that the heuristic matching algorithm achieves the same performance as the optimum solution provided by the mathematical model.
2. Dynamic Pump-Wavelength Selection Switch
A dynamic pump-wavelength selection (DPS) switch, is an OPS using PWCs where the set of pump-wavelengths is dynamically changed in every time slot based on requests. For the general case, the set of pump-wavelengths is defined as, where is the pump-wavelength and is the transmission wavelength index for the Mth PWC.
The DPS switch, whose set of pump-wavelengths can be altered on a time slot basis, consists of three parts: the controller, the pump-wavelength generator, and the main switch (see Figure 2).
The controller performs both matching between input and output ports and selecting pump-wavelengths in an integrated manner on a time slot basis. It controls both the switching configuration and pump-wavelength selection by using a matching scheme. It uses electrical signals to communicate with the pump-wavelength generator and the main switch.
The pump-wavelength generator sets pump-wavelengths that are determined by the controller in every time slot. Figure 2 shows a possible implementation approach to the generation of pump-wavelengths. Tunable laser diodes (TLDs) are used to generate pump-wavelengths for PWCs, one TLD for each PWC. A guard time is needed to separate the time slots considering the time needed for switching and for setting pump-wavelengths. A tunable external-cavity laser requires 0.8 ns for wavelength tuning [21] , while a switch using PLZT optical switching technology [22] requires 2.5 ns for optical switching. As the time for wavelength tuning is less than that for optical switching, the guard time is mainly determined by the optical switching technology adopted. With a transmission speed of 10 Gbps, the number of required guard-time bits is 25 bits (2.5 ns ´ 10 Gbps). Consider a fixed packet length of 64 bytes. The ratio of the guard-time bits to the number of packet bits is 25/(64 ´ 8) = 0.05. Therefore, the impact of the guard time on bandwidth utilization is not large in this example.
The main switch is an OPS with N input and output fibers and M PWCs. Each fiber carries W different wavelengths. Demultiplexers at the output of PWCs are used. Each demultiplexed wavelength has a one-to-one correspondence with an input port of the switch fabric. The individual wavelengths, coming through individual input ports of the switch fabric, are grouped by an optical coupler before being forwarded to the output fiber. In
this way, each converted wavelength can be connected to any output.
3. Proposed Mathematical Model for DPS Switch
A mathematical model is a convenient tool for solving optimization problems. In this paper, the problem is modeled as binary integer linear programming (BILP) to maximize number of connections between input and output ports via PWCs, which in turn minimizes the number of packet losses. In the BILP, the variables are required to be 1 or 0 rather than arbitrary integers. The terminology is as follows.
th input fiber of the main switch, where,.
th output fiber of the main switch, where,.
th original wavelength, where,.
th converted wavelength, where,.
th PWC, where,.
is the decision variable of this BILP model. It defines successful connection from the ith input fiber (wth wavelength) via mth PWC with pump-wavelength to the oth output fiber (th wavelength), where is a decision variable and and.
Objective function
(1a)
Subject to
(1b)
(1c)
(1d)
(1e)
(1f)
(1g)
(1h)
(1i)
Equation (1a) is the objective function of this BILP model. It maximizes the number of connections between input and output ports via PWCs. Parameter defines the total number of incoming requests. is the given parameter that defines the maximum total number of conversion pairs when the pump-wavelength is selected to be. For example, if, is 2 because the conversion pairs are and. If the is 3 because the conversion pairs are, , and.
Equations (1b)-(1i) are constraints of this BILP model. While Equations (1b)-(1d) define general characteristics of PWC, Equations (1e)-(1i) define the special features of a PWC based on DPS. Equation (1b) is the constraint that limits the total number of successful requests so that it does not outnumber the total number of incoming requests. Equation (1c) is the constraint that defines that each oth output fiber at th wavelength can be assigned only in one request. Equation (1d) is the constraint that defines that each incoming request can be assigned to only one output fiber per wavelength. Equation (1e) is the constraint that limits the total number of conversion pairs in the mth PWC when its pump-wavelength is selected to be so that it does not exceed the maximum capacity of conversion pairs permitted by pump-wavelength. Equation (1f) is the constraint that defines that each PWC is able do conversion in only one direction. Equation (1g) is the constraint that defines that each direction (one way) is able to be assigned to only one conversion pair with and defines that the two compared variables are not the same conversion variables. Equation (1h) is the constraint that defines that each PWC can do multiple conversions. The last constraint, Equation (1i) defines that in a time slot each PWC can be assigned only one pump-wavelength or none at all. All of the above constraints apply if there is a request from ith input fiber with wth wavelength is addressed to the th output fiber and the th output fiber with th wavelength is available.
4. Performance Evaluation
In the simulation, the performance of the heuristic matching algorithm of OPS with DPS-based PWC is confirmed against the optimum solution provided by the proposed mathematical model, in term of packet loss rate. The packet loss rate is the difference between the total number of incoming requests and the total number of successful requests, with regard to the total number of incoming requests. An OPS with, , and is considered, otherwise stated. We generated incoming packets. Uniform and non-uniform traffic patterns, which are a subset of admissible traffic patterns [16] , are considered. In the uniform traffic, incoming traffic from input ports is uniformly distributed to all output ports. Since the performance of the DPS switch was discussed in [18] , only the difference in packet loss rate between the heuristic algorithm and the mathematical model is described in this paper.
4.1. Uniform Traffic Pattern
We assume that packet arrival at input ports follows a Bernoulli process. When input traffic load is, an incoming packet arrives with probability of, and there is no arrival with probability of. The incoming packets are distributed uniformly to all output ports. The input traffic is assumed to be homogeneous and distributed uniformly to all input ports.
Figures 3(a)-(d) show that the performance of the mathematical model matches that of the heuristic algorithm for all parameter combinations examined. Figure 3(a) shows the packet loss rate of the DPS-based OPS for different values. The packet loss rate increases with the traffic load. It reaches its maximum at when the traffic load is 1.0. Figure 3(b) shows the packet loss rate for different values. The packet loss rate decreases as increases. It is significantly decreased when changes from one to two. However, the change when is larger than two is slight. The packet loss rates when and are almost the same. Figure 3(c) shows the packet loss rate for different values. The packet loss rate increases as rises from two to four. The performance remains the same when and. Figure 3(d) presents the packet loss rate for different values. The packet loss rate decreases as increases.
Figure 3. Packet loss rate of heuristic algorithm and mathematical model with uniform traffic.
4.2. Non-Uniform Traffic Pattern
Packet loss rates under non-uniform traffic were examined using four well-known traffic models: unbalanced [23] [24] , power of two (PO2) [25] , diagonal [26] , and hotspot [27] .
The traffic is uniform if the destinations are uniformly distributed among all output ports [28] [29] . Otherwise, the traffic is non-uniform [30] . For uniform and non-uniform traffic, packets arriving at input ports follow a Bernoulli process, and the input traffic is assumed to be homogeneous, and so is distributed uniformly to all input ports. The unbalanced traffic model presented in [23] is used. The unbalanced traffic is generated by setting the parameter called the unbalance probability,. If the input load offered to the ith input, , the traffic load from the ith input to jth output, , is given by [23] [24] ,
(2)
The traffic is uniformly distributed if is zero and the traffic is completely non-uniform when is one.
The power of the two (PO2) traffic model [25] is represented by matrix as:
(3)
The diagonal traffic [26] is generated using a diagonal probability, , to represent the traffic from the ith input to jth output, , which is given by
(4)
is written in matrix form as follows.
(5)
Under hotspot traffic [27] , each input sends a packet to outputs with equal probability except for a specific output. The traffic is generated based on a parameter called hotspot probability, , which is the probability that the packet is forwarded from the input to the specific output., which is the traffic load from the ith input to output, is given by
(6)
Figures 4(a)-(d) confirm that the packet loss rates of the heuristic algorithm are the same as those of the mathematical model in every non-uniform traffic pattern sampled. Figure 4(a) shows the packet loss rate for different values. The packet loss rate decreases as increases. When is one, all incoming packets are
Figure 4. Packet loss rate of heuristic algorithm and mathematical model with non-uniform traffic.
assigned to output fibers with the same number as the input fiber. As a result, there is no contention when is one and the packet loss rate is zero. Figure 4(b) indicates that the packet loss rate increases with under PO2 traffic. Figure 4(c) shows that the packet loss rate under the diagonal traffic falls as approaches 0.0 or 1.0. It reaches its maximum when is 0.5. When, every incoming packet is forwarded to the next output fiber. When, every incoming packets is forwarded to the output fiber with the same number as the input fiber. Therefore, there is no contention when is zero or one. The packet loss rate is zero. Figure 4(d) shows the packet loss rate under hotspot traffic. The packet loss rate decreases as increases when is between 0.0 and 0.3. It is minimum when. When, the packet loss rate increases with.
5. Conclusion
This paper proposes a mathematical model to confirm the performance of the heuristic matching algorithm based on dynamic pump-wavelength selection for an OPS with PWCs. The objective function of the mathematical model is to maximize the number of connections, which in turn minimizes the number of packets lost in the optical packet switch between input and output ports. Simulation results show that the heuristic matching algorithm achieves the same performance as the optimum solution is provided by the mathematical model for every parameter combination tested under both uniform and non-uniform traffic patterns.
Acknowledgements
This work was supported in part by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (B) 23360168, and the Support Center for Advanced Telecommunications Technology Research (SCAT).