Open Access
Add to BibSonomyAbstract
We experimentally demonstrate a transmission scheduling algorithm to avoid congestion collapse in O-CDMA networks. Our result shows that transmission scheduling increases the performance of the system by orders of magnitude.
©2007 Optical Society of America
1. Introduction
The advances in optical long-haul transmission have shifted the bottleneck from the core network to metro and access networks. Due to their enormous bandwidth, optical access techniques are promising candidates as the high speed information highways, advocating the fulfillment of the future requirements of applications and Internet services of the next-generation on demand. Optical code division multiple access (O-CDMA) is one of the feasible techniques due to simplicity of the network control, fine channel granularity, and flexible bandwidth management [1,2].
A critical limitation of O-CDMA networks is the reduction of throughput when many users are simultaneously trying to transmit over a common medium, thus producing extreme congestion at high network loads. In fact, networks can suffer from “congestion collapse” in which the network’s throughput is degraded when traffic exceeds a threshold and it eventually approaches to zero under extremely high loads, i.e., when several users transmit simultaneously, their packets and hence their code-words overlap [3,4]. When the optical pulses in the codeword overlap, their power will be added, thus optical pulses from one codeword may be detected by other receivers tuned to other code-words. As a result, a receiver may incorrectly detect other users’ code-words, resulting in packet transmission errors [4]. These false positive errors increase with the offered load, resulting in congestion collapse. Recently, there has been a theoretical report on an O-CDMA network protocol called interference avoidance (IA) that helps managing congestion and maintains a relatively-high throughput even under extreme loads[4, 5]. Also] the stability and throughput of optical CDMA networks using various protocols are analyzed in [6]. They showed how the saturation throughput degrades with code sharing. In the context of packet radio networks, the throughput of a generic CDMA based packet switched network is analyzed [7]. To our knowledge, there have been no reports of experimental demonstrations of a network protocol that avoids congestion collapse for O-CDMA systems.
2. Interference Avoidance Algorithm
Figure 1(a) shows a shared medium operating based on packet-switched optical CDMA LAN in which several nodes are connected to a passive optical coupler to form an all optical broadcast network. The star coupler is a passive optical element with all inputs connected to all outputs. Each node on the network is allocated an optical CDMA codeword, which is a sequence of zeroes and ones that are transmitted asynchronously. When a node is ready to transmit, it tunes its transmitter to the receiver’s codeword and sends the data into the shared medium.
Without using a media access control protocol, each user transmits its data whenever the packet is ready. This is called Aloha-CDMA, which leads to congestion collapse in an O-CDMA network. The problem of throughput collapse in optical CDMA LANs is conceptually similar to the problem of throughput collapse in a single channel, shared medium networks. Single channel, shared medium networks without media access control (Aloha networks) suffer from throughput collapse at high offered load because of collisions between packets. Carrier Sensing Multiple Access (CSMA) and its variants [8] have been proposed as solutions to this problem.
In order to alleviate this problem, the use of a media access protocol “Interference Avoidance (IA)” is proposed. Interference Avoidance is a distributed, contention based Media Access Control (MAC) protocol for broadcast shared medium optical Code Division Multiple Access (CDMA) Local Area Networks (LANs). It improves network throughput at high offered load by estimating the state of the line and scheduling transmissions to reduce packet loss due to interference errors. IA is a contention media access control mechanism that prevents throughput collapse in optical CDMA networks at high offered load. It consists of state estimation and transmission scheduling.
State estimation is a process by which a node calculates an estimate of the state at a point on the line at some time using state observations obtained at some (possibly different) point on the line at some (possibly different) time. The estimated state is used as input to a transmission scheduling algorithm.
Transmission scheduling is the process by which a node, given an estimate of the state of the line and a codeword to transmit, calculates when to transmit the codeword such that packet losses due to interference errors are reduced.
Fig. 1. (a) O-CDMA network: The nodes are connected by transmit and receive (upstream, downstream) fibers to a passive star coupler to enable a shared medium LAN, (b) Block diagram of an Interference Avoidance(IA) network interface card (NIC)
A simplified block diagram of an O-CDMA node is also shown in Fig. 1(b). When a packet arrives on the receive fiber, it splits between two different paths. In one path, it is decoded by the optical CDMA receiver and written to the receive buffer. The other path is used to estimate the state of the link. The transmission scheduling algorithm calculates the appropriate transmission delay based on this information. After estimation of this delay, a scheduler tunes the tunable delay lines (TDLs) and signals the transmitter. The optical CDMA transmitter transmits the packet on the transmit fiber.
Fig. 2. Upper: link after the decoder of user of interest. Lower: the data is transmitted such that the autocorrelation is in the chip time with least interference
The concept of the state estimation and scheduling algorithm is shown in Fig. 2. To accomplish the state estimation we first pass the traffic from the line through the decoder of the user of interest. This is the traffic as it is seen by the receiver end. We then detect the date using multiple threshold detectors. The minimum interference detected here is the best position to transmit the autocorrelation peak. Now the transmission scheduler delays the packet so that the autocorrelation transmits in the designated chip-time “Minimum interference”. The transmission scheduler chooses the marked chip as the lowest MAI and then delays the packet and transmits the autocorrelation peak. It should be noted that as each packet consists of several bits, the state of the link remains constant for a long duration.
Fig. 3. (a) The normalized network throughput vs. normalized offered load for Aloha-CDMA and transmission scheduling. (a) Simulated traffic (b) Real traces of traffic from OC44 link. The throughput of the network does not collapse in high loads The traffic model is Poisson arrivals with exponentially distributed packet lengths.
In [3], an IA based optical CDMA network was modeled using discrete event based packet simulator The simulator modeled multiple nodes on a broadcast shared medium optical O-CDMA LAN. The normalized offered load is the arrival rate (in packets/s) expressed as a fraction of the maximum possible arrival rate (in packets/s) of the network when it is used as a single channel network. The arrival rate is defined as the aggregate rate at which packets arrive to all the nodes for transmission on the network. The normalized network throughput is the ratio of the number of packets that are transmitted over the network without error to the total number of packets offered for transmission multiplied by the normalized offered load. The result of the simulation is shown in Fig. 3(a). The results show that the as the offered load increases the throughput of Aloha-CDMA tends to zero, while the use of the transmission scheduling algorithm prevents throughput degradation. Figure 3(b) shows the congestion collapse when simulations were performed with traffic traces obtained from a real network link to understand the impact of real packet arrival times. Traffic traces from a single OC48 [9] link were used. Several of these traces were merged to generate traffic of different offered loads. The packet sizes, source addresses, and destination addresses were preserved during merging. The results indicate that the performance is similar to that of the Poisson arrivals/exponentially distributed model, indicating that it was a reasonable choice for analysis.
3. Experimental Results
The experimental setup for our O-CDMA system is shown in Fig. 4. We use eight equal space lasers, couple them together and modulate them at 10 Gchip/s. After an EDFA, we use O-CDMA encoder to encode the data and then use a variable delay line to vary the time delay of the user. Each encoder is based on an FBG technology which implements the splitting of the wavelengths and assigning each wavelength chip an appropriate timeslot. This data is transmitted through a short length of fiber and then combined in a star coupler with 5 other users. At the receiver, we amplify the received signal and use a second set of fiber delays to stack the chips to decode the data. At the receiver, a photo-receiver detects the decoded data followed by a threshold detector that samples the data to determine whether it exceeds a set decision threshold.
In our experiment we used the codes with 8 wavelength, 16 chip times, and code weight 6. Our codes are based on code construction function Plot B. [10] and they can support 18 potential users. Note That while the code set can support up to 18 users however having these many users in the system will drop the BER very drastically, this part is not the experimental limitation whereas it is the theoretical limitation of an O-CDMA network. Our code construction is optimal in terms of the number of code-sets and has at most one pulse per wavelength. The chip rate is 10 Gchip/s and the corresponding bit rate is 625 Mbit/s. Figure 5(a), (b), and (c) show the bit pattern of 10110 for 1, 3, and 6 users. The additional MAI is clear as the number of users increases. In Fig. 5(c) the MAI is very high as they are 6 users transmitting. From this figure it can be seen that by delaying out user of interest we can find a position to optimize the performance of the system.
Figure 5(d) shows the eye diagram of the autocorrelation function of a single user. The autocorrelation resembles an RZ signal with 1/16 ratio as there are 16 chip-times. Figure 5(e) shows the eye diagram of the main user along with multiple interferers. It is clear that by varying the transmission delay of this user, the autocorrelation can move to any point of time. In this case the position of the autocorrelation is optimized resulting in an open eye. Figure 5 (f) shows a random delay of the user which causes severe eye closure.
Fig. 5. (a) Bit pattern of 10110 for single user (b) 3 users (c) 6 users, (d) eye diagram of the correlation for single user (b) eye diagram of multiple user using transmission scheduling (c) random case eye diagram
Figure 6(a) shows the BER curves for increasing number of users. As we added more users to the network, we examined the link interference pattern and optimized the transmission delay of the user of interest. It is clear that using the optimized delay up to 6 users are recoverable with less than 4dB power penalty. To compare the performance of the IA algorithm with aloha CDMA, we first fixed the number of users and the state of the link. We then vary the delay of the user of interest to find the optimum delay which can achieve the BER of 1E-10 at the least possible optical power, at this point we fixed the optical power and changed the delay of different users to emulate different link state and then vary the user of interest delay to emulate the Aloha CDMA. The average BER resembles the Aloha-CDMA. The results are shown in Fig. 6(b). It should be noted that the respective point for different number of users are achieved for different optical power. Results show that in worst case the BER of system drops below 1E-3 for 5 and 6 users. Moreover using Aloha-CDMA the performance drops as the number of users increases in the network, while using IA algorithm we can maintain the desired performance for increasing number of users.
It is also important to mention that we are only scheduling the user of interest. This schedule depends on the statistics of other users, however in the experiment we changes the delay of all interferers and then left that at a random point and then by delaying the user of interest scheduled the measured the penalties. The other observation is that if each user tried to optimize itself, it may hurt the other users. Our simulation showed that although this may be partially through, at the equilibrium point the performance of all users could be better, thus avoiding the congestion collapse.
Fig. 6. (a) BER vs. received optical power of user 1 for increasing number of users, (b) performance of an O-CDMA system for increasing number of users with transmission scheduling, aloha-CDMA, and worst case
Acknowledgements
The authors wish to acknowledge the generous support of DARPA, SPAWAR for this work under contract number N66001-02-1-8939.
References and links
1. J. A. Salehi, “Code division multiple-access techniques in optical fiber networks—Part I: Fundamental principles,” IEEE Trans. Commun. 37, 824–833 (1989) [CrossRef]
2. P. Saghari, R. Omrani, A. E. Willner, and V. Kumar, “Analytical interference model for 2-dimentional (time-wavelength) asynchronous O-CDMA systems,” in Optical Fiber Communication Conference, Technical Digest (CD) (Optical Society of America, 2004), paper FG7. http://www.opticsinfobase.org/abstract.cfm?URI=OFC-2004-FG7
3. P. Saghari, R. Gholizadeh, H. Abrishami, E. Pakbaznia, J. E. McGeehan, S. M. R. M. Nezam, and A. E. Willner, “Experimental and theoretical analysis of the optimum decision threshold for varying numbers of active users in a 2-D time-wavelength asynchronous O-CDMA system,” J. Lightwave Technol. 23, 3339–3346 (2005) [CrossRef]
4. P. Kamath, J. D. Touch, and J. A. Bannister, “Algorithms for interference sensing in optical CDMA networks,” IEEE International Conference on Communications (ICC)3, 1720–1724 (2004)
5. P. Kamath, J. D. Touch, and J. A. Bannister, “The need for media access control in optical CDMA networks,” INFOCOM 4, 2208–2219 (2004)
6. Kumar and D. Patil, “Stability and throughput analysis of CDMAALOHA with finite number of users and code sharing,” Telecommunication Systems (a Baltzer Science Journal) 8, 257–275 (1997)
7. D. Raychaudhuri, “Performance analysis of random access packetswitched code division multiple access systems,” IEEE Trans. on Commun. 29, 895–901, (1981) [CrossRef]
8. F. A. Tobagi and V. B. Hunt, “Performance analysis of carrier sense multiple access with collision detection,” Computer Networks 4, 245–259 (1980)
9. NLANR, “Traffic traces from an OC48 link,” www.nlanr.net (2005)
10. R. Omrani and P. V. Kumar, “Improved constructions and bounds for 2-D optical orthogonal codes,” International Symposium on Information Theory (ISIT), (2005)
