Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
2000-06-23
2004-04-27
Qureshi, Afsar (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S395400, C370S468000, C359S199200, C398S049000, C398S177000
Reexamination Certificate
active
06728212
ABSTRACT:
FIELD OF INVENTION
This invention is related to the field of apparatuses and methods for scheduling the flow of packets. More particularly, it relates to the use of a scheduler for filling voids.
BACKGROUND OF INVENTION
Presently, void filling schedulers utilize only one scheduler operating over the entire set of available wavelengths. (A void is a gap or idle period/pattern of determined time length, appearing at the distribution of packets at the output fields of a switch/router. It essentially represents an absence of packets at the output). Assignment of wavelengths is done in the following manner. Assume that there are N wavelengths available on a certain link. Next, assume that the traffic load per wavelength and traffic overall is &rgr;. In addition, assume that there is one scheduler. The scheduler will schedule use of the packets over all N wavelengths, in effect performing interleaving over all the possible wavelengths. This is depicted in
FIG. 1
a
where it is visible that the scheduler operates over all the wavelengths.
Another example of a void filling scheduler is disclosed in U.S. patent application Ser. No. 09/253,309, Optical Fiber-Delay Line Buffers With Void Filling, filed Feb. 19, 1999 and hereby incorporated by reference. It discloses the use of fiber-delay line buffers that incorporate a void filling procedure.
However, to substantially reduce excess load and increase efficiency using present void filling schedulers, large electronic memories are needed to store large numbers of existing voids ready to be filled. Hence, increased efficiency can only be obtained at the expense of a large increase in the complexity of the void filling scheduling method. In addition, inspecting large number of voids to find out whether a packet can be scheduled in an existing void is very time consuming. Hence, increasing the efficiency entails slowing the speed of the scheduler. Therefore, there is a trade off between complexity and efficiency when using only one scheduler.
SUMMARY OF THE INVENTION
The present invention is a method and apparatus for scheduling packets, comprising a plurality of schedulers connected in parallel and a packet divider/classifier circuit operably connected to the plurality of schedulers.
In another embodiment, the invention is an apparatus for scheduling packets, comprising a packet divider/classifier circuit, a plurality of input fibers operably connected to an input of the packet divider/classifier; and a plurality of schedulers connected in parallel. The plurality of schedulers are operably connected to an output of the packet divider/classifier circuit. Furthermore, at least one of the plurality of schedulers comprises at least one buffer. In addition, buffer monitor circuitry is operably connected to the plurality of schedulers. In a preferred embodiment, the buffers are fiber-delay line buffers.
In still another embodiment, the invention comprises a method of asymmetrically allocating bandwidth, comprising the steps of dividing a bandwidth into available wavelengths and assigning the available wavelengths to a plurality of schedulers, wherein at least one of the plurality of schedulers is assigned a different number of wavelengths than another of the plurality of schedulers.
In yet still another embodiment, the invention comprises a method and apparatus of bandwidth grabbing or dynamic bandwidth allocation in which buffer occupancy of at least one of a plurality of schedulers is monitored and at least one packet is redirected to a scheduler having a buffer occupancy below a threshold.
REFERENCES:
patent: 5416769 (1995-05-01), Karol
patent: 5469284 (1995-11-01), Haas
patent: 5486943 (1996-01-01), Sasayama et al.
patent: 5734486 (1998-03-01), Guillemot et al.
patent: 5737106 (1998-04-01), Sansonetti et al.
patent: 6069894 (2000-05-01), Holender et al.
patent: 6169728 (2001-01-01), Perreault et al.
patent: 2002/0054732 (2002-05-01), Zheng
patent: 1030534 (2000-08-01), None
patent: 1 030 534 (2000-08-01), None
patent: 1 089 498 (2001-04-01), None
patent: WO 00/32008 (1999-11-01), None
patent: WO 00/32008 (2000-06-01), None
“A High-Speed Packet Switch Architecture With a Multichannel Bandwidth Allocation”; Kazuhiro Ohtsuki, et al.
“An Output-Buffered ATM Switch in the Multichannel Bandwidth Allocation Environment;” Wen De Zhong, et al., Electronics Communications in Japan, Part 1, vol. 74, No. 6, Jun. 1991; pp. 13-23.
“Multichannel Bandwidth Allocation in a Broadband Packet Switch”; Achille Pattavina; 8272 I.E.E.E. Journal on Selected Areas in Communications, vol. 6, No. 9, New York, NY; pp. 1489-1499.
“A New Scheduling Algorithm for Asynchronous, Variable Length IP Traffic Incorporating Void Filling”; Ljubisa Tancevski, et al.
“WDM Burst Switching for Petabit Data Networks;” Jonathan S. Turner; pp. WD2-1/47-WD2-3/49.
“WDM Burst Switching for Petabit Capacity Routers”, Yuhua Chen, et al.; 1999 IEEE; pp. 968-973.
“WDM Burst Switching”; Jonathan S. Turner; Proceedings of INET 99.
“ECOC 2000”; 26thEuropean Conference on Optical Communication; Proceedings vol. 2.
Qureshi Afsar
Sewell V. Lawrence
Smith Jessica W.
LandOfFree
Asymmetric void filling scheduler with bandwidth grabbing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Asymmetric void filling scheduler with bandwidth grabbing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymmetric void filling scheduler with bandwidth grabbing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205985