Fast credit system
View Patent ↗The invention provides an improved architecture for credit based flow control. Briefly, the memory space within the receiving switch is separated into two parts, a statically allocated portion and a dynamically allocated portion. Packets are first placed in the dynamically allocated portion, and the credits are returned immediately. When the dynamically allocated portion has no additional space, the packets are then stored in the memory portion statically allocated to the specific virtual circuit. Credits are returned when the packets are removed from the statically allocated memory portion. This scenario allows the immediate return of credits when there is space available in the dynamically allocated memory portion. It also allows improved sharing of the overall memory since more of the overall memory can be made available to a particular virtual circuit.
1. A switching device adapted to receive packets from a plurality of communication paths, comprising:
a first statically allocated memory element, adapted to store packets from one of said plurality of communication paths, and
a second dynamically allocated memory element, adapted to store packets from any of said plurality of communication paths; and
control logic adapted to transmit a flow control message to the sender of a packet after receipt of said packet, irrespective of said device's transmission of packets, if the received packet is stored in said second memory element.
2. The switching device of claim 1 , wherein said communication paths comprise virtual circuits.
3. The switching device of claim 1 , further comprising:
a linked list associated with one of said plurality of communication paths, whereby entries in said list are used to indicate the location of a packet stored in said first and second memory elements.
4. The switching device of claim 3 , further comprising:
a marker associated with each entry in said list indicating which of said memory elements said packet is stored.
5. The switching device of claim 4 , further comprising:
control logic adapted to send a flow control message to the sender of a packet after said packet has been removed from said memory element if said marker indicates that said packet was stored in said first memory element.
6. The switching device of claim 5 , wherein said communication paths comprise virtual circuits.
7. The switching device of claim 1 , further comprising:
a FIFO associated with one of said plurality of communication paths, whereby entries in said FIFO are used to indicate the location of a packet stored in said first and second memory elements.
8. The switching device of claim 7 , further comprising:
a marker associated with each entry in said FIFO indicating which of said memory elements said packet is stored.
9. The switching device of claim 8 , further comprising:
control logic adapted to send a flow control message to the sender of a packet after said packet has been removed from said memory element if said marker indicates that said packet was stored in said first memory element.
10. The switching device of claim 9 , wherein said communication paths comprise virtual circuits.
11. A network comprising a plurality of switching devices, adapted to transmit traffic among a plurality of communication paths, wherein each of said switching devices comprises:
a first statically allocated memory element, adapted to store packets from one of said plurality of communication paths, and
a second dynamically allocated memory element, adapted to store packets from any of said plurality of communication paths; and
control logic adapted to transmit a flow control message to the sender of a packet after receipt of said packet, irrespective of said device's transmission of packets, if the received packet is stored in said second memory element.
12. The network of claim 11 , wherein said communications paths comprise virtual circuits.
13. The network of claim 11 , wherein each of said switching devices further comprises:
a linked list associated with one of said plurality of communication paths, whereby entries in said list are used to indicate the location of a packet stored in said first and second memory elements.
14. The network of claim 13 , wherein each of said switching devices further comprises:
a marker associated with each entry in said list indicating which of said memory elements said packet is stored.
15. The network of claim 14 , wherein each of said switching devices further comprises:
control logic adapted to send a flow control message to the sender of a packet after said packet has been removed from said memory element if said marker indicates that said packet was stored in said first memory element.
16. The network of claim 11 , wherein each of said switching devices further comprises:
a FIFO associated with one of said plurality of communication paths, whereby entries in said list are used to indicate the location of a packet stored in said first and second memory elements.
17. The network of claim 16 , wherein each of said switching devices further comprises:
a marker associated with each entry in said FIFO indicating which of said memory elements said packet is stored.
18. The network of claim 17 , wherein each of said switching devices further comprises:
control logic adapted to send a flow control message to the sender of a packet after said packet has been removed from said memory element if said marker indicates that said packet was stored in said first memory element.
19. A method of receiving packets from a plurality of communication paths, comprising:
providing a switching device having a first statically allocated memory element, adapted to store packets from one of said plurality of communication paths, and a second dynamically allocated memory element, adapted to store packets from any of said plurality of communication paths, receiving a packet from the sender of said packet,
determining whether free space is available in said second memory element to store said packet, storing said packet in said second memory element, if said determination indicates said free space is available; and
sending a flow control message to said sender after storing said packet in said second memory element, irrespective of said device's transmission of packets.
20. The method of claim 19 , wherein said communication paths comprise virtual circuits.
21. The method of claim 19 , further comprising:
storing said packet in said first memory element if said determination indicates said free space is not available.
22. The method of claim 21 , further comprising:
sending a flow control message to said sender when said packet is removed from said first memory element.