Multiplex communications – Communication techniques for information carried in plural... – Adaptive
Reexamination Certificate
2000-10-12
2004-10-12
Pham, Chi (Department: 2663)
Multiplex communications
Communication techniques for information carried in plural...
Adaptive
Reexamination Certificate
active
06804255
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field of the Invention
The present invention relates generally to optical routing and scheduling of data packets, and more specifically to an optical routing and scheduling of data packets employing a void filling algorithm and fiber delay lines (FDLs) as an optical buffer.
2. Discussion of the Related Art
One of the major trends in networking in late 1990's has been a relentless growth in demand for bandwidth in both enterprise and service provider networks. Driving the need for more bandwidth is a combination of factors. More users are connecting as the commercial Internet offers a new online experience for consumers. Internet computing applications, including multi-tier distributed databases, interactive multimedia communication, and electronic commerce rely on the network and demand network resources. A new generation of high-speed Internet access is emerging to meet bandwidth demands and further amplify core bandwidth requirements.
At the same time, competitive pressures make it imperative that networking costs be reduced even as the demand for capacity and new services increases. Successful companies are constantly on the lookout for new technologies which can provide a competitive edge and increase their cost effectiveness.
Optical networking has emerged as a solution to the bandwidth crunch. In particular, one new optical technology—Dense Wavelength Division Multiplexing (DWDM)—promises to increase the capacity and performance of existing fiber optic backbones. DWDM offers a capacity upgrade solution with greater scalability and lower cost than available alternatives.
Wavelength Division Multiplexing (WDM) is a technique for increasing the information-carrying capacity of optical fiber by transmitting multiple signals simultaneously at different wavelengths (or “colors”) on the same fiber. In effect, WDM converts a single fiber into multiple “virtual fibers,” each driven independently at a different wavelength. Systems with more than a small number of channels (two or three) are considered Dense WDM (DWDM) systems. Nearly all DWDM systems operate across a range of wavelengths in the 1550 nm low-attenuation window.
A DWDM system generally includes optical transmitters (lasers), an optical multiplexer and an demultiplexer, optical amplifiers and optical receivers. DWDM systems use high resolution, or narrowband, lasers transmitting in the 1550 nm wavelength band.
The optical multiplexer combines the transmit signals at different wavelengths onto a single optical fiber, and the demultiplexer separates the combined signal into its component wavelengths at the receiver. Several technologies are currently used for optical multiplexing and demultiplexing, including thin-film dielectric filters and various types of optical gratings. Some (de)multiplexers are constructed as completely passive devices, meaning they require no electrical input. Passive optical (de)multiplexers behave essentially like very high precision prisms to combine and separate individual colors of the WDM signal.
The optical receiver is responsible for detecting an incoming lightwave signal and converting it to an appropriate electronic signal for processing by the receiving device. Optical receivers are very often wideband devices able to detect light over a relatively wide range of wavelengths from about 1280-1580 nm. This is the reason why some seemingly incompatible devices can actually inter-operate. For instance, directly connecting two otherwise compatible network interfaces with different transmitter wavelengths is usually not a problem, even though one end may be transmitting at 1310 nm and the other at 1550 nm.
An additional benefit of the optical amplifier is that as a strictly optical device, it is a protocol- and bit rate-independent device. In other words, an optical amplifier operates the same way regardless of the framing or bit rate of optical signals. This allows a great deal of flexibility in that an optically amplified link can support any combination of protocols (e.g. ATM, SONET, Gigabit Ethernet, PPP) at any bit rate up to a maximum design limit.
With the deployment of DWDM optical fiber transmission systems to accommodate the ever increasing demand for bandwidth, driven by Internet applications, routers/switches are still likely to be the bottleneck of the next generation of Internet backbones. Using the DWDM technology, one can already achieve the transmission capacity of 320 Gbps per fiber commercially. The need for extremely high capacity routers, in the range of one terabits per second (Tbps) and beyond, is expected in the near future.
Optical burst switching (OBS) is an attractive technology in building tera-bit optical routers and realizing the Internet Protocol (IP) over dense wavelength division multiplexing (DWDM). An intrinsic feature of OBS is the separate transmission and switching of data bursts
150
(payload) and their headers
155
(called burst header packets (BHP)) on data and control channels/wavelengths, respectively. Due to the lack of an optical RAM (random access memory), fiber delay lines (FDLs) are used in optical routers to resolve burst conflicts on outbound data channels. In a simplified optical router architecture with N input fibers and N output fibers each fiber has one data channel group (DCG) of (K−1) channels and one control channel group (CCG) of one channel.
For optical routers using FDL buffering, there is a scheduler for each outbound DCG which schedules the arriving data bursts
150
that are to be routed to the same outbound DCG. The scheduler is a key component in the switch control unit. Any channel scheduling algorithm used in the scheduler will directly affect the router performance in terms of throughput and burst loss ratio. The prior art has not produced channel scheduling algorithms capable of providing acceptable throughput and burst loss ratio.
What is needed are sophisticated channel scheduling algorithms incorporating void filling in order to achieve the desired router performance. For any scheduling algorithm with void filling, each scheduler needs to keep track of the busy/idle periods of every data channel of its associated outbound DCG. The scheduler searches for an eligible void/gap when scheduling an arriving data burst. The search has to be done very quickly, e.g., in the range of a few hundred nanoseconds (say 100-300 ns), as the data burst is transmitted at the speed of light. As the number of channels handled by the scheduler increases, so does the complexity of the scheduler.
A scheduler that has to maintain the hardware implementation of a scheduling algorithm with void filling is a technically challenging endeavor, given the stringent real-time requirements and the state information of each data channel.
Various channel scheduling algorithms with and without void filling have been proposed such as the Latest Available Unused Channel (LAUC) algorithm, (also called the Horizon algorithm) and the Latest Available Unused Channel with Void Filling (LAUC-VF) algorithm (and variations on that theme), and other void filling scheduling algorithms. In terms of router performance (burst loss ratio) simulation studies have shown that the LAUC-VF is probably one of the best among all the scheduling algorithms. Despite the studies and the need for such algorithms, no hardware implementation design is available to implement these algorithms.
SUMMARY OF THE INVENTION
Accordingly the present invention provides a scheduling algorithm incorporating void filling and a hardware implementation design capable of implementing the algorithm wherein the desired performance is capable of scheduling a data packet in no more than a few hundred nanoseconds.
The present invention has been made in view of the above circumstances and has as an object to employ a special-purpose parallel processing architecture in the design of the scheduler to meet the stringent real-time requirements. Specifically, the present invention contemplates the use of an associative memory to store the state information of
Vandenhoute Marc L. J.
Xiong Yijun
Zheng Si Qing
Alcatel
Cary Gray
Ferris Derrick W
Pham Chi
Sewell V. Lawrence
LandOfFree
Hardware implementation of channel scheduling algorithms for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware implementation of channel scheduling algorithms for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware implementation of channel scheduling algorithms for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3319550