Space efficient fair queuing by stochastic Memory multiplexing

Details Space efficient fair queuing by stochastic Memory multiplexing Space efficient fair queuing by stochastic Memory multiplexing

1997-08-05

1999-09-21

Kizou, Hassan

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

710 56, H04L 1228

Patent

active

059563400

ABSTRACT:
A method for multiplexing the buffer space used to store messages of backlogged flows at the output port of a switch. The buffer space is partitioned among queues of variable length, with the first queue long enough to accommodate the largest expected backlog, the second queue long enough to accommodate the second-largest expected backlog, etc. Messages are dequeued from the queues for transmission in Round-Robin order. Incoming messages are enqueued in a manner that guarantees that messages of heavily backlogged flows tend to be enqueued in the longer queues, while preserving FIFO message order. If the messages are all of the same length, then the queues are partitioned into locations, of the same length as the messages, each location having an ordinal index in its queue, and the messages are enqueued so that each message of a particular flow is enqueued in a location with a different ordinal index. If the messages are of different lengths, the queues are partitioned into bins large enough to accommodate the longest messages, one or more messages may be stored in each bin, the round in which each incoming message is to be transmitted is computed in advance, and a similar enqueueing algorithm is used that is based on matching successive transmission rounds of messages of a given flow to successively indexed bins of different queues. The present invention may be used in any application involving Round Robin scheduling.

REFERENCES:
patent: 5381413 (1995-01-01), Tobagi et al.
patent: 5732087 (1998-03-01), Lauer et al.
patent: 5859835 (1999-01-01), Varma et al.
Jain, R., "Congestion Control and Traffic Management in ATM Networks: Recent Advances and a Survey", Computer Networks and ISDN Systems, Feb. 1995.
Demers et al., "Analysis and Simulation of a Fair Queueing Algorithm", Proc. SIGCOMM. pp. 1-12, (1989).
Kung et al., Credit-Based Flow Control for ATM Networks, IEEE Networks, 9(2): 40-48 (1995).
McKenney, P. "Stochastic Fairness Queueing", Internetworking: Research and Experience, 2:113-131 (1991).
Nagle, J., "On Packet Switches with Infinite Storage", IEEE/ACM Trans. On Communications, 35(4): 535-438, (1987).
Keshav, S., "A Control-Theoretic Approach to Flow Control", Proc. SIGCOMM, pp. 3-16 (1991).
Shreedhar et al., "Efficient Fair Queueing Using Deficit Round Robin", IEEE/ACM Trans. On Networking, 4(3):375-385 (1996).

Affiliated with

Also associated with

Rating

Space efficient fair queuing by stochastic Memory multiplexing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Space efficient fair queuing by stochastic Memory multiplexing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space efficient fair queuing by stochastic Memory multiplexing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-87060