With the advances of modern computer architectures, interconnects are playing an ever increasingly important role for providing an effective communication medium. Advanced optical switching technologies, such as optical packet switching and wavelength-division-multiplexing, provide a platform to exploit the huge capacity of optical fiber to meet the increasing needs. This research proposes a new switching paradigm - optical cut-through with electronic packet buffering, and systematically investigates the fundamental and challenging issues in the optical interconnect under this switching scheme, with the objective of designing cost-effective, ultra-low latency and pragmatic interconnects for future high-performance computing and communications systems.
A unique feature of the proposed interconnect is that those packets that do not cause contention can pass the interconnect directly in optical form and experience minimum delay, while only those that cause contention are buffered. This research proposes to combine optical packet switching with electronic buffering, such that the interconnect will enjoy both fast switching and large buffering capacity. This research will (1) design the switching fabric and packet scheduling algorithms, (2) design practical Forward Error Control (FEC) for the interconnect, and (3) conduct extensive performance evaluations by means of simulation and emulation tools and analytical models. The outcome of this project will have a significant impact on fundamental design principles and infrastructures for the development of future high-performance computing and communications systems. The PIs will integrate graduate and undergraduate students into the project and promote the participation of female and minority students. The findings will be disseminated to the research community by way of conferences, journals, and web site access.
In this project, we have studied a novel architecture for optical packet switching networks, referred to as OpCut. In communication networks, data is encapsulated and transferred in units called packets. OpCut is ideally suited for the data communication in high performance computers, where programs run in parallel in many processors such that the communication speed between the processors often determines the computation time. OpCut has two key features: 1) it combines optical switching with electronic buffering to exploit both the fast speed of optics and the large buffering capacity of electronic devices, and 2) whenever possible, it allows a packet to cut-through the switch to output side without being converted to electronic signals to reduce data latency. These features enable OpCut to transfer large amount of data very quickly while introducing very small latency to the data. To unleash the true capacity of the OpCut switch, the key issue is to make intelligent decisions on packet transfer. A packet scheduling algorithm must be employed to determine which packets to be transferred and which to stay, in case multiple packets are destined to the same output port. The challenge is that such packet scheduling algorithms must converge to a schedule very quickly, i.e., in the order of ten nanoseconds, which is the time to transfer one packet inside the switch often called a time slot. As a result, the scheduling algorithm must be implementable in hardware. In addition, the scheduling algorithm must exploit the unique hardware architecture of OpCut, which is very different from existing switches. We have designed efficient packet scheduling algorithms for the OpCut switch. Speaking from a high level, we find that two schedulers running parallel deliver desirable performance, where one scheduler determines how to direct the packets to the buffers, and the other scheduler determines how to direct packets to the output ports. We also find that the first scheduler can be very simple, i.e., may simply direct the packets to the buffer in a round-robin manner, and the main challenge is the second scheduler. We have proposed a pipelined solution for the second scheduler, which divides the task into smaller sub-tasks, each taken care of by one sub-scheduler. Basically, each sub-scheduler takes the partial schedule calculated by the sub-scheduler of lower order and augments the schedule with more packet transmissions. The advantage is that each sub-task is much simpler than the original task, and can be solved more efficiently within a time slot. The caveat, however, is that the sub-schedulers run independently and may give conflicting schedules, i.e., a packet may be scheduled twice, called "duplicate scheduling." While duplicate scheduling is usually difficult to analyze, we are able to rigorously prove that it does not occur with our algorithm when two sub-schedulers are used; we also propose several approaches to reduce it when the number of sub-schedulers is more than two. We also propose a technique called "adaptive pipelining" to reduce the packet latency when the traffic load is low. Basically, when the traffic is low, the scheduling problem is simple and fewer sub-schedulers may suffice such that the packets may experience less delay. This work was first presented in IEEE Infocom 2011, a top conference in the field of computer networking, and an extended version has been published in the June 2012 issue of IEEE Journal of Lightwave Technology. We have also designed algorithms for the OpCut switch with multiple wavelengths per fiber. The capacity of an optical packet switching network is improved when the bandwidth of an optical fiber is better utilized with multiple wavelengths carrying packets in parallel. The packet scheduling problem with multiple wavelengths is even more challenging than with a single wavelength, because multiple packets may arrive at an input fiber simultaneously and the orders of such packets must be maintained. We prove that the optimal scheduling problem is NP-hard, i.e., mathematically intractable. We further prove that the scheduling problem cannot be approximated within a constant factor. Therefore, we propose a set of practical scheduling algorithms and our simulations show that they achieve good performance in typical conditions. This work was first presented inIEEE Infocom 2011 and an extended version is currently under preparation for journal submission. Overall, we have found that OpCut is an efficient switching architecture. With the good packet scheduling algorithms we have designed, it is capable of achieving higher throughput and lower packet latency than other switches at comparable cost. Therefore, OpCut advances our knowledge in developing future high-performance computing systems. Throughout this project, both PhD students and undergraduate students are involved in various research topics. Student from underrepresented groups, i.e., a female PhD student, has also participated in this project. The results of this project have been disseminated in conferences, journals, as well as on the professional website maintained by the PI.
