Open Access
Add to BibSonomyAbstract
This paper investigates the design and implementation of distributed computing applications in local area network. We propose a novel Dynamical Wavelength Scheduled Hybrid WDM/TDM Passive Optical Network, which is termed as DWS-HPON. The system is implemented by using spectrum slicing techniques of broadband light source and overlay broadcast-signaling scheme. The Time-Wavelength Co-Allocation (TWCA) Problem is defined and an effective greedy approach to this problem is presented for aggregating large files in distributed computing applications. The simulations demonstrate that the performance is improved significantly compared with the conventional TDM-over-WDM PON.
©2009 Optical Society of America
1. Introduction
Among many optical access networks, the Wavelength Division Multiplexing (WDM) / Time Division Multiplexing (TDM) Hybrid Passive Optical Network (HPON) has been considered as a promising solution for the next-generation broadband access networks, because of the extended overlay reach serving the increased number of customers, the lower network cost per PON user, the more flexible and scalable optical access solution, and the higher utilization efficiency of network resource [1-4].
In local area with the scope of dozens of kilometres, we assume that HPON connects a collection of geographically distributed and heterogeneous computational resources, such as supercomputer, cluster, storage and display devices, via high bandwidth optical path. In the network context, one can try to use accessible computing resources distributed in different locations across HPON for distributed computing applications such as geosciences, biomedical informatics, and nuclear physics [5-8].
However, when considering the distributed computing applications on hybrid PON, we may need to build completely customized HPON because the requirements of distributed computing applications are far beyond today's HPON infrastructure. In general, distributed computing applications consist of a set of tasks with dependent relationship. These tasks are allocated to different computational and storage resources across network for computing, analyzing and other processing. Thus, each geographical distributed network node associated with computational resources has the potential to generate extremely large capacity transmission with gigabytes or terabytes size [5,6]. These data should be aggregated again to the remote supercomputer at data centre for final data-processing and visualization within several seconds or several tens of seconds [7,8]. Therefore, there exist stringent bandwidth requirements to upstream transmission from different optical network units (ONU) to optical line terminal (OLT) across HPON for data aggregation with the lower transfer latency. It is totally different from the telecommunication PON services and applications that have much more downstream traffic than those in upstream.
However, in existing HPON architectures, the upstream wavelength per ONU is fixed. Within one sub-PON, the traffic loads from different ONUs must be upstream-transmitted in one wavelength with Time Division Multiple Access (TDMA) scheme. With high traffic burstiness and unbalanced traffic pattern for distributed computing applications, the utilization of wavelength becomes poor and transfer latency is very large.
In this paper, we propose a novel WDM/TDM HPON architecture, which enables flexible allocation of upstream bandwidth resources depended on traffic requirements for real-time data aggregation in distributed computing applications. The proposed HPON architecture would not only employ the same components in each ONU (usually referred to as colorless ONU in the literature), but also allows all ONUs to share all wavelength resources across HPON. Thus, each ONU can obtain upstream bandwidth on demand in the wavelength or finer sub-wavelength granularity and better quality of service (QoS). Meanwhile, to improve effectively the overall system throughput and to minimize the transfer latency for data aggregation, we consider the problem of bandwidth reservation for dedicated channels and for future time slots, where a channel is operated in a TDM fashion. We define the above problem as Time-Wavelength Co-Allocation (TWCA) Problem for scheduling these large files over their respective wavelengths and timeslots. We will prove that TWCA is NP-complete, propose an effective greedy approach and finally evaluate the system performance compared with the conventional TDM-over-WDM PON.
The rest of the paper is organized as follows. Section 2 presents the DWS-HPON network topology and design parameters. Experimental demonstration is given in Section 3 to verify the total connectivity between OLT and ONUs using spectrum slicing techniques of broadband light source (BLS). In section 4, we model the data aggregation problem as the Time-Wavelength Co-Allocation (TWCA) Problem and discuss an effective greedy approach based on some sorting schemes and scheduling heuristics to solve it. And the numerical results are presented and discussed. At last, conclusions are given in Section 5.
2. Dynamic Wavelength Scheduled Hybrid WDM/TDM PON
Figure 1 shows the proposed Dynamical-Wavelength-Scheduled Hybrid WDM/TDM PON (DWS-HPON). Without loss of generalization, here we just show four wavelength channels both in down and upstream. The basic structure of optical network units (ONU) is shown in Fig. 2.
Fig. 1. Schematic diagram of the proposed Dynamical-Wavelength-Scheduled hybrid WDM/TDM PON architecture
The centric supercomputer is attached to optical line terminal (OLT), and other computing and storage resources are located in respective ONUs. The proposed DWS-HPON provides multi-gigabits network connection between OLT and ONUs for large data transfer in distributed computing applications.
In downstream (OLT-ONU) direction, each downstream WDM wavelength λ1~λ4 transmitted by the OLT only is routed to one sub-PON respectively, as same as conventional HPON. In each sub-PON, downstream data are broadcast to every ONU by power optical splitter (POS). Each ONU equipped with Photo-Diode (PD) receiver gets data by checking electronically different identifier such as LLID (Logical Link IDentifier) over MAC (Media Access Control) layer. It is noteworthy that an optical broadcast channel λ10 (dashed line in Fig. 1) is added to this system for transferring control signalling. The centre scheduler in OLT has overall knowledge of the amount of data that each ONU will send by last round of polling scheme. In the scheme, every ONU reports the amount of data to be transferred to OLT. Based on the overall information, OLT scheduler decides to schedule upstream data on which wavelength channel and at which time slots for each ONU, in order to minimize the completion time of upstream transmission. Then the scheduling results of wavelength and timeslots (usually referred to as Grant message in Ethernet-PON protocol) are carried on the overlay broadcast channel λ10. The overlay broadcast wavelength λ10 is power-split to four branches and then coupled with four downstream paths λ1~λ4 at remote node (RN) and finally reaches each ONU.
The design schematic of ONU is shown in Fig. 2. In upstream (ONU-OLT) direction, upon receiving the Grant message, ONU adjusts electronically Fibre Bragg Grating (FBG) to filter one designated narrow-band optical upstream carrier of four upstream carriers λ11~λ14 from BLS and sends up-data and up-controlling (Report) signalling in required timeslots. The Report signal contains the amount of data to be transferred from ONUs to OLT. At RN, the upstream wavelength λ11~λ14 are combined by a coupler (POS) and sent back to OLT through feeder fibre.
Figure 3 shows the wavelength allocation plan used in the experiment network, and divides the C-band into two, with the one half carrying downstream channels (λ1~λ4) and the another half carrying upstream channels (λ11~λ14) and broadcast control signalling channel (λ10). The two bands are separated by a relatively broad guard band, which allows low-cost filter to be used to separate the downstream data and broadcast control signalling (Grant) in ONU. The transmissions of both up-data and up-controlling (Report) signal are separated in time domain as shown in Fig. 4. The up-data are followed closely by up-controlling signal using the same wavelength channel for each ONU. The ranging and clock synchronization schemes for each ONU in multiple sub-PONs are the same as the EPON protocol. The length of assigned slots for each active ONUs and the polling period are variable in each cycle according to the traffic request from ONUs. The up-controlling (Report) signals are received by the supercomputer at data centre, and then feed back to the centric scheduler in OLT for scheduling processing.
The DWS-HPON is a potential network infrastructure for distributed computing applications, because of two-stage tree-topology naturally connecting the data center with many geographically distributed and heterogeneous computational resources. It is also self-adaptive optical access system to the high traffic burstiness and unbalanced traffic pattern. When the much heavier upstream traffic load is occurred within one sub-PON, several available wavelengths could be allocated to this sub-PON simultaneously. Thus the total upstream bandwidth within one sub-PON are greater than one wavelength capacity, compared to the conventional hybrid TDM-over-WDM PON, where one upstream wavelength is dedicated to one sub-PON. For the sub-PON with the lower upstream traffic, each ONU in this sub-PON transfers upstream data on one wavelength channel in a TDMA fashion. Consequently, the DWS-HPON enables to transfer data in the wavelength or finer sub-wavelength granularity and improves effectively overall network throughput.
3. Experimental Setup and Results
Figure 5 shows the experimental setup to demonstrate the feasibility of the proposed DWS-HPON. In the OLT, single downstream data channel λ1 at 1544.53nm and broadcast signalling channel λ10 at 1547.72nm are fed into two single drive Mach-Zehnder modulators (MZMs), which are modulated by a 10-Gb/s 231 -1 pseudorandom binary sequence (PRBS) and its complementary data, generated by a pulse pattern generator (PPG), respectively. Then the two wavelengths are combined by an AWG after amplification by erbium-doped fibre amplifier (EDFA) and filtering by tunable band-pass filter (BPF). After transmission of 12.5km single mode fibres (SMF), another AWG at RN is used to separate both downstream signals. Due to the broadcast control signal is power split into four copies by the 1×4 star coupler at remote node, it is attenuated 6dB by a variable optical attenuator (VOA) to simulate power splitting. The attenuated broadcast signal is coupled with downstream data again and fed into 12.5km SMF and finally sent to ONU. At ONU, the multiplexed signals go through BPF and are received by photodiode (PD), respectively.
The bit-error-rate (BER) curves and eye diagrams of the NRZ downstream data and broadcast control signaling are provided in Fig. 6. The power penalties are ~0.44 dB and ~0.85dB with the ~10-dB extinction ratio (ER) of the NRZ signal, respectively.
To verify the feasibility of the downstream link, power budgets analysis are carried out using a modulated optical power of around -6dBm and a gain of 40dB for the EDFA as shown in Table 1. In this analysis, losses were made of a band-pass filter (BPF) loss of 3dB, a 2.8dB transmission loss for each 12.5km optical fiber, an insert loss of 5dB for AWG, an insert loss of 0.8dB for optical circulator, a splitter loss of about 15dB (10log32) at remote node and an insert loss 0.5dB for CWDM de-multiplexer at ONU. Specially, for the broadcast control signal, an additional 6dB (10log4) loss is incurred to simulate power splitting to four downstream branches. The receiver sensitivity of the downstream data and broadcast control signal are considered to be -14.6dBm and -14.2dBm respectively, according to the experiment data (Fig. 6). The power margin of about 9.1dB and 2.7dB are obtained for downstream data and broadcast control signal, which indicates the feasibility of the downstream link with N=4 sub-PONs and M=32 users in each sub-PON.
Table 1. Power Margin Calculation for Downstream and Upstream Data
In upstream, we assume that ONU has received overlay broadcast signaling that contains all scheduling information. To eliminate inter-spectrum correlation, we adopt first-modulation last-slicing approach for transferring up-stream data and signaling. Broadband light spectrum (BLS) in C-band at -20dBm from a commercial BLS (Agilent 83438A ERBIUM SOURCE) is fed into a MZM which is biased at the quadrature point and is driven by a 2.5-Gb/s 231-1 PRBS to generate upstream NRZ signal at -26dBm, with an ER of ~10dB. The modulated NRZ broadband signal is then spectrum-sliced at 1556nm by a tunable FBG with a pass bandwidth of 1.6nm, according to scheduling information from OLT, and then amplified by EDFA. The output optical signal form ONU is around 12.7dBm. After total 25km SMF transmission with the transmission loss of 5.6dB and a splitter loss of about 15dB (10log32) at remote node, the OLT receives the upstream data and up-controlling (Report) signaling at about -10.9dBm by a 10-GHz broadband PD, respectively. The power margin of about 0.5dB is obtained for upstream transmission according to the experiment data (Fig. 7).
Fig. 7. BER curves and eye diagrams for NRZ upstream signal using spectrum-slicing techniques of BLS
The BER performance and eye diagrams of NRZ up-signals before and after the 25km transmission are shown in Fig. 7. For the spectrum-sliced NRZ with the ~10-dB ER, the power penalty is ~1.5 dB.
To demonstrate TDM and WDM of upstream wavelength, the PPG was set to “zero substitute” mode to generate a burst packet consisting of 408 bits of random data followed by 616 ‘0’s. For the TDM of upstream wavelengths, two 2.5-Gb/s non-return-to-zero (NRZ) data streams are generated at the same wavelength λ11=1556nm, in separate time slots, respectively, and combined with optical coupler after 12.5km SMF transmission. The TDM waveforms as shown in Fig. 5a)~c) confirm that contention among the up-streams traffic can be avoided by proper scheduling. The spectra of multiplexing signals are inserted in Fig. 5d) to demonstrate WDM of 1556nm and 1548.8nm upstream wavelengths.
4. Scheduling Algorithm and Numerical Results
We assume that respective TDM-PON in our proposed DWS-HPON follows Ethernet-PON standard, thus the Multi-Point Control Protocol (MPCP) is deployed in OLT, which regulates the file transfer protocol (Ethernet) and provides the signaling infrastructure (control plane) for coordinating the data transmission from the ONUs to the OLT. The OLT scheduler has overall knowledge of the amount of data that each ONU will send by last round of polling communication between OLT and ONUs. The objective of our proposed scheduling algorithm is to determine 1) upstream wavelength channel on which file transfer, and 2) time slots at which a connection must be reserved for the corresponding file, in order to make the transmission of many large data files from each ONU to the centric supercomputer (OLT) as soon as possible. Each file fi is denoted by file size Si, transfer time Ti, and maximum transfer delay deadline Di. Transfer time Ti is estimated as Ti= Si / BW + Pi, where BW denotes the bandwidth capacity of wavelength channel. We assume that each file is large enough to make the value of Si/BW much greater than that of Pi, so we ignore the difference of different ONU-to-OLT propagation delay Pi. This means that transfer time Ti only depends on file size Si instead of ONU-to-OLT propagation delay Pi.
We define the above problem as Time-Wavelength Co-Allocation (TWCA) Problem in DWS-HPON. We term N independent files originating from ONU as N independent jobs to be processed, and term M available identical wavelength channels as M parallel machines, because of the same bandwidth capacity (say B=2.5-Gigabit). This is Multiprocessor Scheduling Problem (MSP) Pm ∥ C max, and is a NP-hard problem [9], where Pm denotes identical machines in parallel, Cmax denotes makespan (the maximum completion time), defined as Eq. (1)
where Ci denote the completion time of the machine i and Cmax is equivalent to the completion time of the last job.
We propose a greedy approach to solve TWCA problem. The greedy approach chooses one file at a time and determines corresponding wavelength channel and timeslots for the file transfer. We describe two sorting schemes for choosing a file, and three scheduling algorithms such as The Least File-Load first (LFL), The First-Fit first (FF) and The Best-Fit first (BF) for determining the best schedule for the file.
4.1 Heuristics for Choosing the File
1) The Longest File First (LFF) scheme:
The approach is based on the intuition that the smaller file is, the more flexible and effective file is to balance the transmission load on all channels. It reorders N independent files based on the size or transfer time of files in the file list and places the smaller files toward the end of the schedule.
2) The First-Come First-Service (FCFS) scheme:
The approach reorders N independent files in the file list based on release time Ri of each file. The approach eliminates the files sorting process, reduces transfer latency for shorter files and is also suitable for on-line scheduling scenario.
4.2 Algorithms for Determining Wavelength Channel and Timeslots
1) The Least File-Load first (LFL)
LFL assigns firstly the M files from the file list to the M channels. After that, whenever a channel is free, the next file in the file list is put on the channel until the last file is scheduled. The algorithm attempts to balance the traffic load among all the wavelength channels. It is noted that the global information is required to compute the least-load wavelength in this algorithm.
2) The First-Fit first (FF)
FF firstly establishes a lower bound (LB) on the completion time of an optimal solution for TWCA, simply calculated as Eq. (2). The LB is the average transfer time of N independent files on the M wavelength channels, which ideally consider the file dividable infinitely.
All wavelengths are numbered. The lower-numbered wavelength is considered before a higher-numbered wavelength. Each file is then taken in turn from the above list and allocated to the first channel onto which it will fit without exceeding the LB. If the file will not fit onto any channel with exceeding this value LB, it is allocated to the least loaded channel. The algorithm has the less communication and computing overhead compared with the LFL and BF because no global information is required.
3) The Best-Fit first (BF)
BF similarly allocates each file in turn from the above list, but instead of allocating it to the first channel on which it will fit. It is allocated to the channel on which it will fit ‘best’. The best channel has least load among non-empty channels and has enough gaps for the new file within the LB. If the file will not fit onto any channel with exceeding this value LB, it is allocated to the least loaded channel. It is same that the algorithm requires the global information to compute the ‘best’ wavelength.
4.3 Numerical Results
To show the benefits of dynamic scheduling of upstream wavelength, we perform simulations by comparing the proposed DWS-HPON with a conventional TDM-over-WDM PON in terms of the maximum completion time for data aggregations from all ONUs to OLT. The simulations are performed in a 16-ONUs PON. In the case of TDM-over-WDM PON, they are grouped into 4 sub-PONs. Each sub-PON contains 4 ONUs and has a dedicated upstream wavelength. In the DWS-HPON, 16 ONUs share 4 upstream wavelengths. The number of slots for each file from each ONU follows a negative exponential distribution with the mean value of 10 slots, and the slot duration and the data rate are assumed to be 2s and 2.5 Gb/s, respectively. The network traffic load, which is defined as the ratio of the traffic slots to the total amount of traffic slots and interval slots, is varied from 0.1 to 0.9. It simulates different amount of the files from different ONUs in upstream transmission.
Figure 8 compares the performance of two sorting scheme: 1) the First-Come First-Service (FCFS) and 2) the Longest File First (LFF) for three scheduling algorithms. As we expect, since the LFF scheme schedules larger files earlier on a channel, and then fills up the gap left with the smaller jobs, which leads to files of different sizes are effectively combined on a channel and finally well balances transmission load on all channels. The less maximum completion time is exhibited than those using First-Come First-Service (FCFS) scheme.
Fig. 9. Performance comparison of the there scheduling algorithms in the proposed PON with the conventional TDM-over-WDM PON based on the LFF scheme
Figure 9 shows the performance of the three scheduling algorithms based on the LFF scheme in the DWS-HPON, compared with the conventional TDM-over-WDM PON. The maximum completion time does not vary much with the network load for LFL, FF and BF algorithms, but significantly outperforms the conventional PON, which is primarily due to the sharing and flexible scheduling of wavelength resource among all ONUs. We also note that BF algorithms is clearly more complex than FF, but, surprisingly, BF performs slightly worse than FF. The difference is more perceptible when the network load becomes heavier. An interesting trend is the performance of LFL compared with FF. For the lower network load, LFL performs slightly better than FF. As the network load becomes heavier, FF’s performance also improves, and eventually surpasses LFL. This is possibly attributed to the following reason. When the network load is lower, the number of files is small, and FF could not find well-balanced solutions among all available channels. With the increasing network load, the number of files of different size is much more than that of channels, which helps in equally distributing files into all channels. Therefore, we conclude that LFF-FF algorithm should be the preferred one with the less communication and computing overhead, especially for the heavier network load.
5. Conclusions
In this work, we propose and experimentally demonstrate a novel DWS-HPON for distributed computing applications. The property of dynamic wavelength scheduling is implemented by using spectrum slicing techniques of broadband light source and overlay broadcast-signaling scheme. And we define the Time-Wavelength Co-Allocation (TWCA) Problem for large data aggregation from geographical distributed ONUs in the proposed DWS-HPON and present an effective greedy approach (LFF-FF) to solve this problem. The significant improvement in the maximum completion time is shown compared with the conventional TDM-over-WDM PON.
Acknowledgement
This work is jointly supported by NSFC with grant No. 60672016, 60632010, 60572029, and 60825103, and the National 863 Program of China.
References and links
1. F. An and D. Gutierrez. “SUCCESS-HPON: A next-generation optical access architecture for smooth migration from TDM-PON to WDM-PON,” IEEE Communications Magazine 43, 40–47 (2005). [CrossRef]
2. G. Talli and P. D. Townsend. “Hybrid DWDM-TDM Long-Reach PON for Next-Generation Optical Access,” J. Lightwave Technol. 24, 2827–2834(2006). [CrossRef]
3. S. Mun, S. Lee, K. Okamoto, and C. Lee, “A multiple star WDM-PON using a band splitting WDM filter,” Opt. Express 16, 6260–6266(2008) [CrossRef] [PubMed]
4. Y. Shachaf, C. H. Chang, and P. Kourtessis, “Multi-PON access network using a coarse AWG for smooth migration from TDM to WDM PON,” Opt. Express 15, 7840–7844(2007) [CrossRef] [PubMed]
5. T. DeFanti, C. D. Laat, J. Mambretti, K. Neggers, and B. S. Arnaud, “TransLight: A Global-Scale LamdaGrid for e-Science,” IEEE Communications of ACM 46, 34–41(2003) [CrossRef]
6. W. Guo, Y. Jin, W. Sun, W. Hu, X. Lin, M. Wu, H. Liu, S. Fu, and J. Yuan, “Distributed Computing over Optical Networks,” in Optical Fiber Communication Conference and Exposition and The National Fiber Optic Engineers Conference, OSA Technical Digest (CD) (Optical Society of America, 2008), paper OWF1, http://www.opticsinfobase.org/abstract.cfm?URI=OFC-2008-OWF1. [PubMed]
7. A. Banerjee and W. Feng, “Algorithms for Integrated Routing and Scheduling for Aggregating Data from Distributed Resources on a Lambda Grid,” IEEE Transactions on Parallel and Distributed System 19, 24–34 (2008). [CrossRef]
8. A. J. Page, L. Ahrenberg, and T. J. Naughton, “Low memory distributed reconstruction of large digital holograms,” Opt. Express 16, 1990–1995(2008) [CrossRef] [PubMed]
9. M. Garey and D. Johnson, “Computers and Intractability: A guide to the theory of NP-Completeness,” W. H. Freeman, (San Francisco, 1979).
