Method and apparatus for source rate pacing in an ATM network

Claim 3

The method according to claim 1 further comprising the step of preallocating entries on the timing ring for scheduling transmission of packets of one or more additional virtual circuits.

Claim 4

The method according to claim 2 wherein the processing step comprises placing packets into a transmit buffer to await transmission onto the network.

Claim 5

The method according to claim 3 wherein the dynamically allocating step occurs initially at virtual circuit establishment and thereafter when a packet scheduled by a dynamically allocated entry is placed into the transmit buffer.

Claim 6

The method according to claim 4 further comprising the step of delaying the transmission of a packet onto the network for a number of cell transmission times equivalent to the number of previous ring entries for which no packets were placed into the transmit buffer.

Claim 7

The method of claim 1, wherein the static action fields and dynamic action fields are on the same timing ring.

Claim 8

The method of claim 1, wherein the static action fields are on a first timing ring, and the dynamic action fields are on a second parallel timing ring.

Claim 9

The method of claim 1, wherein each field contains either a NULL pointer or an address pointer to a location in a data structure defining an action to be taken during the interval.

Claim 10

The method of claim 8, further comprising: determining whether a static action is scheduled for a time slot; if a static action is scheduled for the time slot, determining whether requisite data necessary to execute the static action is available; and if no static action is scheduled or if the requisite data is not available, executing a dynamic action during the time slot.

Claim 11

The method of claim 1, wherein only a single action is allocated to each static action field.

Claim 12

The method of claim 10, wherein the single action is performed during the time interval corresponding to the static action field to which the single action is assigned.

Claim 13

A packet transmission apparatus for scheduling the transmission of packets in a packet switching network, comprising: at least one timing ring containing entries for scheduling transmission of packets on one or more virtual circuits, wherein each entry represents an available slot for scheduling transmission of a single packet, and wherein each entry comprises a static action field and a dynamic action field and; a processor for sequentially processing the entries on the ring so as to transmit packets onto the network during their scheduled time slots or the first available time slot thereafter, wherein both the static action field and the dynamic action field are read to determine, for each entry, the actions to be performed for the scheduled transmission of packets.

Claim 14

A packet transmission apparatus for scheduling the transmission of packets in a packet switching network, comprising: at least one timing ring containing entries for scheduling transmission of packets on one or more virtual circuits, wherein each entry represents an available slot for scheduling transmission of a single packet, and wherein each entry comprises a static action field and a dynamic action field and; a processor for sequentially processing the entries on the ring so as to transmit packets onto the network during their scheduled time slots or the first available time slot thereafter, wherein both the static action field and the dynamic action field are read to determine, for each entry, the actions to be performed for the scheduled transmission of packets.

Claim 15

The packet transmission apparatus of claim 12, wherein the static action fields and dynamic action fields are on the same timing ring.

Claim 16

The packet transmission apparatus of claim 12, wherein the static action fields are on a first timing ring, and the dynamic action fields are on a second parallel timing ring.

Claim 17

The packet transmission apparatus of claim 12, wherein each field contains either a NULL pointer or an address pointer pointing to a location in a data structure defining an action to be taken during the interval.

Claim 18

The packet transmission apparatus of claim 12, wherein the processor is adapted to: determine whether a static action is scheduled for a time slot; if a static action is scheduled for the time slot, determine whether requisite data necessary to execute the static action is available; and if no static action is scheduled or if the requisite data is not available, execute a dynamic action during the time slot.

Claim 19

The packet transmission apparatus of claim 12, wherein only a single action is allocated to each static action field.

Claim 20

The packet transmission apparatus of claim 12, wherein the single action is performed during the time interval corresponding to the static action field to which the single action is assigned.

Claim 21

The packet transmission apparatus of claim 12 wherein the timing ring includes entries preallocated for the scheduling of the transmission of packets of one or more additional virtual circuits.

Claim 22

The packet transmission apparatus of claim 19 wherein the packet switching network is an ATM network.

Claim 23

The packet transmission apparatus of claim 20 wherein the preallocated entries on the timing ring correspond to CBR or real-time VBR virtual circuits.

Claim 24

The packet transmission apparatus of claim 21 wherein the preallocated entries on the timing ring corresponding to a single virtual circuit are spaced at fixed integral intervals.

Claim 25

The packet transmission apparatus of claim 20 wherein the dynamically allocated entries on the timing ring correspond to ABR, UBR and non-realtime VBR virtual circuits.

Claim 26

The packet transmission apparatus of claim 23 wherein only one dynamically allocated entry per virtual circuit is present on the timing ring at any one time.

Claim 27

The packet transmission apparatus of claim 19 wherein an entry is dynamically allocated for a virtual circuit initially at connection set-up time and subsequently after a previously dynamically allocated entry for that virtual circuit has been processed.

Claim 28

The packet transmission apparatus of claim 25 wherein the next entry to be dynamically allocated for a virtual circuit is a fixed integral number of entries following the currently processed entry.

Claim 29

The packet transmission apparatus of claim 26 wherein the fixed integral number is modified by adding or subtracting one entry after a fixed number of packets on that virtual circuit have been transmitted.

Claim 30

The packet transmission apparatus of claim 35 wherein the next entry to be dynamically allocated for a virtual circuit is determined by moving a fixed integral number of entries following the currently processed entry and then linearly searching from that entry to find the first freely available entry.

Claim 31

The packet transmission apparatus of claim 19 wherein an entry on the timing ring may be both preallocated and dynamically allocated.

Claim 32

The packet transmission apparatus of claim 29 wherein a preallocated entry is represented by an action data structure specified by the corresponding static action field, and wherein a dynamically allocated entry is represented by a queue of action data structures specified by the corresponding dynamic action field.

Claim 33

The packet transmission apparatus of claim 30 wherein the processor processes an allocated ring entry by placing the queue of action data structures onto a latent queue, and if preallocated, by performing the action indicated by the action data structure specified by the static action field.

Claim 34

The packet transmission apparatus of claim 30 wherein the processor processes an allocated ring entry by placing the queue of action data structures onto a latent queue and by performing the action indicated by the action data structure at the head of the latent queue.

Claim 35

The packet transmission apparatus of claim 31 wherein the processor processes a ring entry which has not been preallocated by performing the action indicated by the action data structure at the head of the latent queue.

Claim 36

The packet transmission apparatus of claim 33 wherein the action is performed by an action handler routine specified by the action data structure.

Claim 37

The packet transmission apparatus of claim 34 wherein the action performed includes the placing of a packet corresponding to a virtual circuit into a transmit buffer to await subsequent transmission onto the network.

Claim 38

The packet transmission apparatus of claim 35, wherein the transmit buffer is not permitted to become empty.

Claim 39

The packet transmission apparatus of claim 35, wherein a dummy packet is placed in the transmit buffer when no packet transmission is specified for a ring entry.

Claim 40

The packet transmission apparatus of claim 35 wherein the transmission of the packet is delayed by a number of packet transmission times equivalent to the number of previous ring entries for which no packet transmission was specified.

Claim 41

The packet transmission apparatus of claim 38 wherein the number of packet transmission times is encoded in the header of the packet to be transmitted.

Claim 42

The packet transmission apparatus of claim 34 wherein the action handler routine implements a state machine such that state changes occur as subsequent actions corresponding to a single virtual circuit are performed.

Claim 43

The packet transmission apparatus of claim 40 wherein the state machine implements AAL5 segmentation and transmission.

Claim 44

The packet transmission apparatus of claim 12 wherein a dynamically allocated entry is represented by a queue of action data structures specified by the corresponding dynamic action field.

Claim 45

A packet transmission apparatus for scheduling the transmission of packets in a packet switching network, comprising at least one timing ring containing entries allocated for scheduling transmission of packets on one or more virtual circuits, wherein an entry on the timing ring represents an available time slot for scheduling transmission of a single packet; and a processor for processing the entries on the timing ring to transmit packets onto the network during their scheduled time slots, wherein the processor is adapted to read both a static action field and a dynamic action field for each entry, so as to determine, for each time slot, the action to be performed for the scheduled transmission of said packet; the static action field enabling packet transmission on a single virtual circuit on its scheduled time slot and having a priority over the dynamic action field, whereby the dynamic action field enables packet transmission on the first available time slot thereafter.

Claim 46

A packet transmission apparatus for scheduling the transmission of packets in a packet switching network, comprising at least one timing ring containing entries allocated for scheduling transmission of packets on one or more virtual circuits, wherein an entry on the timing ring represents an available time slot for scheduling transmission of a single packet; and a processor for processing the entries on the timing ring to transmit packets onto the network during their scheduled time slots, wherein the processor is adapted to read both a static action field and a dynamic action field for each entry, so as to determine, for each time slot, the action to be performed for the scheduled transmission of said packet; the static action field enabling packet transmission on a single virtual circuit on its scheduled time slot and having a priority over the dynamic action field, whereby the dynamic action field enables packet transmission on the first available time slot thereafter.

Claim 47

The packet transmission apparatus of claim 43, wherein the processor delays the transmission of a packet onto the network for a number of packet transmission times equivalent to the number of previous ring entries for which no packets were placed into the transmit buffer.

Claim 48

The packet transmission apparatus of claim 44, wherein the number of packet transmission times is encoded in the header of the packet to be transmitted.

Claim 49

The packet transmission apparatus of claim 43, wherein the dynamic action field enables transmission on ABR, UBR, and non-real-time VBR virtual circuits; and the static action field enables transmission on CBR and real-time VBR virtual circuits.

Claim 50

The packet transmission apparatus of claim 43, further including data storage means, and wherein each dynamic action field physically contains either a null pointer or an address pointer to a data structure stored in said storage means; the null pointer indicating that the timing slot has not been allocated for scheduling a dynamic action, whereby no action need be performed; the address pointer indicating a queue of dynamic actions which become current during the time slot.

Claim 51

The packet transmission apparatus of claim 47, wherein the queue of dynamic actions maintained for each entry is a singly linked last-in, first-out queue.

Claim 52

The packet transmission apparatus of claim 43, wherein the processor processes a dynamic action field by placing the queue of dynamic actions onto a latent queue.

Claim 53

The packet transmission apparatus of claim 49, wherein the processor processes a ring entry which has not been preallocated by performing the action at the head of the latent queue.

Claim 54

The packet transmission apparatus of claim 50, wherein the action is performed by an action handler routine.

Claim 55

The packet transmission apparatus of claim 51, wherein the action handler routine implements a state machine such that state changes occur as subsequent actions corresponding to a single virtual circuit are performed.

Claim 56

The packet transmission apparatus of claim 52, wherein the state machine implements AAL5 segmentation and transmission.

Claim 57

Apparatus for scheduling transmission of packets on one or more virtual circuits in an ATM packet switching network, the apparatus comprising: a timing ring for static and dynamic entries, said static entries being made for preallocated static cell scheduling for use with CBR and real-time VBR virtual circuits, said dynamic entries being made for dynamic cell scheduling for use with ABR, UBR, and non real-time VBR circuits, and said ring simultaneously accomodating the static and dynamic entries at correspondingly scheduled time slots so that, when each time slot is reached, either the static or dynamic entry or both can be processed in order to transmit cells onto the network during their scheduled time slots; and processing means for processing, in a burst, a sequence of said entries on the respective time slots, said processing means being operative such that: (a) said static entries always cause the transmission of cells at allocated time slots, so that fixed transmission intervals are maintained for CBR and real-time VBR traffic, and (b) said dynamic queued entries form a linked list at a single scheduled time slot, said linked list is moved from said ring to a latent queue when said scheduled slot is reached, so that the latent queue can then be further processed, in a LIFO manner, in order to transmit each cell on said network, said further processing being such that, as each cell is transmitted on the network, the next cell transmission time is calculated and is added to the entries on said ring at the respective time slot, whereby said dynamic cell scheduling occurs at said scheduled time slot or during the next available time slot thereafter, whereby said ABR and non real-time VBR traffic is dynamically scheduled.

Claim 58

Apparatus for scheduling transmission of packets on one or more virtual circuits in an ATM packet switching network, the apparatus comprising: a timing ring for static and dynamic entries, said static entries being made for preallocated static cell scheduling for use with CBR and real-time VBR virtual circuits, said dynamic entries being made for dynamic cell scheduling for use with ABR, UBR, and non real-time VBR circuits, and said ring simultaneously accomodating the static and dynamic entries at correspondingly scheduled time slots so that, when each time slot is reached, either the static or dynamic entry or both can be processed in order to transmit cells onto the network during their scheduled time slots; and processing means for processing, in a burst, a sequence of said entries on the respective time slots, said processing means being operative such that: (a) said static entries always cause the transmission of cells at allocated time slots, so that fixed transmission intervals are maintained for CBR and real-time VBR traffic, and (b) said dynamic queued entries form a linked list at a single scheduled time slot, said linked list is moved from said ring to a latent queue when said scheduled slot is reached, so that the latent queue can then be further processed, in a LIFO manner, in order to transmit each cell on said network, said further processing being such that, as each cell is transmitted on the network, the next cell transmission time is calculated and is added to the entries on said ring at the respective time slot, whereby said dynamic cell scheduling occurs at said scheduled time slot or during the next available time slot thereafter, whereby said ABR and non real-time VBR traffic is dynamically scheduled.