Abstract:
A method and apparatus for packet scheduling using a virtual time stamp for a high capacity combined input and output queued switching system. A network employs a virtual time reference system (VTRS) to generate packet virtual time stamps associated with each packet traversing the network. The VTRS includes edge conditioners located at the edge of the network that receive unregulated packet traffic and generate regulated packet traffic for a given flow. The edge conditioners also add a packet virtual time stamp to each incoming packet. Core routers within a network core reference the packet virtual time stamps to schedule packet flow. The core routers also update the packet virtual time stamps using virtual delays. The packet virtual time stamps are removed from the packets when the packets leave the network core through an edge conditioner.

Description:
CROSS-REFERENCE TO RELATED APPLICATION  
       [0001]    This application claims the benefit of U.S. Provisional Application No. 60/250,458 filed on Dec. 1, 2000 which is hereby incorporated by reference as if set forth in full herein. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    The problem of Quality of Service (QoS) provisioning in packet-switched networks has been a focus of networking and telecommunication research communities. Many new packet scheduling algorithms, such as Virtual Clock (VC) and Weighted Fair Queueing (WFQ), have been proposed for the support of QoS guarantees. For example, it has been shown that in a network where WFQ schedulers (or VC schedulers) are employed at every router, end-to-end delay and bandwidth guarantees can be supported for each user traffic flow. Using these results as a reference model, the Internet Engineering Task Force (IETF) has defined a guaranteed service under its Integrated Services or IntServ architecture, where end-to-end delay and bandwidth guarantees are provided for users on a per-flow basis. To support the IETF IntServ architecture, a signaling protocol, RSVP, for setting up end-to-end QoS reservation along a flow&#39;s path has also been proposed and standardized.  
           [0003]    Performing per-flow management inside the network, however, raises the important issue of scalability. Because of the complexity of per-flow operations both in the data plane and QoS control plane, the IntServ architecture may not scale well with the increasing size of the Internet. As an alternative to per-flow based QoS provisioning, in recent years a different paradigm, the Differentiated Services or DiffServ, has been proposed and defined by the IETF. By processing packets based on a number of pre-specified Per-Hop Behaviors (PHBs) encoded by bit patterns carried inside a packet header, the DiffServ paradigm greatly simplifies the data plane of the network core of a domain, thereby making it more scalable. (We will refer to these bit patterns, or the PHBs they embody, as the packet state.) End-to-end, user-to-user QoS support is provided through intra-domain QoS provisioning and inter-domain service agreement. These control plane functions can be performed, for example, by employing a bandwidth broker architecture. On the other hand, the DiffServ architecture, as it is currently defined, aims to provide only coarse-grain QoS support to users. It remains to be seen whether such a service model would be sufficient to meet the potentially diverse user QoS requirements in the future. Furthermore, many issues regarding the design of bandwidth brokers such as admission control and QoS provisioning still need to be addressed, both theoretically and in practice.  
           [0004]    The DiffServ paradigm has been extended using the notion of dynamic packet states to include several techniques to support end-to-end per-flow delay guarantees without per-flow QoS management. In the data plane, a (non-work-conserving) scheduling algorithm, called Core Jitter Virtual Clock or CJVC, provides end-to-end per-flow delay guarantees without per-flow scheduling states at core routers. (Such scheduling algorithms are referred to as core-stateless, in contrast to the conventional stateful scheduling algorithms such as VC or WFQ, where certain scheduling states must be maintained for each flow.) In the control plane, an aggregate reservation estimation algorithm is designed which eliminates the need of maintaining per-flow QoS reservation states. Instead, an aggregate QoS reservation state is maintained at each core router. A hop-by-hop signaling protocol, however, is still needed to set up QoS reservation for each flow along its path within a domain.  
           [0005]    The Internet backbone is facing two problems simultaneously: (1) there is a need to introduce guaranteed QoS, and (2) there is a need for faster switching infrastructure. The first problem may be solved by building switches using output-queuing. This approach is known to achieve the throughput of the switch to 100%. Furthermore, powerful scheduling algorithms, for example WFQ, may be placed at the output port and thus provide QoS guarantee. But output queuing for an N×N switch may require the switching fabric and memory to run N times as fast as the line rate. Thus it may be impractical to design high speed switches, for example a terabit switch, since memories with sufficient bandwidth are simply not available at such high speed.  
           [0006]    To build faster switches, an Input-Queued (IQ) switch architecture may be employed since the fabric and memory of an IQ switch need only run as fast as the line rate. Furthermore, it has been shown that by using a scheme known as Virtual Output Queuing (VOQ), it is possible to eliminate entirely the so-called Head-Of-Line (HOL) blocking problem associated with an IQ switch. However, it remains to be seen how an IQ switch without any speedup can guarantee QoS.  
           [0007]    It is possible to use a combined input and output port queued (CIOQ) switch with a small speedup, termed S, (e.g., 2-4) to provide guaranteed QoS. Under such an architecture, buffers are employed at both the input ports and output ports and the switch can remove up to S (1_&lt;S&lt;_N) packets from each input and deliver up to S packets to each output within a time slot, where a time slot is the time between packet arrival at input ports. With a small speedup, for example, 2 to 4 time, a CIOQ switch may behave identically to an OQ switch for all types of traffic. Herein, “behave identically” is defined as when the same inputs are applied to both the OQ switch and to the CIOQ switch, the corresponding output processes from the two switches are completely indistinguishable.  
           [0008]    Although there are processes that enable a CIOQ switch with a small speedup to mimic an OQ switch with WFQ scheduling algorithm, in practice, such processes may not be implementable for the following two problems: the processes are not scalable (and thus not feasible) to maintain per-flow QoS state in a high speed CIOQ switch to mimic an OQ switch with WFQ scheduler; and even if it were feasible to maintain per-flow state at the CIOQ switch, the calculation of departure time for scheduling in a CIOQ switch requires complex communication among various input and output ports, which is simply not implementable for a switch operating at very high speed. Therefore, there is a need to design an implementation-friendly scheduling algorithm for a CIOQ switch to guarantee QoS.  
         SUMMARY OF THE INVENTION  
         [0009]    A method and apparatus for packet scheduling using a virtual time stamp for a high capacity combined input and output queued switching system are provided. A network employs a virtual time reference system (VTRS) to generate packet virtual time stamps associated with each packet traversing the network. The VTRS includes edge conditioners located at the edge of the network that receive unregulated packet traffic and generate regulated packet traffic for a given flow. The edge conditioners also add the packet virtual time stamp to each incoming packet. Core routers within a network core reference the packet virtual time stamps to schedule packet flow. The core routers also update the packet virtual time stamps using virtual delays. The packet virtual time stamps are removed from the packets when the packets leave the network core through an edge conditioner.  
           [0010]    In one aspect of the invention, a method for routing packets by a scheduler operably coupled to a switch including a plurality of inputs and a plurality of outputs is provided. A packet virtual time stamp is generated for each of the packets and appended to the packets upon entering the network. The switch included in the network receives at its plurality of inputs the packets and the scheduler matches inputs to outputs using the packet virtual time stamps.  
           [0011]    In another aspect of the invention, the scheduler a matches the plurality of inputs to the plurality of outputs by determining a virtual finish time for each packet in the regulated packet traffic and matching an output to an input using the virtual finish times.  
           [0012]    In another aspect of the invention, the network further includes an edge conditioner located at the edge of the network. The edge conditioner is operably coupled to a first-hop core router in the network core. The edge conditioner receives the packets and generates a regulated packet traffic for a flow using the a size of each of the packets and a reserved flow rate. The regulated packet traffic is transmitted by the edge conditioner to the first-hop core router.  
           [0013]    In another aspect of the invention, the first-hop core router updates the packet virtual time stamp for each packet in the regulated packet traffic for a flow using the arrival time of each packet at the first-hop core router. Subsequent network core routers update the packet virtual time stamp for each packet in the regulated packet traffic for a flow using each packet&#39;s packet virtual time stamp and a virtual delay. For delay-based network core routers, the virtual delay is a fixed delay. For rate-based network core routers, virtual delay is generated using the size of each packet, a flow rate reserved for the regulated packet traffic for a flow, and a cumulative queuing delay 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]    These and other features, aspects, and advantages of the present invention will become better understood with regard to the following description and accompanying drawings where:  
         [0015]    [0015]FIG. 1 is a diagram of an exemplary computer network in accordance with the present invention;  
         [0016]    [0016]FIG. 2 a  is a diagram of an exemplary traffic spacer in accordance with the present invention;  
         [0017]    [0017]FIG. 2 b  is a diagram depicting the effect edge traffic conditioning has on the flow of traffic injected into a core network;  
         [0018]    [0018]FIG. 3 is a diagram of a packet with a packet virtual time stamp in accordance with the present invention;  
         [0019]    [0019]FIG. 4 is a process diagram of an exemplary virtual stamp update process as used by a core router in accordance with the present invention;  
         [0020]    [0020]FIG. 5 is a diagram of an exemplary 3×3 switch in accordance with the present invention; and  
         [0021]    [0021]FIG. 6 is a diagram of an exemplary smallest virtual finish time first scheduling process in accordance with the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0022]    A Virtual Time Reference System (VTRS) in accordance with an embodiment of the present invention provides a unifying scheduling framework allowing scalable support for guaranteed services using the DiffServ paradigm. An embodiment of a scheduler based on the VTRS for a switch resolves both a scaling problem associated with maintaining per-flow QoS state information at a switch and a complex inter-port communication problem encountered in calculating and updating a departure time for each packet associated with the switch. More specifically, a virtual finish time associated with each incoming packet to a switch provides for scheduling in a switch to mimic a Core Stateless Virtual Clock (CSVC).  
         [0023]    [0023]FIG. 1 is a diagram of an exemplary embodiment of a network employing a VTRS in accordance with the present invention. A computer network  100  employing a VTRS includes an edge conditioner  102  located at the edge of the computer network. The edge conditioner is operably coupled to a core router  104  included in a network core  105 . The edge router receives an incoming packet  106  that is to be transmitted through the network. The edge conditioner receives the incoming packet and generates a VTRS packet  108  by associating a packet state including a packet virtual time stamp to the incoming packet. The VTRS packet is transmitted to the core router. The core router uses the packet virtual time stamp included in the VTRS packet&#39;s packet state to schedule the transmission of the VTRS packet to the next core router  109  in the network core.  
         [0024]    Each core router in the network core uses the packet virtual time stamp to schedule the transmission of the VTRS packet to the next core router. Additionally, each core router receiving the VTRS packet updates the packet virtual time stamp as the VTRS packet leaves the core router. A final edge conditioner  110  receives the VTRS packet and generates an outgoing packet  112  by removing the packet virtual time stamp from the VTRS packet. Thus, the VTRS is defined and implemented within a single administrative domain because the packet virtual time stamp inserted by one administrative domain will not be carried over to another administrative domain.  
         [0025]    The exemplary embodiment of a network in accordance with the present invention is shown with three core routers and two edge conditioners with a single path through the network. Other embodiments of networks in accordance with the present invention may employ a plurality of edge conditioners each of which may be coupled to a plurality of core routers. In turn, each core router may be operably coupled to a plurality of other core routers in the network core.  
         [0026]    [0026]FIG. 2 a  is a diagram of an exemplary embodiment of an edge conditioner in accordance with the present invention. An exemplary embodiment of an edge conditioner  102  receives a flow of packets  200 . The edge conditioner injects the traffic of a flow into the network core at a rate less than or equal to the flow&#39;s reserved rate. The edge conditioner uses a rate spacing process that generates appropriate spacing between the packets of a flow based on the flow&#39;s reserved rate. The resulting packet traffic  202  is regulated and includes in each VTRS packet a packet state including a packet virtual time stamp. The edge conditioner generates packet traffic wherein the arrival times of the packets within the network core adhere to the following relationship: for a flow j with a reserved rate r j , the inter-arrival time of two consecutive packets of the flow is such that: 
           a   j,k+1   −a   j,k   ≧L   j,k+1   /r   j   (1) 
         [0027]    where a j,k  denotes the arrival time of the kth packet, p j,k , of flow j at the network core, and L j,k , is the size of packet p j,k .  
         [0028]    In the VTRS, each core router is equipped with a per-hop virtual time reference/update mechanism allowing maintenance of a continual progression of the virtual time embodied by the packet virtual time stamps. As a VTRS packet traverses each core router along the path of the VTRS packet&#39;s flow, the packet virtual time stamp is updated by the core router as the VTRS packet leaves the core router. This packet virtual time stamp represents the arrival time of the packet at the next core router in virtual time, and thus it is also referred to as the virtual arrival time of the packet at the next core router. With respect to the virtual time, the inter-arrival time spacing is preserved at a core router by the VTRS packet spacing generated by the edge conditioner. Or to put it another way, the “virtual rate” (as defined with respect to the virtual time) of packets of a flow arriving at a core router does not exceed the reserved rate of the flow.  
         [0029]    [0029]FIG. 2 b  is a graph depicting the effect edge traffic conditioning has on the flow of traffic injected into a network core. Increasing time is represented on the horizontal axis and cumulative traffic in a flow is represented on the vertical axis  206 . For a given reserve rate over time, the expected cumulative traffic in a flow is given by the service curve  208 . A first unregulated packet  210  may arrive at the edge conditioner and be injected into the core network without exceeding the service curve. A second unregulated packet  212  may arrive at the edge conditioner. Injection of the second unregulated packet may cause the flow&#39;s cumulative traffic to exceed the service curve for the flow. A subsequent unregulated packet  214  may arrive at the edge conditioner and be injected into the network core. The result is that the reserved rate of the flow may be exceeded.  
         [0030]    In a regulated flow, a delay  216  is added to the second unregulated packet so that a regulated packet  218  is injected into the network core that does not exceed the service curve of the flow. In a like manner, a delay is added to each subsequent unregulated packet to generate a subsequent regulated packet  220 . Thus the edge conditioner generates a flow of packets wherein the inter-packet delay satisfies equation 1.  
         [0031]    [0031]FIG. 3 is a diagram of a packet with a packet state in accordance with the present invention. Core routers in a network core employing a VTRS reference and update a packet state included in each VTRS packet transmitted through the network. A VTRS packet  108  includes an incoming packet  106  and a packet state  300 . The packet state includes QoS reservation information  302  for the flow including the VTRS packet. The QoS information includes a reserved flow rate or a delay parameter for the flow. The VTRS packet further includes a packet virtual time stamp  304  for the VTRS packet and a virtual time adjustment term  306 . The packet state is initialized and appended to a packet at the network edge after the packet has gone through the edge conditioner. The per-hop behavior of each core router is defined with respect to the packet state carried by VTRS packets traversing the core router. One property of packet virtual time stamps is that they can be computed using the packet state carried by packets (plus a couple of fixed parameters associated with core routers). In this sense, the VTRS is core stateless, as per-flow states are not needed at core routers for computing packet virtual time stamps.  
         [0032]    [0032]FIG. 4 is a process diagram of an exemplary virtual time stamp update process as used by a core router in accordance with the present invention. Each core router in the network core references and updates the packet virtual time stamp. A core router uses  402  a packet virtual time stamp for a VTRS packet to generate a virtual finish time for the VTRS packet&#39;s traversal of the core router. The core router uses  404  the virtual finish time to schedule the departure of a VTRS packet from the core router. The core router updates  406  the packet virtual time stamp before the VTRS packet is transmitted to the next core router.  
         [0033]    The packet virtual time stamp as used by a core router is updated by the previous core router. In the case where the core router is the first-hop core router, the packet virtual time stamp is initialized to the actual arrival time of the VTRS packet to the first-hop core router. If the first-hop core router is located with an edge conditioner, then the actual arrival time of the VTRS packet is substantially the same as the actual network arrival time of the packet used to generate the VTRS packet. If the core router is not the first-hop core router, the packet virtual time stamp is updated by adding a delay value to the previous packet virtual time stamp.  
         [0034]    In one embodiment of a VTRS in accordance with the present invention, the delay value added to a packet virtual time stamp by a core router includes a virtual delay. The virtual delay is determined by the type of the core router. Core routers can be either rate-based routers or delay-based routers. A rate-based router has a service capacity equal to the reserved rate r j  of flow j. Hence a rate-based router takes L j,k /r j  amount of time to process packet p j,k  of flow j. A delay-based router has a fixed latency, which equals a delay parameter d j  of flow j. In other words, a delay-based router with latency d j  takes d j  amount of time to process a VTRS packet included in flow j, independently of the VTRS packet&#39;s packet size.  
         [0035]    For a rate-based router, the virtual delay is given by L j,k /r j  added to a virtual time adjustment term, δ j,k . In a network having q rate-based core routers, δ j,k =Δ q   j,k /q where Δ q   j,k  is the cumulative queuing delay of VTRS packet p j,k . The virtual time adjustment term is generated at the network edge and inserted into the packet state in addition to the reserved rate r j  as shown in FIG. 3.  
         [0036]    In one embodiment of a VTRS in accordance with the present invention, the delay value added to a packet virtual time stamp by the core routers includes a propagation delay value, π. The propagation delay is the delay experienced by a VTRS packet as the VTRS packet is transmitted between routers in a network core. The propagation delay can be predetermined for each hop, is independent of the size of the VTRS packet being transmitted, and stored by the router as a fixed parameter.  
         [0037]    In one embodiment of a VTRS in accordance with the present invention, the delay value added to a packet virtual time stamp by a core router includes an error term, Ψ. The error term is an upper bound of the difference between the actual departure time and virtual finish time of a packet traversing a core router.  
         [0038]    In one embodiment of a VTRS in accordance with the present invention, the delay value added to a packet virtual time stamp by a core router is the summation of the virtual delay, the error term, and the propagation delay, or:  
         ϖ     i   +   1       j   ,   k       =       ϖ   i     j   ,   k       +       d   ~     i     j   ,   k       +     Ψ   i     +     π     i   ,     i   +   1                                 
 
         [0039]    where {overscore (ω)} l+1   j,k  is the virtual time stamp for VTRS packet p j,k  entering the (i+l) th  hop router Si+l, {tilde over (d)} l   j,k  is the virtual delay for hop router Si, Ψ i  is the error term for hop router Si, and π i,i−1  is the propagation delay between hop router Si and Si+l.  
         [0040]    A Core stateless Virtual Clock (CsVC) scheduler is a work-conserving, rate-based scheduler using a packet virtual time stamp. A CsVC scheduler services VTRS packets in the order of their virtual finish times. For any packet p j,k  traversing the scheduler, if ω j,k  is the virtual time carried by p j,k  as it enters the scheduler, and  
         d     j   ,   k       =         L     j   ,   k         r   j       +     δ     j   ,   k                               
 
         [0041]    its virtual delay. Then the virtual finish time v j,k  of p j,k  is given by ω j,k +d j,k .  
         [0042]    A virtual time earliest deadline first (VT-EDF) scheduler is a work-conserving, delay-based scheduler. A VT-EDF scheduler services VTRS packets in the order of their virtual finish times. The virtual finish time of p j,k  is given by V p,k =ω j,k +d j , where ω j,k  is the virtual time carried by p j,k  as it enters the VT-EDF scheduler and d j  is the delay parameter associated with the VTRS packet&#39;s flow.  
         [0043]    [0043]FIG. 5 is a diagram of an exemplary 3×3 CIOQ switch in accordance with the present invention. Δn exemplary 3×3 CIOQ switch  500  includes a first input port  502  operably coupled to a first output port  504 , a second output port  506 , and a third output port  508 . The first input port is operably coupled to a set of Virtual Output Queues (VOQ)  505  for packets destined for each output. The set of VOQs includes a separate queue corresponding to each of the output ports. Incoming VTRS packets are stored in a VOQ in sorted order based on the VTRS packet&#39;s virtual finish times. In an embodiment of a CIOQ switch in accordance with the present invention, the VTRS packets are sorted in ascending order with the VTRS packet with the smallest virtual finish time at the front of the queue.  
         [0044]    In a similar manner, a second input port  510  is operably coupled to the first, second, and third output ports. The second input port is operably coupled to a second set of VOQs  511  for packets destined for each output. A third input port  512  is operably coupled to the first, second, and third outputs. The third input port is operably coupled to a second set of VOQs  513  for packets destined for each output.  
         [0045]    A scheduler  514  generates a matching between the inputs and the outputs in such a way that each non-empty input is matched with at most one output and, conversely, each output is matched with at most one input. The matching is used to configure the CIOQ switch before packets are transferred from the input side to the output side. The scheduler uses the previously described virtual finish time to match inputs and outputs. The scheduler matches inputs to outputs by assigning an output to an input holding the output&#39;s VTRS packet with the smallest virtual finish time. In the case of contention caused by multiple outputs being matched to a single input, the scheduler breaks the contention and matches one of the outputs to the single input. The scheduler will try and match a losing output to an input holding the losing output&#39;s VTRS packet with the next smallest virtual finish time. When no more matching of inputs and outputs is possible, VTRS packets are transferred and the scheduler repeats the process.  
         [0046]    [0046]FIG. 6 is a diagram of an exemplary smallest virtual finish time first scheduling process in accordance with the present invention. At the beginning of each transfer phase, each output port tries to obtain its VTRS packet with the smallest virtual finish time from an input port. Incoming packets are stored  601  in the VOQs for each input port as previously described. At the beginning of each phase, a scheduler tentatively matches  602  each unmatched output port to an input port. An input port is matched to an output port if the input port is holding the VTRS packet in a VOQ for the output port having the smallest virtual finish time.  
         [0047]    The scheduler determines if more than one output port is tentatively matched to the same input port  604 . If only one output port is matched to an input port, then the scheduler accepts  606  the match. If more than one output port is matched to an input port the scheduler determines  608  if the virtual finish times for the VTRS packets for the output ports are the same. If the virtual finish times for the VTRS packets are the same, then the scheduler matches  610  the input port to the output port with the smallest port number. If the virtual finish times for the VTRS packets are not the same, the scheduler matches  612  the input port to the output port whose VTRS packet has the smallest virtual finish time. The scheduler repeats  614  the process of matching unmatched input ports to output ports until there are no more matches possible. Once all possible matches are made, the scheduler transfers  616  the VTRS packets from the input ports to the matched output ports. The scheduler then starts  616  a new matching phase.  
         [0048]    Although this invention has been described in certain specific embodiments, many additional modifications and variations would be apparent to those skilled in the art. It is therefore to be understood that this invention may be practiced otherwise than as specifically described. Thus, the present embodiments of the invention should be considered in all respects as illustrative and not restrictive, the scope of the invention to be determined by claims supported by this application and the claims&#39; equivalents rather than the foregoing description.