Method and apparatus for managing data traffic between a high capacity source and multiple destinations
View Patent ↗A method or system or apparatus provides improved digital communication. In one aspect, destination scheduling is performed by scheduling polling rather than scheduling data emissions. In particular aspects, a loop port scheduler assigns a weight and sequence number to each destination and scheduling polling of ports using these parameters.
1. A method of scheduling data transmission from a source to a plurality of destinations comprising:
performing weighted scheduling of polling to destinations;
assigning each destination a logarithmic weight value defining the relative rate at which the destination will be eligible to be polled;
wherein a destination's relative weight is equal to two raised to the maximum logarithmic weight minus said assigned logarithmic weight; and
transmitting data to destinations with successful polls using a shared transmit data buffer.
2. The method according to claim 1 further comprising:
using weighted interleaved round robin scheduling in conjunction with a weight spreader function to schedule polling.
3. The method according to claim 1 wherein said scheduling maintains fairness and reduces head-of-line blocking.
4. The method according to claim 1 further comprising:
assigning a weight value to help ensure that polled destinations have a high probability of being able to accept data.
5. The method according to claim 1 further comprising:
only polling destinations for which data is pending for transmission.
6. The method according to claim 1 further comprising:
assigning each destination a sequence value, with destination of the same weights being assigned to a roughly evenly distributed sequence values so that said sequence values evenly distribute polling of destinations of the same relative weight.
7. The method according to claim 6 wherein said scheduling does not require a particular assignment of destination identifications because sequence numbers are assigned independently of a destination identification.
8. The method according to claim 1 further comprising:
using a scheduler to cycle through a numerical sequence;
wherein a destination is eligible for polling if the destination has data queued and if a number n of LSBs of the destination sequence match the n LSBs of the master sequence number, where n is the destination's logarithmic weight value or where n equals zero.
9. The method according to claim 1 wherein said scheduling does not require a particular assignment of destination identifications because relative weights are assigned independently of a destination identification.
10. The method according to claim 1 further comprising:
receiving data to a plurality of destinations from a wide area network;
holding said data in queues in a queue controller; and
for destinations with successful polls, transmitting data from said queues to a transmit data FIFO.
11. The method according to claim 10 further comprising:
signaling from said queue controller to a polling scheduler an identification for destinations with pending data.
12. A method of cyclically outputting values encoded by a bit vector comprising:
determining a lowest active bit position value in said bit vector using a priority encoder;
outputting said lowest active bit position value;
feeding back said lowest active bit position value and said bit vector to a reset bit module for removing a bit at said lowest active bit position value; and
repeating said determining, outputting, and feeding back steps on a bit vector with said lowest active bit position reset until a terminal condition is reached.
13. The method according to claim 12 wherein said terminal condition is determined by:
determining a highest active bit position in said bit vector; and
comparing said lowest active bit position and said highest active bit position and when equal signaling that a last bit has been reached.
14. A traffic management device comprising:
a master sequence number that increments when a port selection cycle is completed;
a scheduler that reads polling parameters corresponding to port ids and selects ports for polling based on said parameters;
a poller for issuing polls to ports; and
a queue controller for emitting data units to ports that respond affirmatively to said polls;
wherein said parameters include a port active parameter and wherein ports are not selected if said port active parameters indicates there is no data to send to said port;
wherein ports are not selected if said port sequence parameter does not match a specified number of bits of said master sequence number.
15. The device according to claim 14 wherein said specified number is determined by a port weight parameter.
16. The device according to claim 15 further comprising:
a poll request FIFO for holding port ids of ports selected for polling.
17. The device according to claim 15 further comprising:
a transmit data FIFO for holding data to be transmitted to ports with successful polls.
18. The device according to claim 15 further comprising:
a queue controller with per port FIFOs for holding data yet to be scheduled for transmission to ports with successful polls.
19. A computer readable medium containing computer interpretable instructions describing a circuit layout for an integrated circuit that, when constructed according to said descriptions, will configure a circuit to embody the apparatus described in claim 14 .
20. A communication device comprising:
an ATM up-link module providing centralized traffic management for a plurality of access line cards;
a plurality of access line modules for connecting to a plurality of destinations;
an engine for per port flow control and cell emission scheduling of downstream traffic; and
a polling sequencer comprising:
a sequencer that scans a sequencing table identifying loop ports which are eligible for polling;
a Poll Request FIFO wherein portIDs of eligible loop ports are placed; and
a poller that uses said portIDs from said Poll Request FIFO to poll ports.
21. The device according to claim 20 further comprising:
wherein said polling requests asserted transmit packet available signals indicating ports to which cells may be transmitted.
22. A communications system comprising:
a plurality of loop port modems for exchanging data with a plurality of subscribers;
a traffic management device for handling flow control and traffic management between said plurality of subscribers and a wide-area-network;
a loop port scheduler that scans sequencing parameters, said parameters indicating loop ports that are eligible for polling and identifies port ids of ports eligible for polling;
a poller that uses said port ids to poll ports to detect ports ready to accept data: and
a wide area network interface accepting data from a wide area network into and transmitting said data to ports ready to accept data.