Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
2005-10-11
2005-10-11
Dang, Khanh (Department: 2111)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S316000
Reexamination Certificate
active
06954811
ABSTRACT:
An arbiter for a switch maintains a pair of counters for each flow of traffic at each input port: one counter (also called “first counter”) to indicate an ideal transfer of traffic, and another counter (also called “second counter”) to indicate the actual transfer of traffic. Both counters are incremented when traffic is received by the input port, and the second counter is decremented when a unit of traffic (such as a cell or packet) is about to be transmitted whereas the first counter is decremented in a fractional manner (relative to the unit of traffic) in each period of arbitration, based on available bandwidth. The arbiter selects one of the output ports (also called “winning output port”) of the switch, based at least partially on values of the two counters for each flow from the input port to one of the output ports, and generates a signal to approve transfer of traffic from the input port to the winning output port. In several embodiments, the above-described flow can be for either high priority traffic or for low priority traffic, and any bandwidth leftover from transferring high priority traffic is used in transferring low priority traffic. Specifically, the arbiter maintains additional counters for each port indicative of total bandwidth being used, and the additional counters are used to allocate leftover bandwidth in an iterative manner, until a flow from an input port to an output port is saturated, at which time the saturated flow is removed from iteration.
REFERENCES:
patent: 5119367 (1992-06-01), Kawakatsu et al.
patent: 5295135 (1994-03-01), Kammerl
patent: 5455826 (1995-10-01), Ozveren et al.
patent: 5471632 (1995-11-01), Gavin et al.
patent: 5500858 (1996-03-01), McKeown
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5604867 (1997-02-01), Harwood
patent: 5634004 (1997-05-01), Kurshan et al.
patent: 5710549 (1998-01-01), Horst et al.
patent: 5741632 (1998-04-01), Kiekens
patent: 5828878 (1998-10-01), Bennett
patent: 5859835 (1999-01-01), Varma et al.
patent: 5923644 (1999-07-01), McKeown et al.
patent: 5982771 (1999-11-01), Caldara et al.
patent: 6014367 (2000-01-01), Joffe
patent: 6072800 (2000-06-01), Lee
patent: 6134217 (2000-10-01), Stiliadis et al.
patent: 6160812 (2000-12-01), Bauman et al.
patent: 6185221 (2001-02-01), Aybay
patent: 6262986 (2001-07-01), Oba et al.
patent: 6327253 (2001-12-01), Frink
patent: 6385678 (2002-05-01), Jacobs et al.
patent: 6389031 (2002-05-01), Chao
patent: 6389480 (2002-05-01), Kotzur et al.
patent: 6501731 (2002-12-01), Chong et al.
Office Action dated Sep. 28, 2004 in EP Application No. 03254534.5-2416 based on U.S. Appl. No. 10/199,996 (5 pages total excluding cover sheet).
Search Report dated Oct. 15, 2003 in EP Application No. 03254534.5-2416 based on U.S. Appl. No. 10/199,996 (2 pages total excluding cover sheet).
“The iSLIP scheduling algorithm for input-queued switches,” by N. W. McKeown in IEEE/ACM Transactions on Networking, vol. 7, No. 2, Apr. 1999.
T. Anderson, S. Owicki, J. Saxe and C. Thacker, “High Speed Switch for Local Area Networks”, ACM Transactions on Computer Systems, vol. 11, No. 4, Nov. 1993 pp. 1-13.
N. W. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick and M. Horowitz, “The tiny tera: A packet switch core”, Hot Interconnects V., Aug. 1996, pp. 1-13.
A. Parekh, R. Gallager, “A Generalized Processor Sharing Approach To Flow Control in Integrated Services Networks: The Multiple Node Case”, IEEE/ACM Transaction On Networking, vol. 2, No. 2, Apr. 1994, pp. 136-151.
A. Parekh, R. Gallager, “A Generalized Processor Sharing Approach To Flow Control in Integrated Services Networks: The Single Node Case”, IEEE/ACM Transaction On Networking, vol. 1, No. 2, Jun. 1993, pp. 344-357.
D. Stiliadis, A. Varma, “Efficient Fair-Queuing Algorithms for Packet-Switched Networks”, IEE/ACM Transaction On Networking, vol. 6, No. 2, 1998, Article No. 27473, pp. 1-11 and B.1-B.2.
M. Goureau, S. Kolliopoulos, S. Rao, “Scheduling Algorithms for Input-Queued Switches: Randomized Techniques and Experimental Evaluation”, IEEE/Infocom 2000, pp. 1634-1643.
J. Bennett, Hui Zhang “Why WFQ Is Not Good Enough For Integrated Services Networks”, 1996, pp. 1-8.
N. McKeown, A. Mekkittikul, V. Anantharam, J. Walrand, “Achieving 100% Throughput in an Input-Queued Switch”, IEEE Transaction Communications, vol. 47, No. 8, Aug. 1999, (22 pages).
I. Stoica, S. Shenker, H. Zhang, “Core-Stateless Fair Queuing: Achieving, Approximately Fair Bandwidth Allocations in High Speed Networks”, Http://www-2.cs.cmu.edu/˜istoica/sig98talk/, 1998, pp1-20.
N. KcKeown, “Scheduling Algorithms for Input-Queued Cell Switches”, ©1995, pp. 1-119.
R. Schoenen, “An Architecture Supporting Quality-of-Service in Virtual-Output-Queued Switches”, iEICE Transaction Communications, vol. E83-B, No. 2, Feb. 2000, pp. 1-10.
M.J.G. van Uitert, S.C. Borst, “A Reduced-Load Equivalence For Generalized Processor Sharing Networks With Heavy-Tailed Input Flows”, Probability, Networks and Algorithms (PNA), PNA-R007, Aug. 31, 2000, pp. 1-37.
N. Joy, K. Jamadagni, “Optimal Call Admission Control in Generalized Processor Sharing (GPS) Schedulers”, IEEE Infocom 2001, pp. 1-10.
D. Stiliadis, A. Varma, “Rate-Proportional Servers: A Design Methodology for Fair Queuing Algorithms”, UCSC-CRL-95-58, Dec. 1995, pp. 1-22 and A.1-A.4.
D. Staliadis, A. Varma, “Latency-Rate Servers: A General Model for Analysis of Traffic Scheduling Algoriths”, IEEE/ACM Transactions of Networking, vol. 6, No. 5, Oct. 1998, pp. 611-624.
M. Vishne, “Implementing VirtualClock without Cell Stamps”, IEEE Communications Letters, 1997, pp. 1-3.
M. Vishne, J. Mark, “A Flexible Service Scheduling Scheme for ATM Networks”, DBLP Record conf/infocom/VishnuM96, 1996, pp. 647-654.
M. Vishne, J. Mark, “Reference Queue Tracking Strategies for Delay Guarantees in ATM Networks”, Nov. 4, 1997, pp. 1-22.
M. Vishne, J. Mark, “Reference Queue Tracking Strategies for Delay Guarantees in ATM Networks”, Nov. 22, 1999, pp. 1-18.
M. Vishne, J. Mark, “HOL-EDD: A Novel Service Scheduling Scheme for ATM Networks”, Jun. 16, 1997, pp. 1-23.
Calix Networks, Inc.
Dang Khanh
Silicon Valley Patent & Group LLP
LandOfFree
Arbiter for an input buffered communication switch does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbiter for an input buffered communication switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbiter for an input buffered communication switch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3445638