Real-time traffic shaper with keep-alive property for best-effort traffic

A traffic shaper for shaping traffic in a packet network, comprising:

• a packet classifier coupled to receive an incoming packet from said packet network and to classify the incoming packet as one of a real-time packet and a best-effort packet;
• a packet discarding block coupled to perform traffic shaping of the incoming packet from the packet classifier and discard the incoming packet in accordance with traffic shaping parameters;
• connection queues including a real-time queue and a best-effort queue coupled to temporary store real-time packets and best-effort packets from the packet discarding block, respectively;
• and
• a packet scheduling block coupled to send the real-time and best-effort packets from the connection queues to an outgoing device in accordance with said traffic shaping parameters, wherein said packet scheduling block is periodically executed to schedule output of an incoming packet by:
• determining whether both the real-time and best-effort queues are empty;
• determining whether there is concurrency and time to transmit the best-effort packet from the best-effort queue;
• when there is concurrency and time to transmit the best-effort packet, checking whether total bandwidth constraint allows transmission of the best-effort packet from the best-effort queue head;
• when transmission is allowed, updating a time of next transmission and transmitting the best-effort packet to the outgoing device;
• determining whether the real-time queue is not empty and time for transmission of the real-time packet is permitted;
• when the real-time queue is not empty and time for transmission of the real-time packet is permitted, updating the transmission time and transmitting the real-time packet to the outgoing device from the real-time queue head;
• determining whether the best-effort queue is not empty and time for transmission of the best-effort packet is permitted;
• and
• when the best-effort queue is not empty and time for transmission of the best-effort packet is permitted, updating the transmission time and transmitting the best-effort packet to the outgoing device from the best-effort queue head.

A network, comprising:

• a source terminal comprising a host and a network interface controller;
• a destination terminal comprising a host and a network interface controller;
• a bandwidth-limited link providing connection between the source terminal and the destination terminal;
• and
• at least one network interface controller of the source terminal or the destination terminal comprises a traffic shaper installed therein for shaping traffic in the network, said traffic shaper comprising:
• a packet classifier to receive an incoming packet and to classify the incoming packet as one of a real-time packet and a best-effort packet;
• a packet discarding block to perform traffic shaping of the incoming packet from the packet classifier and discard the incoming packet in accordance with traffic shaping parameters;
• connection queues including a real-time queue and a best-effort queue to temporary store real-time packets and best-effort packets from the packet discarding block, respectively;
• and
• a packet scheduling block to send the real-time and best-effort packets from the connection queues to an outgoing device in accordance with said traffic shaping parameters, wherein said packet discarding block is executed to discard an incoming packet by:
• determining whether the real-time and best-effort queues are empty;
• when the real-time and best-effort queues are empty, resetting the counters and a scheduled transmission time of the next incoming packet;
• determining whether a real-time latency is greater than a maximum latency value of the real-time queue;
• when the real-time latency is greater than the maximum latency value of the real-time queue, discarding the real-time packet input from the packet classifier;
• determining whether a total latency is greater than a maximum latency value of both the real-time and best-effort queues;
• when the total latency is greater than the maximum latency value of both the real-time and best-effort queues, adding a best-effort packet to a tail of the best-effort queue and discarding a best-effort packet from a head of the best-effort queue;
• determining whether a length of the real-time queue is greater than a maximum queue length of the real-time queue;
• when the length of the real-time queue is greater than a maximum queue length of the real-time queue, discarding the real-time packet input from the packet classifier;
• determining whether a length of the best-effort queue is greater than a maximum queue length of the best-effort queue;
• when the length of the best-effort queue is greater than a maximum queue length of the best-effort queue, adding a best-effort packet input from the packet classifier to the tail of the best-effort queue and discarding a best-effort packet from a head of the best-effort queue;
• determining whether there is concurrency and time to discard a real-time packet to make room for best-effort packets;
• when there is concurrency and time to discard the real-time packet, discarding the real-time packet to implement the keep-alive bandwidth for best-effort packets;
• and
• placing the real-time packet that was not discarded in the real-time queue.

A network comprising:

• a source terminal comprising a host and a network interface controller;
• a destination terminal comprising a host and a network interface controller;
• a bandwidth-limited link providing connection between the source terminal and the destination terminal;
• and
• at least one network interface controller of the source terminal or the destination terminal comprises a traffic shaper installed therein for shaping traffic in the network, said traffic shaper comprising:
• a packet classifier to receive an incoming packet and to classify the incoming packet as one of a real-time packet and a best-effort packet;
• a packet discarding block to perform traffic shaping of the incoming packet from the packet classifier and discard the incoming packet in accordance with traffic shaping parameters;
• connection queues including a real-time queue and a best-effort queue to temporary store real-time packets and best-effort packets from the packet discarding block, respectively;
• and
• a packet scheduling block to send the real-time and best-effort packets from the connection queues to an outgoing device in accordance with said traffic shaping parameters, wherein said packet scheduling block is periodically executed to schedule output of an incoming packet by:
• determining whether both the real-time and best-effort queues are empty;
• determining whether there is concurrency and time to transmit the best-effort packet from the best-effort queue;
• when there is concurrency and time to transmit the best-effort packet, checking whether total bandwidth constraint allows transmission of the best-effort packet from the best-effort queue head;
• when transmission is allowed, updating a time of next transmission and transmitting the best-effort packet to the outgoing device;
• determining whether the real-time queue is not empty and time for transmission of the real-time packet is permitted;
• when the real-time queue is not empty and time for transmission of the real-time packet is permitted, updating the transmission time and transmitting the real-time packet to the outgoing device from the real-time queue head;
• determining whether the best-effort queue is not empty and time for transmission of the best-effort packet is permitted;
• and
• when the best-effort queue is not empty and time for transmission of the best-effort packet is permitted, updating the transmission time and transmitting the best-effort packet to the outgoing device from the best-effort queue head.

A computer usable medium having computer readable program code means embodied therein a traffic shaper algorithm for use in a source terminal for shaping traffic in a packet network, comprising:

• a packet classifier module configured to receive an incoming packet and to classify the incoming packet as one of a real-time packet and a best-effort packet;
• a packet discarding module configured to perform traffic shaping of the incoming packet from the packet classifier and discard the incoming packet in accordance with traffic shaping parameters;
• a connection queue module including a real-time queue and a best-effort queue configured to temporary store real-time packets and best-effort packets from the packet discarding block, respectively;
• and
• a packet scheduling module configured to send the real-time and best-effort packets from the connection queues to an outgoing device in accordance with said traffic shaping parameters, wherein said packet discarding module is configured to discard an incoming packet by:
• determining whether the real-time and best-effort queues are empty;
• when the real-time and best-effort queues are empty, resetting the counters and a scheduled transmission time of the next incoming packet;
• determining whether a real-time latency is greater than a maximum latency value of the real-time queue;
• when the real-time latency is greater than the maximum latency value of the real-time queue, discarding the real-time packet input from the packet classifier;
• determining whether a total latency is greater than a maximum latency value of both the real-time and best-effort queues;
• when the total latency is greater than the maximum latency value of both the real-time and best-effort queues, adding a best-effort packet to a tail of the best-effort queue and discarding a best-effort packet from a head of the best-effort queue;
• determining whether a length of the real-time queue is greater than a maximum queue length of the real-time queue;
• when the length of the real-time queue is greater than a maximum queue length of the real-time queue, discarding the real-time packet input from the packet classifier;
• determining whether a length of the best-effort queue is greater than a maximum queue length of the best-effort queue;
• when the length of the best-effort queue is greater than a maximum queue length of the best-effort queue, adding a best-effort packet input from the packet classifier to the tail of the best-effort queue and discarding a best-effort packet from a head of the best-effort queue;
• determining whether there is concurrency and time to discard a real-time packet to make room for best-effort packets;
• when there is concurrency and time to discard the real-time packet, discarding the real-time packet to implement the keep-alive bandwidth for best-effort packets;
• and
• placing the real-time packet that was not discarded in the real-time queue.

A computer usable medium having computer readable program code means embodied therein a traffic shaper algorithm for use in a source terminal for shaping traffic in a packet network, comprising:

• a packet classifier module configured to receive an incoming packet and to classify the incoming packet as one of a real-time packet and a best-effort packet;
• a packet discarding module configured to perform traffic shaping of the incoming packet from the packet classifier and discard the incoming packet in accordance with traffic shaping parameters;
• a connection queue module including a real-time queue and a best-effort queue configured to temporary store real-time packets and best-effort packets from the packet discarding block, respectively;
• and
• a packet scheduling module configured to send the real-time and best-effort packets from the connection queues to an outgoing device in accordance with said traffic shaping parameters, wherein said packet scheduling block is configured to periodically schedule output of an incoming packet by:
• determining whether both the real-time and best-effort queues are empty;
• determining whether there is concurrency and time to transmit the best-effort packet from the best-effort queue;
• when there is concurrency and time to transmit the best-effort packet, checking whether total bandwidth constraint allows transmission of the best-effort packet from the best-effort queue head;
• when transmission is allowed, updating a time of next transmission and transmitting the best-effort packet to the outgoing device;
• determining whether the real-time queue is not empty and time for transmission of the real-time packet is permitted;
• when the real-time queue is not empty and time for transmission of the real-time packet is permitted, updating the transmission time and transmitting the real-time packet to the outgoing device from the real-time queue head;
• determining whether the best-effort queue is not empty and time for transmission of the best-effort packet is permitted;
• and
• when the best-effort queue is not empty and time for transmission of the best-effort packet is permitted, updating the transmission time and transmitting the best-effort packet to the outgoing device from the best-effort queue head.

A mechanism, comprising:

• a packet classifier to classify incoming packets received from a connection source, as one of real-time packets indicating real-time data streams and best-effort packets indicating best-effort data streams;
• a packet discard unit to perform traffic shaping of the incoming packets and discard the incoming packets in accordance with bandwidth parameters;
• connection queues including a real-time queue and a best-effort queue to temporary store real-time packets and best-effort packets, respectively, from the packet discard unit;
• and
• a packet scheduler to send the real-time packets and the best-effort packets from the connection queues to an outgoing device in accordance with said bandwidth parameters, wherein the packet discard unit is configured to discard an incoming packet by:
• determining if the real-time and best-effort queues are empty;
• if the real-time and best-effort queues are empty, resetting internal counters and a scheduled transmission time of the next incoming packet;
• determining if a real-time latency is greater than a maximum latency value of the real-time queue;
• if the real-time latency is greater than the maximum latency value of the real-time queue, discarding the real-time packet from the packet classifier;
• determining if a total latency is greater than a maximum latency value of both the real-time and best-effort queues;
• if the total latency is greater than the maximum latency value of both the real-time and best-effort queues, adding a best-effort packet to a tail of the best-effort queue and discarding a best-effort packet from a head of the best-effort queue;
• determining if a length of the real-time queue is greater than a maximum queue length of the real-time queue;
• if the length of the real-time queue is greater than a maximum queue length of the real-time queue, discarding the real-time packet input from the packet classifier;
• determining if a length of the best-effort queue is greater than a maximum queue length of the best-effort queue;
• if the length of the best-effort queue is greater than a maximum queue length of the best-effort queue, adding a best-effort packet input from the packet classifier to the tail of the best-effort queue and discarding a best-effort packet from a head of the best-effort queue;
• determining if there is concurrency and time to discard a real-time packet to make room for best-effort packets;
• if there is concurrency and time to discard the real-time packet, discarding the real-time packet to implement the keep-alive bandwidth for best-effort packets;
• and
• placing the real-time packet that was not discarded in the real-time queue.

A mechanism comprising:

• a packet classifier to classify incoming packets received from a connection source, as one of real-time packets indicating real-time data streams and best-effort packets indicating best-effort data streams;
• a packet discard unit to perform traffic shaping of the incoming packets and discard the incoming packets in accordance with bandwidth parameters;
• connection queues including a real-time queue and a best-effort queue to temporary store real-time packets and best-effort packets, respectively, from the packet discard unit;
• and
• a packet scheduler to send the real-time packets and the best-effort packets from the connection queues to an outgoing device in accordance with said bandwidth parameters, wherein the packet scheduler is configured to periodically schedule an output of the incoming packet by:
• determining if both the real-time and best-effort queues are empty;
• if the real-time and best-effort queues are empty, resetting internal counters and a scheduled transmission time of the next incoming packet;
• determining if there is concurrency and time to transmit the best-effort packet from the best-effort queue;
• if there is concurrency and time to transmit the best-effort packet, checking whether total bandwidth constraint allows transmission of the best-effort packet from the best-effort queue head;
• if transmission is allowed, updating a time of next transmission and transmitting the best-effort packet to the outgoing device;
• determining if the real-time queue is not empty and time for transmission of the real-time packet is permitted;
• if the real-time queue is not empty and time for transmission of the real-time packet is permitted, updating the transmission time and transmitting the real-time packet to the outgoing device from the real-time queue head;
• determining if the best-effort queue is not empty and time for transmission of the best-effort packet is permitted;
• and
• if the best-effort queue is not empty and time for transmission of the best-effort packet is permitted, updating the transmission time and transmitting the best-effort packet to the outgoing device from the best-effort queue head.