# American Institute of Mathematical Sciences

October  2018, 14(4): 1667-1684. doi: 10.3934/jimo.2018026

## Selective void creation/filling for variable size packets and multiple wavelengths

 SMACS Research Group, Department of Telecommunications and Information Processing (TELIN), Ghent University, St.-Pietersnieuwstraat 41, B-9000 Ghent, Belgium

Received  August 2017 Published  January 2018

With ever-increasing demand for bandwidth, both optical packet switching and optical burst switching are proposed as alternatives to increase the capacity of optical networks in the future. In these packet-based switching techniques, Fiber Delay Lines (for delay assignments) and wavelength conversion (for channel assignments) are used to avoid contention between contending packets. The involved scheduling algorithms decide on which Fiber Delay Line and wavelength each packet is scheduled in order to maximize performance. For the setting without wavelength conversion we proposed a scheduling algorithm for assigning delays called void-creating algorithm that outperforms existing void filling algorithms for a variety of packet size distributions. This is achieved by selectively delaying packets longer than strictly necessary based on a numerical procedure that assigns a theoretical value to each void based on how likely the void will eventually be filled and thus prove useful. This contribution extends the concept of void-creation to the important case with multiple wavelengths, where also the channel has to be assigned. Results obtained by Monte Carlo simulation show that with our void-creating algorithm the obtainable improvement in various performance measures highly depends on the number of wavelengths present.

Citation: Kurt Van Hautegem, Wouter Rogiest, Herwig Bruneel. Selective void creation/filling for variable size packets and multiple wavelengths. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1667-1684. doi: 10.3934/jimo.2018026
##### References:

show all references

##### References:
The modelled output port as part of a $K \times M$ optical switch.
An example of a provisional schedule for a single wavelength when the packet size is variable ($B \neq E[B] = D = 1$).
Evolution of the provisional schedule for a single wavelength when the packet size is fixed and equal to the granularity ($B = E[B] = D$).
Life cycles of the voids created by scheduling on the $\bullet$ and $\blacktriangle$ of Fig. 2.
An example of a provisional schedule for fixed packet size and multiple wavelengths ($c = 4$). The G-VF algorithm will choose to minimize the gap by scheduling on position $a$.
An example of a provisional schedule for fixed packet size and multiple wavelengths ($c = 4$) resulting in a possible void creation on the second wavelength.
Maximum gain (i.e., reduction giving rise to performance gain) for different performance measures as a function of the number of wavelengths ($c$).
Performance measures of D-VF for different packet size distributions and a single wavelength.
 D-VF Fixed B= E[B]=D Exponential E[B]=D Uniform on [0, 2D] Uniform on [0.5D, 1.5D] p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 LP 2.1 % 14.5 % 2.6 % 9.1 % 1.9 % 9.8 % 2.2 % 12.9 % LPlength 2.1 % 14.5 % 3.4 % 11.9 % 2.3 % 11.7 % 2.3 % 13.4 % Packet delay 3.0 6.1 2.5 4.1 2.7 4.8 3.0 5.7 Packet gap 0.36 0.42 0.29 0.30 0.33 0.34 0.37 0.39
 D-VF Fixed B= E[B]=D Exponential E[B]=D Uniform on [0, 2D] Uniform on [0.5D, 1.5D] p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 LP 2.1 % 14.5 % 2.6 % 9.1 % 1.9 % 9.8 % 2.2 % 12.9 % LPlength 2.1 % 14.5 % 3.4 % 11.9 % 2.3 % 11.7 % 2.3 % 13.4 % Packet delay 3.0 6.1 2.5 4.1 2.7 4.8 3.0 5.7 Packet gap 0.36 0.42 0.29 0.30 0.33 0.34 0.37 0.39
Optimal thresholds and corresponding performance improvements of the void value threshold algorithm for a single wavelength.
 (A) Optimal thresholds optimal threshold Fixed B= E[B]=D Exponential E[B]=D Uniform on [0, 2D] Uniform on [0.5D, 1.5D] p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 LP 1.0 1.2 1.1 1.4 1.4 1.6 1.2 1.5 LPlength 1.0 1.2 2.3 3.0 1.9 2.0 1.3 1.6 Packet delay 1.0 1.2 0.9 0.9 1.9 2.0 1.3 1.6 Packet gap 1.2 1.3 3.0 2.3 1.8 2.0 1.5 1.6 (B) Corresponding performance improvements maximum gain Fixed B= E[B]=D Exponential E[B]=D Uniform on [0, 2D] Uniform on [0.5D, 1.5D] p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 LP 54.1 % 36.1 % 4.5 % 6.4 % 5.7 % 6.9 % 28.7 % 19.4 % LPlength 54.1 % 36.1 % 0.2 % 0.1 % 0.6 % 1.9 % 25.0 % 16.5 % Packet delay 16.3 % 16.2 % 0.8 % 3.4 % 1.7 % 3.9 % 8.2 % 8.8 % Packet gap 11.5 % 22.8 % 0.0 % 0.0 % 0.3 % 1.3 % 4.5 % 10.3 %
 (A) Optimal thresholds optimal threshold Fixed B= E[B]=D Exponential E[B]=D Uniform on [0, 2D] Uniform on [0.5D, 1.5D] p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 LP 1.0 1.2 1.1 1.4 1.4 1.6 1.2 1.5 LPlength 1.0 1.2 2.3 3.0 1.9 2.0 1.3 1.6 Packet delay 1.0 1.2 0.9 0.9 1.9 2.0 1.3 1.6 Packet gap 1.2 1.3 3.0 2.3 1.8 2.0 1.5 1.6 (B) Corresponding performance improvements maximum gain Fixed B= E[B]=D Exponential E[B]=D Uniform on [0, 2D] Uniform on [0.5D, 1.5D] p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 p=0.6 p=0.8 LP 54.1 % 36.1 % 4.5 % 6.4 % 5.7 % 6.9 % 28.7 % 19.4 % LPlength 54.1 % 36.1 % 0.2 % 0.1 % 0.6 % 1.9 % 25.0 % 16.5 % Packet delay 16.3 % 16.2 % 0.8 % 3.4 % 1.7 % 3.9 % 8.2 % 8.8 % Packet gap 11.5 % 22.8 % 0.0 % 0.0 % 0.3 % 1.3 % 4.5 % 10.3 %
Performance measures of G-VF for a fixed packet size distribution and a varying number of wavelength ($c = 1,2,4,6$ and $8$).
 G-VF c=1 c=2 c=4 c=6 c=8 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 LP 2.1 % 14.5 % 22.5 % 0.0 % 4.5 % 13.8 % x 0.1 % 5.7 % x 0.0 % 1.7 % x x 0.3 % LPlength 2.1 % 14.5 % 22.5 % 0.0 % 4.5 % 13.8 % x 0.1 % 5.7 % x 0.0 % 1.7 % x x 0.3 % Packet delay 3.0 6.1 7.1 1.0 4.9 7.1 0.4 1.9 6.2 0.2 1.1 4.5 0.1 0.8 2.8 Packet gap 0.36 0.42 0.42 0.13 0.25 0.28 0.03 0.08 0.16 0.01 0.04 0.09 0.01 0.02 0.05
 G-VF c=1 c=2 c=4 c=6 c=8 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 LP 2.1 % 14.5 % 22.5 % 0.0 % 4.5 % 13.8 % x 0.1 % 5.7 % x 0.0 % 1.7 % x x 0.3 % LPlength 2.1 % 14.5 % 22.5 % 0.0 % 4.5 % 13.8 % x 0.1 % 5.7 % x 0.0 % 1.7 % x x 0.3 % Packet delay 3.0 6.1 7.1 1.0 4.9 7.1 0.4 1.9 6.2 0.2 1.1 4.5 0.1 0.8 2.8 Packet gap 0.36 0.42 0.42 0.13 0.25 0.28 0.03 0.08 0.16 0.01 0.04 0.09 0.01 0.02 0.05
Optimal thresholds and corresponding performance improvements of the void value threshold algorithm for a fixed packet size distribution and a varying number of wavelength ($c = 1,2,4,6$ and $8$).
 (A) Optimal thresholds optimal threshold c=1 c=2 c=4 c=6 c=8 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 LP 0.9 1.2 1.3 0.7 1.0 0.9 x 0.8 0.7 x 2.3 0.5 x x 1.4 LPlength 0.9 1.2 1.3 0.7 1.0 0.9 x 0.8 0.7 x 2.3 0.5 x x 1.4 Packet delay 0.9 1.2 1.2 to 1.0 0.9 to to 0.7 to to 1.0 to to 2.4 Packet gap 1.2 1.3 1.3 0.8 0.9 0.9 to 0.7 0.7 to to 0.5 to to 0.5 (B) Corresponding performance improvements maximum gain c=1 c=2 c=4 c=6 c=8 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 LP 53.5 % 35.9 % 26.0 % 47.2 % 41.3 % 25.6 % x 26.6 % 22.1 % x 86.5 % 12.8 % x x 1.8 % LPlength 53.5 % 35.9 % 26.0 % 47.2 % 41.3 % 25.6 % x 26.6 % 22.1 % x 86.5 % 12.8 % x x 1.8 % Packet delay 16.1 % 16.1 % 12.9 % 0 % 14.0 % 11.1 % 0 % 0 % 8.3 % 0 % 0 % 3.2 % 0 % 0 % 1.0 % Packet gap 11.4 % 22.7 % 24.8 % 3.5 % 19.8 % 20.9 % 0 % 5.2 % 14.3 % 0 % 0 % 7.4 % 0 % 0 % 2.1 %
 (A) Optimal thresholds optimal threshold c=1 c=2 c=4 c=6 c=8 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 LP 0.9 1.2 1.3 0.7 1.0 0.9 x 0.8 0.7 x 2.3 0.5 x x 1.4 LPlength 0.9 1.2 1.3 0.7 1.0 0.9 x 0.8 0.7 x 2.3 0.5 x x 1.4 Packet delay 0.9 1.2 1.2 to 1.0 0.9 to to 0.7 to to 1.0 to to 2.4 Packet gap 1.2 1.3 1.3 0.8 0.9 0.9 to 0.7 0.7 to to 0.5 to to 0.5 (B) Corresponding performance improvements maximum gain c=1 c=2 c=4 c=6 c=8 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 p=0.6 p=0.8 p=0.9 LP 53.5 % 35.9 % 26.0 % 47.2 % 41.3 % 25.6 % x 26.6 % 22.1 % x 86.5 % 12.8 % x x 1.8 % LPlength 53.5 % 35.9 % 26.0 % 47.2 % 41.3 % 25.6 % x 26.6 % 22.1 % x 86.5 % 12.8 % x x 1.8 % Packet delay 16.1 % 16.1 % 12.9 % 0 % 14.0 % 11.1 % 0 % 0 % 8.3 % 0 % 0 % 3.2 % 0 % 0 % 1.0 % Packet gap 11.4 % 22.7 % 24.8 % 3.5 % 19.8 % 20.9 % 0 % 5.2 % 14.3 % 0 % 0 % 7.4 % 0 % 0 % 2.1 %
 [1] Mikhail Gilman, Semyon Tsynkov. Statistical characterization of scattering delay in synthetic aperture radar imaging. Inverse Problems & Imaging, 2020, 14 (3) : 511-533. doi: 10.3934/ipi.2020024 [2] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [3] Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020027 [4] Yunfei Lv, Rong Yuan, Yuan He. Wavefronts of a stage structured model with state--dependent delay. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 4931-4954. doi: 10.3934/dcds.2015.35.4931

2019 Impact Factor: 1.366