Patent Document

TECHNICAL FIELD 
     This description relates to computer networking, and more particularly to scheduling transmission of network cells. 
     BACKGROUND 
     In ATM networking, cells are transmitted over virtual connections. Virtual connections represent stateful communication setups such as an ATM virtual circuit or an Internet TCP connection. At each end of the network virtual connection is a software application that can send and receive messages. The messages are carried across the network as packets or frames that are further subdivided into 48 byte ATM cells. The interface in and out of the forwarding device is either 48 byte ATM cells or 64 byte frame segments. Each virtual connection has a quality of service or rate specification. ATM Forum Traffic Management Specification 4.1 specifies the types of rates, e.g. constant bit rate (CBR), variable bit rate (VBR), unspecified bit rate (UBR), etc. Unspecified bit rate can have a priority associated with the virtual connection. 
     Network devices such as routers, switches, and traffic shapers schedule the transmission of cells to a network. One form of schedule for transmission is the calendar schedule, where a slot of the schedule represents a period of time for possible transmission of one or more cells. A virtual connection is “scheduled” according to a calendar schedule if a slot in the calendar schedule is reserved for the virtual connection. A transmission process performs the transmissions of the network device. The transmission process uses the calendar schedule as a guide for when to offer transmission opportunities to scheduled virtual connections. 
     Groups of virtual connections may be scheduled for transmission to one region of a network, going through a network interface such as a port. A large traffic shaper may handle many schedules. For example, each schedule may be for a different port or network domain. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is a block diagram of logical elements in a reservation system; 
         FIG. 2  is a block diagram of a router/traffic shaper; 
         FIG. 3A  is a block diagram of a schedule repository; 
         FIG. 3B  is a diagram of a recurrent transmission cycle; 
         FIG. 4  is a block diagram of a virtual connection repository; 
         FIG. 5A  is a diagram of a hierarchical reservation vector; 
         FIG. 5B  is a diagram of a branch of a hierarchical reservation vector; 
         FIG. 6  is a block diagram of a vector address; 
         FIG. 7  is a block diagram of a range for virtual connection transmission; 
         FIG. 8  is a block diagram of reservation procedures; 
         FIG. 9  is a flowchart of a shape procedure; 
         FIG. 10  is a flowchart of a schedule next slot procedure; 
         FIG. 11  is a flowchart of a recursive slot subroutine; and 
         FIG. 12  is a flowchart of a circular priority find procedure. 
     
    
    
     Like reference symbols in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
     In general, for a virtual connection associated with a schedule, a reservation system includes reservation procedures that find an available slot within the schedule. The reservation procedures find the available slot subject to timing requirements imposed by the rate of the virtual connection, when such requirements exists. The reservation system also includes a hierarchical reservation vector whose structure supports efficient lookups of first available slots by the reservation procedures. The reservation procedures are encoded as computing instructions that are executable by one or more automated processors. 
     Referring to  FIG. 1 , a reservation system  20  includes hierarchical reservation vector  22  and reservations procedures  24 . Hierarchical reservation vector  22  is a data structure. 
     Reservation system  20  uses a schedule repository  26  that provides information on schedules  28 , including the timing and boundaries of each such schedule  28 . 
     Reservation system  20  also uses a virtual connection (or “VC”) repository  34 . VC repository  34  provides information on virtual connections  36  whose transmission opportunities are governed by schedules  28  in schedule repository  26 . VC repository  34  provides information including the rate and affiliated schedule  28  for each virtual connection  36 . 
     Broadly, reservation system  20  manages transmission opportunities for virtual connections  36  according to multiple schedules  28 . A transmission process  38  uses reservation system  20  to determine when to offer a transmission opportunity to a given virtual connection  36 . 
     Reservation system  20 , schedule repository  26 , VC repository  34 , and transmission process  38  are component software processes of routing/shaping software  30 . In general, routing/shaping software  30  includes software processes that control the operation of a router/traffic shaper  40  (shown in  FIG. 2 ). 
     The inner workings of transmission process  38  are beyond the scope of the description. Transmission process  38  is a software process that controls transmissions of network traffic by router/traffic shaper (to be discussed below). 
     Referring to  FIG. 2 , a router/traffic shaper  40  is a networking device. Router/traffic shaper  40  includes components such as main memory  42   a , storage  42   b , one or more processors  42   c , network interface  42   d , and bus  42   e  interconnecting components  42   a - d . Main memory  42   a  and storage  42   b  store computing instructions and data readable by a processor  42   c . Main memory  42   a  is random-access memory. Storage  42   b  is non-volatile storage such as a disk drive, programmable memory, writable media, or non-writable media. Processor  42   c  can access and transfer computing instructions, such as router/shaper software (Item  30 ,  FIG. 1 ), between main memory  42   a  and storage  42   b . Furthermore, processor  42   c , which contains multiple registers  48 , executes computing instructions of router/shaper software (Item  30 ,  FIG. 1 ). 
     In the present embodiment, router/traffic shaper  40  is a networking device conforming to architecture standards for the Intel IXP series of network processors, manufactured by Intel Corporation, Santa Clara, Calif. In this case, processor  42   c  is an Intel IXP 1200, and registers  48  each hold 32 bits. 
     Network interface  42   d  includes physical ports  44   a  and  44   b , which carry communication between network interface  42   d  and a network  46 . Network interface  42   d  provides logical access to physical ports  44 . Transmission process  38  controls transmissions of network traffic by router/traffic shaper  40  onto network  46 . 
     In the Intel IXP1200 architecture, bit addressing is conventional, i.e., the least significant bit of a byte is rightmost. Byte addressing is little-endian, i.e., less significant bytes have lower addresses. 
     Referring now to  FIG. 3A , schedule repository  26  is a source of information on schedules (Item  28 ,  FIG. 1 ). Schedule repository  26  includes a schedule space  50 , which is divided into 64K (i.e., two to the sixteenth power) slots  52 . A slot  52  represents a unit of time for possible transmission of a cell. Slots  52  can be reserved for use by virtual connections (Item  36 ,  FIG. 1 ) as will be described. Slots  52  are sequenced relative to one another in schedule space  50  according to a timing sequence  54 . Schedule space  50  has a schedule space start  50   a  and a schedule space end  50   b  which correspond to its first and last slots  52 , respectively. 
     Schedule space  50  includes one or more schedules  28   a ,  28   b ,  28   c . There can be many hundreds of schedules  28   a ,  28   b ,  28   c  in schedule space  50 . In general, a schedule  28   a ,  28   b ,  28   c  describes when to transmit cells to a network. The transmissions described by a schedule  28   a ,  28   b ,  28   c  can have local or remote origins, relative to router/traffic shaper (Item  40 ,  FIG. 2 ). That is, a schedule  28   a ,  28   b ,  28   c  can govern the local behavior of the router/traffic shaper  40  in its capacity as a store-and-forward network device on network  46 . Alternatively, a schedule  28   a ,  28   b ,  28   c  can govern transmissions in other devices or systems than router/traffic shaper (Item  40 ,  FIG. 2 ). For instance, router/traffic shaper (Item  40 ,  FIG. 2 ) could manage schedules  28   a ,  28   b ,  28   c  for other devices or systems accessible via network (Item  46 ,  FIG. 2 ) each for a different port, network domain, or the like. 
     Each schedule  28   a ,  28   b ,  28   c  is encoded in schedule space  50  as a contiguous block of slots  52  in schedule space  50 . Schedules  28   a ,  28   b ,  28   c  therefore represents a block of time that is divided into slots  52 . Each schedule  28   a ,  28   b ,  28   c  has a schedule start  56  and a schedule end  58  which correspond to its first and last slots  52 , respectively. 
     Referring now to  FIG. 3B , schedule space (Item  50 ,  FIG. 3   a ) describes a finite amount of time divided into schedule slots (Item  52 ,  FIG. 3   a ). The amount corresponds to a transmission cycle  51  that repeats with a regular period in time. Typically, the transmission cycle describes a window of transmission choices made by a transmission process (Item  38 ,  FIG. 1 ) of router/traffic shaper (Item  40 ,  FIG. 2 ). 
     Periodic repetition maps the transmission cycle  51  forward in time. Repetition creates a correspondence between a finite amount of time (corresponding to a transmission cycle) and an arbitrarily large amount of time (corresponding to the future transmission choices of transmission process; item  38 ,  FIG. 1 ). In particular, any future transmission choice corresponds to some unique iteration of the transmission cycle. 
     Furthermore, transmission cycle repeats with a regular period. The timing of events governed by schedule space (Item  50 ,  FIG. 3   a ) is therefore predictable, at least until the configuration of schedule space (Item  50 ,  FIG. 3   a ) changes. 
     Referring now to  FIG. 4 , VC repository  34  is a source of virtual connection information. VC repository  34  includes a VC schedule map  60  and collection of virtual connections  36 . 
     A virtual connection  36  includes a type  36   a  and rate information  36   b . Type  36   a  can adopt values consistent with ATM Forum Traffic Management Specification  4 . 1 . For instance, acceptable values for type  36   a  include constant bit rate (CBR), variable bit rate (VBR), and unspecified bit rate (UBR). 
     In general, rate information  36   b  describes traffic parameters for virtual connection  36 , such as for quality-of-service contracts or bandwidth allocations. Rate information  36   b  includes fields for PCR (“peak cell rate”)  62   a  and MBS (“maximum burst size”)  62   b . PCR  62   a  describes a maximum data rate at which virtual connection  36  is specified to operate, measured as an average over time. MBS  62   b  describes the maximum number of sequential cells that can be sent at PCR  62   a  on virtual connection  36  instantaneously (or within a small window of instantaneously, relative to the measurement of PCR  62   a ). 
     Some types of rate information  36   b  depend on the value of type  36   a . For example, virtual connections  36  with a VBR value for type  36   a  include a field for sustained cell rate (SCR)  62   c . SCR  62   c  describes a minimum data rate at which virtual connection  36  is specified to operate, measured as an average over time. Alternatively, a virtual connection  36  with a non-VBR value for type  36   a  can include a minimum cell rate (MCR)  62   d . A third possibility is a UBR virtual connection  36  that has a zero-valued MCR  62   d , indicating that there is no minimum rate associated with them. 
     VC schedule map  60  associates virtual connections  36  with schedules  28 . 
     Broadly speaking, a hierarchical reservation vector (to be discussed below) is a data structure that tracks whether slots (Item  52 ,  FIG. 3   a ) in schedule space (Item  50 ,  FIG. 3   a ) are reserved, i.e., have transmission commitments to a virtual connection  36 . 
     Referring now to  FIGS. 5A &amp; 5B , a hierarchical reservation vector  22  includes a first level  22   a , a second level  22   b , and a third level  22   c . In the present embodiment, third level  22   c  includes a left longword  70   a  and a right longword  70   b . Hierarchical reservation vector  22  also features a time direction  22   d , which organizes first level slots  72  into a sequence corresponding to their relative positions in time within the transmission cycle of schedule space. 
     First level  22   a  is a bit vector organized to correspond to schedule space  50 . First level  22   a  includes first level slots  72 , each of which is encoded as a bit that uniquely corresponds to a schedule space slot  52  in schedule space  50 . First level  22   a  has as many first level slots  72  as there are schedule space slots  52  in schedule space  50 —in this case, 64K. Time direction  22   d  is an ordering of first level slots  72  that corresponds to timing sequence (Item  54 ,  FIG. 3 ). 
     In the present embodiment, time direction  22   d  simply uses the ordering given by bit addressing in main memory (Item  42   a ,  FIG. 2 ). Thus, schedule space slots  52  and collections of schedule space slots  52  have corresponding locations in first level  22   a . In particular, a given schedule  28  in schedule space  50  corresponds to a schedule image  74  in first level  22   a . In this way, schedules  28  are encoded as variable-size arrays (schedule images  74 ) within hierarchical reservation vector  22 . 
     Second level  22   b  is a bit vector organized to correspond to first level  22   a  according to a scaling factor  78 . The scaling factor  78  is the number of bits in first level  22   a  that are represented (or “shadowed”) by a single bit in second level  22   b . The scaling factor  78  is constant throughout hierarchical reservation vector  22 . In the present embodiment, the scaling factor  78  has the value thirty-two. In  FIG. 5A , for visual simplicity and clarity, scaling factor  78  is drawn such that the scaling factor  78  is four. The value of thirty-two for scaling factor  78  is based on the word size of processor (Item  42   c ,  FIG. 1 ), i.e., the number of bits that can fit in register (Item  48 ,  FIG. 2 ). Each bit in second level  22   b  corresponds to a full word in first level  22   a . Conversely, every bit in first level  22   a  has one bit in second level  22   b  that shadows it. 
     Scaling factor  78  determines the size of second level  22   b  relative to the size of first level  22   a . Because first level  22   a  has 64K members, second level  22   b  has 2K (i.e., 2048) members. 
     Third level  22   c  relates to second level  22   b  in much the same way that second level  22   b  relates to first level  22   a . Each bit in third level  22   c  corresponds to a full word in second level  22   b , as determined by scaling factor  78 . Because first level  22   a  has 2048 members, therefore, second level  22   b  has 64 members. The first half of these is shadowed by left longword  70   a , while the second half is shadowed by right longword  70   b.    
     Reservations are represented in hierarchical reservation vector  22  as follows. A bit off in first level  22   a  (i.e., a value of a slot  72 ) indicates the corresponding slot  52  is reserved. A bit off in second level  22   b  indicates all of the bits it shadows are off in the next lower level, i.e., all of the corresponding first level slots  72  are reserved. Therefore, a bit on at second level  22   b  indicates at least one of its shadowed first level slots  72  is available. Similarly, a bit off at third level  22   c  indicates all of the bits it shadows are off in lower levels, i.e., 1024 first level slots  72  are reserved. A bit on at third level  22   c  indicates at least one of the 1024 first level slots  72  it represents is available. 
     Referring now to  FIG. 6 , a vector address  80  is a 16-bit unsigned binary integer that describes hierarchical reservation vector  22 . Vector address  80  describes a bit position of a first level slot  72  within first level  22   a . Vector address  80  also describes bit positions of shadowing bits in second level  22   b  and third level  22   c.    
     The bits of vector address  80  are numbered sequentially from least significant to most significant. Thus, the least significant bit of vector address  80  is numbered zero, and the most significant bit is numbered fifteen. 
     Vector address  80  is organized into portions that yield offsets  82   a ,  82   b ,  82   c  into levels of hierarchical reservation vector  22 , when the portions are evaluated as unsigned binary integers. For example, treated as a 16-bit unsigned binary integer, the entire vector address  80  is an offset into the 64K bits of first level  22   a , shown as first level offset  80   a . Conversely, every first level slot  72  has a unique value, representing its offset position in first level  22   a , that can be represented as a vector address  80 . 
     Vector address  80  includes a second-level sub-address  80   b , stored in bits five through fifteen of vector address  80 . Note that the scaling factor (Item  78 ,  FIG. 5   a ) is such that first level slots  72  are grouped together in groups of thirty-two. Also note that for a given 11-bit prefix on a 16-bit unsigned binary integer (that is, for fixed values of bits five through fifteen) there are precisely thirty-two such integers that have that prefix. (A prefix of length N is the N most significant bits.) Further note that 11 bits is precisely the number of bits necessary to address the 2048 members of second level  22   b . Vector address  80  takes advantage of these inherent properties of unsigned binary integers to use bits five through fifteen as second-level sub-address  80   b , describing an offset  82   b  into second level  22   b . In particular, for a given first level slot  72  having a vector address  80 , the offset of its corresponding shadowing bit in second level  22   b  is given by second-level sub-address  80   b.    
     Vector address  80  includes a third-level sub-address group  84 , stored in the six bits numbered ten through fifteen of vector address  80 . Third-level sub-address group  84  is divided into a branch sub-address  80   d  and a third-level sub-address  80   c . Note that the six bits of third-level sub-address group  84  use several of the same principles of unsigned binary integers that define the value of second-level sub-address  80   b . A given 6-bit prefix of a 16-bit value is held in common by a group of 1024 distinct values, which is a size that corresponds exactly to the shadowing of 1024 first level slots  72  as already described. Furthermore, the 6-bit prefix also corresponds to a shadowed group when considered only as the prefix of the 11-bit second-level sub-address  80   b . That is, a given 6-bit prefix is held in common by a group of 32 distinct 11-bit values. Thus, third-level sub-address group  84  could be used as an offset into third level  22   c , but this is not how vector address  80  is structured in the present embodiment. Instead, third level  22   c  is divided into two 32-bit arrays, namely, left longword  70   a  and right longword  70   b . Bit fifteen of vector address  80  is used to specify the branch to use, while bits ten through fourteen are used as an offset into the particular array. An advantage of this branched approach is that each of left longword  70   a  and right longword  70   b  can be placed entirely in register  48  of the processor (Item  42   c ,  FIG. 2 ). The fact that an entire array (or a significant portion of one) can be stored in register  48  or processed in native operations of processor  42   c  is beneficial to certain manipulations of hierarchical reservation vector  22 . For instance, it is useful if the processor (Item  42   c ,  FIG. 2 ) supports finding the first set bit in a 32-bit array, as will be explained in regards to circular priority find procedure (to be explained below). Thus, for sufficiently small lengths of bit arrays in hierarchical reservation vector  22 , addressing the arrays via the branching approach used for third-level sub-address  80   c  may have advantages over the non-branched approach used for second-level sub-address  80   b.    
     Referring now to  FIG. 7 , a range  91 ′,  91 ″ associates a virtual connection (Item  36 ,  FIG. 4 ) with a schedule image  74 ′,  74 ″ in the hierarchical reservation vector (Item  22 ,  FIG. 6 ). Therefore, a range (e.g.,  91 ′) can describe a period of time in which a reservation can be made for the virtual connection (Item  36 ,  FIG. 4 ) that would satisfy both the traffic parameters of the virtual connection (Item  36 ,  FIG. 4 ) and the time constraints of a schedule image (e.g.,  74 ′). 
     For example, range  91 ′ includes a could-send reference  91   a ′ and a must-send reference  91   b ′. Together, could-send reference  91   a ′ and a must-send reference  91   b ′ specify one or more contiguous blocks of first level slots (Item  72 ,  FIG. 6 ) in hierarchical reservation vector (Item  22 ,  FIG. 6 ), such that the blocks occur within the boundaries of the schedule image  74 ′. 
     Could-send reference  91   a ′ specifies a could-sent slot  74   a ′, while must-send reference  91   b  specifies a must-send slot  74   b ′. The relative position of could-sent slot  74   a ′ and must-send slot  74   b ′ in schedule image  74 ′ determines at least two possible values for a range topology  91   c ′. When could-sent slot  74   a ′ occurs before must-send slot  74   b ′ with regards to time direction (Item  22   d ,  FIG. 5   a ) of hierarchical reservation vector (Item  22 ,  FIG. 5   a ), topology  91   c , has a contiguous range  100 . 
     Alternatively, for example, when could-sent slot  74   a ″ occurs after must-send slot  74   b ″, topology  91   c ″ has a wrapped range  102 . 
     In schedule image  74 ′, contiguous range  100  is a contiguous block of slots, which begins with could-send slot  74   a ′ and ends with must-send slot  74   b′.    
     For schedule image  74 ″, wrapped range  102  includes a high component  102   b  and a low component  102   a , each of which is a contiguous block of slots in schedule image  74 ″. Low component  102   a  begins with could-send slot  74   a ″ and ends with the last slot of schedule image  74 ″. Low component  102   a  represents an earlier time than high component  102   b , due to the wrap. High component  102   b  begins with the first slot of schedule image  74 ″ and ends with must-send slot  74   b ″. Conceptually, wrapped range  102  begins with could-send slot  74   a ″, continues uninterrupted to the last slot of schedule image  74 ″, wraps to the first slot of schedule image  74 ″, and ends with must-send slot  74   b ″. This conceptual wrapping of wrapped range  102  reflects the cyclical structure of schedules (Item  28 ,  FIG. 1 ) and their corresponding schedule images (e.g.,  74 ). 
     Reservation system  20  includes reservation procedures  24  (to be discussed below). Broadly speaking, reservation procedures maintain and inspect schedule information stored in hierarchical reservation vector (Item  22 ,  FIG. 6 ). For instance, various reservation procedures set, clear, and detect slot reservations in the schedule space (Item  50 ,  FIG. 3   a ) as it is represented in hierarchical reservation vector (Item  22 ,  FIG. 6 ). 
     Referring now to  FIG. 8 , reservation procedures  24  include a shape procedure  90 , a schedule next slot procedure  92 , a circular priority find procedure  94 , a zeroes-compensation procedure  98 , a schedule bit set procedure  96 , and a schedule bit clear procedure  97 . 
     Broadly, shape procedure  90  determines a range (e.g., range  91 ″,  FIG. 7 ) for a given virtual connection (Item  36 ,  FIG. 1 ) associated with a schedule (Item  28 ,  FIG. 1 ). Given a virtual connection (Item  36 ,  FIG. 1 ) having traffic parameters, shape procedure  90  calculates a could-send time, which is the earliest time the next cell can be sent according to the traffic parameters. Shape procedure  90  also calculates a must-send time, which is the latest time the next cell can be sent according to the traffic parameters. Shape procedure  90  correlates these times to slots (Item  72 ,  FIG. 6 ) in the hierarchical reservation vector (Item  22 ,  FIG. 6 ). 
     Referring now to  FIG. 9 , shape procedure  90  receives as input a virtual connection and a base slot index (i.e., process  90   a ). Virtual connection is associated with a schedule, in that schedule has a schedule image in hierarchical reservation vector. The base slot index references a first-level slot that corresponds to current absolute time, i.e., the time at which the shape procedure  90  is executing. 
     Shape procedure  90  examines the rate of virtual connection to determine a maximum permissible current transmission speed, then expresses this speed as a could-send offset (i.e., process  90   b ). The could-send offset is a count of first-level slots. Maximum permissible current transmission speed is calculated based on the current state of virtual connection and its traffic parameters. Generally, the maximum permissible current transmission speed is the lesser of an overall maximum, given by PCR, and a situational maximum based on burst size, given by MBS. 
     Shape procedure  90  tests whether the could-send offset added to the base slot index yields a slot before the end of the current schedule (i.e., process  90   c ). If the test is positive, shape procedure  90  designates that slot as the could-send slot (i.e., process  90   d ). If the test is negative, shape procedure wraps the offset to the corresponding slot within schedule (i.e., process  90   e ), then designates the wrapped slot as the could-send slot (i.e., process  90   d ). 
     Shape procedure  90  also examines the rate of virtual connection to determine a minimum permissible current transmission speed, expressing this speed as a must-send offset (i.e., process  90   f ). The must-send offset is a count of first-level slots. Minimum permissible current transmission speed is calculated based on the type and traffic parameters of virtual connection. For instance, for a VBR virtual connection, the calculation uses SCR (Item  62   c ,  FIG. 4 ). Alternatively, for a non-VBR virtual connection (Item  36   a ,  FIG. 1 ) that has a minimum, the calculation uses MCR (Item  62   d ,  FIG. 1 ). 
     Shape procedure  90  then tests whether the must-send offset added to the base slot index yields a slot before the end of the current schedule (i.e., process  90   g ). If the test is positive, shape procedure  90  designates that slot as the must-send slot (i.e., process  90   h ). If the test is negative, shape procedure  90  wraps the offset to the corresponding slot within schedule and designates the wrapped slot as the must-send slot (i.e., process  90   i ). 
     Broadly speaking, unless schedule next slot procedure encounters a failure condition, as will be explained, schedule next slot procedure starts at the highest level of hierarchical reservation vector and repeatedly applies circular priority find procedure at each successive level, until reaching first level and finding a first level slot. The slot, if found, is the first available slot within a given range. 
     Referring now to  FIG. 10 , schedule next slot procedure  92  first determines which branch (e.g., items  70   a  and  70   b ,  FIG. 5   a ) of hierarchical reservation vector (Item  22 ,  FIG. 6 ) is appropriate to the could-send reference (i.e., procedure  92   a ). Schedule next slot procedure inspects branch sub-address of the could-send reference, which is a vector address. For example, in the described embodiment, where branch sub-address can be stored in one bit, schedule next slot procedure  92  determines the branch by testing the bit of branch sub-address. If the bit is on, schedule next slot procedure  92  selects the left longword  70   a . Otherwise, schedule next slot procedure  92  selects the right longword  70   b.    
     Schedule next slot procedure  92  then invokes recursive slot subroutine (i.e., procedure  92   b ). Generally, starting from an arbitrary location within a branch, recursive slot subroutine either finds a first available slot subject to a range and a schedule image, or returns a failure result (e.g., if no such slot is available). Schedule next slot procedure  92  provides recursive slot subroutine with the range that schedule next slot procedure received as inputs, and also provides the top level of the branch and a zero offset into that branch. 
     Schedule next slot procedure  92  next tests the output of recursive slot subroutine (i.e., procedure  92   c ). If the recursive slot subroutine returns a slot, schedule next slot procedure  92  returns that slot as a result value (i.e., procedure  92   d ). Otherwise, schedule next slot procedure  92  tests whether the given range spans a subsequent branch (i.e., procedure  92   e ). If such a spanning exists, schedule next slot procedure  92  loops back to select the next branch, according to the ordering given by time direction and the range topology (i.e., procedure  92   a ). Thus, schedule next slot procedure  92  continues evaluating branches according to the ordering given by time direction until either the entirety of range has been searched, or an available slot has been found. For a range topology having a contiguous range, the ordering of branches is that given by time direction over contiguous range. For a range topology having a wrapped range however, the ordering of branches has two parts: that given by time direction over high component, followed by the same ordering over low component. 
     If the test of procedure is negative, schedule next slot procedure  92  returns a result indicating failure (i.e., procedure  92   f ). 
     Referring now to  FIG. 11 , recursive slot subroutine  93  takes as input a range, a schedule image, a level of hierarchical reservation vector, and an offset within that level. The offset specifies a unique longword within the given level. Recursive slot subroutine returns a first available slot after the starting point and within the range, or a failure result. 
     Recursive slot subroutine  93  invokes a primary instance of circular priority find (Item  94 ,  FIG. 8 ) on the longword specified by the offset (i.e., process  93   a ). As will be explained, circular priority find (Item  94 ,  FIG. 8 ) returns a first set bit within a longword. This discussion will refer to that bit as the “primary bit”. If the level given to recursive slot subroutine  93  is first level, the primary bit represents a slot that is available to be allocated. For higher levels such as second level and above, the primary bit shadows a block of slots, at least one of which is available to be allocated. Moreover, since bits of the longword are ordered according to time direction, the primary bit typically represents a first available allocation opportunity. An exception to this general rule occurs for degenerate cases, as will be explained. 
     Recursive slot subroutine  93  next invokes a secondary instance of circular priority find on the portion of the longword, if any, that follows the bit position returned by the primary instance of circular priority find (i.e., process  93   b ). The bit returned by the secondary instance of circular priority find, if any, represents a next available allocation opportunity, subsequent to the first. This discussion will refer to that bit as the “secondary bit”. Process  93   b  also sets a “fallback flag” to a true/false value, initially indicating whether the secondary bit is available as a fallback alternative to the primary bit. 
     Recursive slot subroutine  93  tests the result of the primary instance of circular priority find (i.e., process  93   c ). If the primary bit was successfully found, recursive slot subroutine  93  uses the primary bit as a working bit (i.e., process  93   d ). The working bit is a candidate for the bit that recursive slot subroutine  93  will return. Otherwise, if a primary bit was not found, recursive slot subroutine  93  tests the fallback flag (i.e., process  93   e ). If the fallback flag is true, recursive slot subroutine  93  uses the secondary bit as the working bit and sets the fallback flag value to false (i.e., process  93   f ). 
     If the fallback flag is false, recursive slot subroutine  93  returns a failure result (i.e., process  93   g ). 
     Following a selection of the working bit, recursive slot subroutine  93  tests whether the current level of hierarchical reservation vector is the first level (i.e., process  93   h ). If the current level is the first level, recursive slot subroutine returns the working bit as a result value representing a slot (i.e., process  93   k ). Otherwise, if the current level is not the first level, an opportunity exists to recurse from the current level to a next level, toward first level, such that the next level includes a longword shadowed by the working bit. If such a next level exists, recursive slot subroutine  93  begins processing the next level at the longword shadowed by the working bit, using the same range as was passed to recursive slot subroutine  93  (i.e., process  93   i ). For example, a current instance of recursive slot subroutine  93  can pass control to a dependent instance of recursive slot subroutine  93 , where the dependent instance executes to completion before returning control to the current instance. In general, unless failure conditions occur, this pattern of recursive control-passing repeats until recursive slot subroutine  93  processes a longword at first level. The number of repetitions is therefore bounded by the number of levels between first level and the level passed to the top-level instance of recursive slot subroutine  93 . 
     Process  93   i  can return a problem result, comparable to that returned by recursive slot subroutine  93  itself. In the absence of a problem result, however, process  93   i  continues a recursive chain that eventually reaches first level. Thus, if process  93   i  returns a bit, that bit represents a first-level slot. 
     Recursive slot subroutine  93  tests the result of process  93   i  via process  93   m . If a problem result is found, recursive slot subroutine  93  goes to process  93   e  to test the fallback flag and proceeds from there as already described. Otherwise, if no problem result is found, recursive slot subroutine  93  uses the bit returned by process  93   i  as the working bit (i.e., process  93   n ). Recursive slot subroutine  93  then returns the working bit as a result value representing a slot (i.e., process  93   k ). 
     Circular priority find procedure (Item  94 ,  FIG. 8 ) takes as inputs a range and a longword of hierarchical reservation vector. Circular priority find procedure (Item  94 ,  FIG. 8 ) returns a first set bit, or an error if no first set bit exists. In the present embodiment, the first set bit is the least significant bit which is not off and which is in the intersection of the longword and the range. 
     Referring now to  FIG. 12 , circular priority find procedure  94  tests whether the given range has a could-send reference which is less than its must-send reference (i.e., process  94   a ). This is equivalent to testing whether the given range has a contiguous range topology. If the range is contiguous, circular priority find procedure  94  creates a contiguous mask (i.e., process  94   b ). Contiguous mask is a bit mask that selects for bits of the longword that correspond to the range topology of range, using exclusive-or (“XOR”) bit operations. Contiguous mask is a longword. Thus, there is a one-to-one correspondence between contiguous mask and the longword passed as input to circular priority find procedure  94 . A bit in contiguous mask is on if the corresponding slot in hierarchical reservation vector is covered by the range topology of range. 
     Next, circular priority find procedure  94  applies contiguous mask to the longword and finds the first set bit in the result (i.e., process  94   c ). In the present embodiment, circular priority find procedure  94  can take advantage of a hardware-supported processor operation of processor to find the first set bit in a longword. Circular priority find procedure  94  returns the resulting bit or indicates that no such bit exists. This can happen, for instance, if all bits in the intersection of the range  91  and the given longword represent slots that are already allocated. 
     When the range  91  is not contiguous, circular priority find procedure  94  creates a low mask and a high mask (i.e., process  94   d ). In this case, range topology has a wrapped range. Low mask is a mask that selects bits of the input longword that correspond to the low component of wrapped range. Similarly, high mask is a mask that selects bits of the input longword that correspond to the high component of wrapped range. 
     Next, circular priority find procedure  94  applies low mask to the input longword and finds the first set bit in the result (i.e., process  94   e ). Circular priority find procedure  94  then determines whether process  94   e  found a set bit (i.e., process  94   f ). If so, circular priority find procedure  94  returns the resulting bit. Otherwise, circular priority find procedure  94  applies high mask to the input longword and finds the first set bit in that result (i.e., process  94   g ). Circular priority find procedure  94  returns the resulting bit or indicates that no such bit exists. 
     One advantage of reservation system applies to lookups of the first available time slot in a contiguous range of time slots—for instance, by the schedule next slot procedure. The hierarchy encoded in hierarchical reservation vector allows lookups to take advantage of register-based processor operations. This reduces the number of memory accesses needed to accomplish the lookup, relative to approaches that use processor operations that cannot be accomplished within the registers. 
     For example, a three-level hierarchical reservation vector keeps reservations for multiple calendars over 64K time slots. A processor provides 32-bit memory accesses and a 32-bit circular find first bit set. The hierarchical reservation vector keeps its top level (level  3 ) in two local registers as 64-bits. The reservation system can perform a search over the 64K time slots in four operations. One memory reference and a circular find first bit set reduces the candidates to 2048 time slots, while a second memory reference and another circular find first bit set to reduce the candidates to one. 
     In another advantage, the reservation system also supports circular lookups, i.e. lookups within a schedule where the range of possible values wraps around the end of the schedule and continues from the beginning of the schedule. 
     Still another advantage of the hierarchical reservation vector is a relatively small footprint in memory for its representation of the schedule space. 
     A number of embodiments have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the description. 
     In the described embodiment, schedule repository and VC repository are component software processes of routing/shaping software. In other embodiments, schedule repository or VC repository (or both) could be applications or services external to routing/shaping software. Indeed, schedule repository or VC repository (or both) could be external to router/traffic shaper—for instance, they could remote software in communication with routing/shaping software via network. In other embodiments, slots can be reserved to entities other than virtual connections. 
     The details of one or more embodiments are set forth in the accompanying drawings and the description below. Other features, objects, and advantages will be apparent from the description and drawings, and from the claims. Accordingly, other embodiments are within the scope of the following claims.

Technology Category: 5