Method to achieve bounded buffer sizes and quality of service guarantees in the internet network

Abstract

Methods to achieve bounded router buffer sizes and Quality of Service guarantees for traffic flows in a packet-switched network are described. The network can be an Internet Protocol (IP) network, a Differentiated Services network, an MPLS network, wireless mesh network or an optical network. The routers can use input queueing, possibly in combination with crosspoint queueing and/or output queueing. Routers may schedule QoS-enabled traffic flows to ensure a bounded normalized service lead/lag. Each QoS-enabled traffic flow will buffer O(K) packets per router, where K is an integer bound on the normalized service lead/lag. Three flow-scheduling methods are analysed. Non-work-conserving flow-scheduling methods can guarantee a bound on the normalized service lead/lag, while work-conserving flow-scheduling methods typically cannot guarantee the same small bound. The amount of buffering required in a router can be reduced significantly, the network links can operate near peak capacity, and strict QoS guarantees can be achieved.

What is claimed is: 
     
         1 . A method for achieving bounded buffer sizes in a packet-switched network for a provisioned application-layer traffic flow, comprising:
 a packet-switched network comprising routers and links, said routers comprising switches and buffers to hold packets,   a router scheduling method for scheduling packets through said routers,   said provisioned traffic flow routed over at least one path through the network,   one or more Application-Specific Traffic-Shaper modules associated with said provisioned application-layer traffic flow at the source node, said Traffic-Shaper modules shaping said provisioned application-layer traffic flows and transmitting network-layer packets into the network with a bounded normalized service lead/lag,   one or more Application-Specific Playback-Queue modules associated with said provisioned application-layer traffic flow at the destination node, said Playback-Queue modules reconstructing the provisioned application-layer packets from the network-layer packets received from the network,   said router scheduling method scheduling said network-layer packets associated with said provisioned traffic flow through at least one of said routers to depart said router with a bounded normalized service lead/lag.   
     
     
         2 . The method of  claim 1 ,
 wherein the routers comprise at least one input port module with at least one virtual output queue (VOQ) and a flow-scheduling method,   wherein at least one provisioned network-layer traffic flow is associated with at least one VOQ,   wherein said flow-scheduling method selects network-layer-packets for service from said at least one provisioned traffic flow associated with said at least one VOQ, when the VOQ is enabled to service a packet.   
     
     
         3 . The method of  claim 2 ,
 wherein said network-layer-packets associated with one provisioned traffic flow departing said router have a normalized service lead/lag.   
     
     
         4 . The method of  claim 2 ,
 wherein said flow-scheduling method computes a non-work-conserving flow-schedule for a scheduling frame of duration F time-slots, wherein said flow-schedule identifies zero or one provisioned traffic flows for service for each time-slot when the associated VOQ is enabled for service.   
     
     
         5 . The method of  claim 2 ,
 wherein said flow-scheduling method is work-conserving,   wherein said schedule identifies one non-empty provisioned traffic flow for service for each time-slot when the associated VOQ is enabled for service.   
     
     
         6 . The method of  claim 2 ,
 wherein said flow-scheduling method selects a provisioned traffic flow for service substantially at random when the associated VOQ is enabled for service.   
     
     
         7 . The method of  claim 2 ,
 wherein said flow-scheduling method selects a provisioned traffic flow for service by prioritizing provisioned traffic flows based upon an attribute of each traffic flow, and selecting one provisioned traffic flow for service with the highest value of said attribute, when the associated VOQ is enabled for service.   
     
     
         8 . The method of  claim 2 , further comprising at least aggregation module and associated de-aggregation module,
 wherein at least 2 of said provisioned traffic flows arriving to said aggregation module are combined to form one new aggregated traffic flow,   wherein at least one aggregated traffic flow arriving to said dis-aggregation module is partitioned into at least 2 of said provisioned traffic flows.   
     
     
         9 . The method of  claim 8 ,
 wherein packets associated with an aggregated traffic flow departing from at least one of said packet-switches have a bounded normalized service lead/lag.   
     
     
         10 . A method for achieving bounded buffer sizes in a packet-switched network for selected traffic classes, comprising:
 a packet-switched network comprising packet-switches and links, said packet-switches comprising buffers to hold packets,   a scheduling algorithm for scheduling traffic through said packet-switches,   one or more Traffic-Shaper modules at the entry points of the network,   said Traffic-Shaper modules shaping said incoming traffic flows in each traffic class to achieve a bounded normalized service lead/lag,   said scheduling algorithm scheduling network-layer packets belonging to said traffic classes through said packet-switches such that said packets associated with one traffic class leaving at least one of said switches achieves a bounded normalized service lead/lag.   
     
     
         11 . A method for achieving bounded buffer sizes and mathematically provable Quality of Service guarantees in a packet-switched network for selected traffic classes, comprising
 a packet-switched network comprising packet-switches and links, said packet-switches comprising buffers to hold packets,   a scheduling algorithm for scheduling traffic through said packet-switches,   one or more Application-Specific Traffic-Shaper modules at some entry points of the network,   one or more Application-Specific Playback Queue modules at some exit points of the network,   said Traffic-Shaper modules shaping said provisioned application-layer traffic flows and transmitting network-layer packets with associated traffic class identifier into said network with a bounded normalized service lead/lag,   said switch scheduling method scheduling said network-layer packets through at least one of said switches such that the network-layer packets associated with one traffic class leaving at least one of said switches achieves a bounded normalized service lead/lag,   said Playback-Queue modules reconstructing the original application-layer packets in said traffic flows.   
     
     
         12 . The method of  claim 11 ,
 wherein said Playback-Queues release application-level packets such that Quality of Service guarantees are met.