Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2006-09-12
2006-09-12
Pham, Chi (Department: 2616)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S395400, C370S412000
Reexamination Certificate
active
07106693
ABSTRACT:
Methods and apparatuses are disclosed for pacing the rate at which packets of one or more information streams are sent from a device, such as, for example, a workstation, computer, communications mechanism, or component thereof. Typically, multiple timing wheels each having a different timing granularity are used to schedule the transmission of packets of information corresponding the to the information streams. Using multiple timing wheels in this manner allows scheduling of a larger range of rates while typically using a significantly smaller amount of memory than a single timing wheel covering the same range of rates. An entry, corresponding to a next portion of an information stream to be sent from the device, is inserted into the timing wheels at a target time for sending the information. At the target time, the entry is removed and placed in a transmit list of items to be sent from the device. In one implementation a single transmit list is used for all timing wheels. In another implementation, multiple transmit lists are used, typically one for each timing wheel. Entries corresponding to portions of the information streams to be sent from the device are removed in a queued or target transmission time order from a transmit list. A packet of information corresponding to a removed entry is sent, and the entry itself is re-inserted in a timing wheel for the determined next transmission target time.
REFERENCES:
patent: 4491945 (1985-01-01), Turner
patent: 4494230 (1985-01-01), Turner
patent: 4630259 (1986-12-01), Larson et al.
patent: 4630260 (1986-12-01), Toy et al.
patent: 4734907 (1988-03-01), Turner
patent: 4745593 (1988-05-01), Stewart
patent: 4829227 (1989-05-01), Turner
patent: 4849968 (1989-07-01), Turner
patent: 4893304 (1990-01-01), Giacopelli et al.
patent: 4901309 (1990-02-01), Turner
patent: 5027342 (1991-06-01), Boulton et al.
patent: 5127000 (1992-06-01), Henrion
patent: 5161156 (1992-11-01), Baum et al.
patent: 5173897 (1992-12-01), Schrodi et al.
patent: 5179551 (1993-01-01), Turner
patent: 5179556 (1993-01-01), Turner
patent: 5229990 (1993-07-01), Teraslinna
patent: 5229991 (1993-07-01), Turner
patent: 5253251 (1993-10-01), Aramaki
patent: 5260935 (1993-11-01), Turner
patent: 5265092 (1993-11-01), Soloway et al.
patent: 5339311 (1994-08-01), Turner
patent: 5402415 (1995-03-01), Turner
patent: 5471460 (1995-11-01), Tanabe
patent: 5475682 (1995-12-01), Choudhury et al.
patent: 5533020 (1996-07-01), Byrn et al.
patent: 5689500 (1997-11-01), Chiussi et al.
patent: 5768572 (1998-06-01), George et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5844890 (1998-12-01), Delp et al.
patent: 5848227 (1998-12-01), Sheu
patent: 6246665 (2001-06-01), Watanabe et al.
patent: 6343067 (2002-01-01), Drottar et al.
patent: 6366557 (2002-04-01), Hunter
patent: 6411599 (2002-06-01), Blanc et al.
patent: 6418115 (2002-07-01), Lino et al.
patent: 6424624 (2002-07-01), Galand et al.
patent: 6430150 (2002-08-01), Azuma et al.
patent: 6477168 (2002-11-01), Delp et al.
patent: 6654342 (2003-11-01), Dittia et al.
patent: 6674721 (2004-01-01), Dittia et al.
patent: 6728211 (2004-04-01), Peris et al.
patent: 6735173 (2004-05-01), Lenoski et al.
patent: 6747972 (2004-06-01), Lenoski et al.
patent: 6788689 (2004-09-01), Turner et al.
patent: 6816492 (2004-11-01), Turner et al.
patent: 6826186 (2004-11-01), Dittia et al.
Zubin Dittia, “Integrated Hardware/Software Design of a High Performance Network Interface,” Mar. 2000, Doctor of Science Thesis, Sever Institute of Technology, Washington University, St. Louis, Missouri, 139 pages.
Jonathan S. Turner, “An Optimal Nonblocking Multicast Virtual Circuit Switch,” Jun. 1994, Proceedings of Infocom, 8 pages.
Chaney et al., “Design of a Gigabit ATM Switch,” Feb. 5, 1996, WUCS-96-07, Washington University, St. Louis, MO, 20 pages.
Turner et al., “System Architecture Document for Gigabit Switching Technology,” Aug. 27, 1998, Ver. 3.5, ARL-94-11, Washington University, St. Louis, MO, 110 pages.
George Varghese and Anthony Lauck, “Hashed and Hierarchical Timing Wheels: Efficient Data Structures for Implementing a Timer Facility”, IEEE/ACM Transactions on Networking, vol. 5, No. 6, Dec. 1997, pp. 824-834.
U.S. Appl. No. 09/705,450, filed Nov. 2, 2000, Turner et al.
U.S. Appl. No. 09/784,787, filed Feb. 15, 2001, Turner et al.
U.S. Appl. No. 09/519,282, filed Mar. 7, 2000, Lenoski et al.
U.S. Appl. No. 09/949,125, filed Sep. 7, 2001, Dejanovic et al.
Cox Jerome R.
Turner Jonathan S.
Cisco Technology Inc.
Jagannathan Melanie
Pham Chi
The Law Office of Kirk D. Williams
Washington University
LandOfFree
Method and apparatus for pacing the flow of information sent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for pacing the flow of information sent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for pacing the flow of information sent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3610412