EP0782303A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Adaptive time slot scheduling apparatus and method for end-points in an ATM network
Assignee: AT&T Inc
•
Filing: 1996-12-05
•
Granted: —
•
Expires: 2016-12-05
Abstract
Abstract A scheduling mechanism for satisfying specified Quality of Service (QoS) guarantees for each VC of an end-point host in an ATM network. The scheduling mechanism includes a time slot ring, a VC table and a pending queue. The time slot ring is an array, wherein each element represents a time slot. Each slot contains a pointer which contains the virtual channel identifier (VCID) which is to be serviced in this time slot. The VC table is an array of all the VC descriptors. The pending queue is used for queuing a new VC and also at a later time, when the scheduler is unable to find a time slot for a VC it is queued in the pending queue. The scheduler reads and processes one slot at a time at the maximum speed that the physical link will allow. The scheduler circularly services the slots in the ring continuously and a current slot pointer (CSP) points to the slot being serviced. For the current time slot, the scheduler first services the VC waiting on this slot, then schedules a new target time slot for this VC after marking the current slot empty. The target slot is calculated based on a cell-to-cell spacing parameter and a remainder mechanism is used to correct the average output cell rate to a required rate. In an alternate embodiment, the time slots within the ring are grouped into clusters. The ring contains cluster pointers which point to the first VC to be serviced. The rest of the VCs in the cluster are linked to the first VC. In order to accommodate different classes of service, each entry in the ring holds multiple cluster pointers.
Inventors
- 👤 Sunder Raj Rathnavelu
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 13:31
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5603; H04L2012/5609; H04L2012/5612; H04L2012/5614; H04L2012/5616; H04L2012/5638; H04L2012/5646; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
110 words
An apparatus for scheduling communications traffic from an end-point host over an ATM network, said apparatus comprising: a time slot ring including an array of time slots, wherein each of said time slots includes a virtual channel identifier (VCID) of a virtual channel (VC) to be serviced; a VC table including an array of VC descriptors, wherein said VCID stored in said time slot ring points to a VC descriptor in said VC table; processing means for scheduling said VCs in said time slots of said time slot ring, wherein said time slots are circularly processed in a continuous fashion thereby enabling scheduled transmission of ATM cells in said network.
Claim 2
Dependent Claim
22 words
The apparatus of Claim 1, further including a pending queue for queuing VCs prior to placement in one of said time slots.
Claim 3
Dependent Claim
55 words
The apparatus of Claim 1, further including a current slot pointer (CSP) for pointing to a current slot being serviced in said time slot ring, said processing means being operable to service a VC referenced by said CSP and to schedule a new target time slot for said VC after marking said current slot empty.
Claim 4
Dependent Claim
69 words
The apparatus of Claim 2, wherein said processing means is operable to check if a target slot in said time slot ring is empty, a non-empty slot being indicative of a collision, wherein a current VC is queued in said pending queue if said target slot is non-empty, and wherein a next VC in said pending queue is serviced upon encountering an empty slot in said time slot ring.
Claim 5
Dependent Claim
33 words
The apparatus of Claim 4, wherein said processing means is operable to transmit a dummy cell over said output link when said target slot is empty and said pending queue is also empty.
Claim 6
Dependent Claim
46 words
The apparatus of Claim 1, wherein said VC descriptor includes a remainder variable defined as the accumulated difference between required cell-to-cell spacing and actual cell-to-cell spacing for a VC, said remainder variable operable to ensure that said cell to cell spacing averages to said required spacing.
Claim 7
Dependent Claim
32 words
The apparatus of Claim 2, wherein a cell rate in said time slot ring is altered for different QOS requirements by altering said cell to cell spacing parameter in said VC descriptor.
Claim 8
Dependent Claim
30 words
The apparatus of Claim 4, wherein said processing means searches N consecutive time slots in said time slot ring upon encountering a collision to thereby locate an empty target slot.
Claim 9
Dependent Claim
32 words
The apparatus of Claim 8, wherein each said time slot in said time slot ring includes an empty bit variable, said empty bit variable indicative of whether said time slot is occupied.
Claim 10
Dependent Claim
47 words
The apparatus of Claim 1, wherein each of said VC descriptors in said VC table includes a cell-to-cell spacing parameter for each VC, wherein said cell-to-cell spacing parameter is defined as the transmission rate of said output link divided by a required cell rate for said VC.
Claim 11
Dependent Claim
39 words
The apparatus of Claim 1, further including admission control means for controlling total bandwidth required by all VCs in said time slot ring to ensure that said total bandwidth does not exceed the link speed of said output link.
Claim 12
Dependent Claim
74 words
The apparatus of Claim 1, wherein said time slot ring is divided into a plurality of clusters, each of said clusters including a predetermined number of slots indicative of a cluster_size, wherein each of said clusters includes at least first and second pointers of differing priority for accommodating transmission under various classes of service from said end-point, wherein multiple VCs for said first and second pointers in a cluster are linked to one another.
Claim 13
Dependent Claim
66 words
The apparatus of Claim 12, further including a current cell time pointer (CCTP), a current slot high priority pointer (CSHPP) and current slot low priority pointer (CSLPP), wherein only the higher priority queues associated with said first and second pointers of a cluster are serviced during backlog conditions in said time slot ring, a backlog condition being defined as a CCTP value/cluster_size > a CSHPP value.
Claim 14
Dependent Claim
25 words
The apparatus of Claim 13, wherein if a current cluster is empty, said processing means emits an unassigned cell before proceeding to a next cluster.
Claim 15
Dependent Claim
35 words
The apparatus of Claim 14, further including a burst_size variable, wherein each time a calculated target slot equals the current slot, a burst of cells according to said burst_size variable is transmitted over said link.
Claim 16
Dependent Claim
41 words
The apparatus of Claim 13, further including a Current Slot High Priority Pointer (CSHPP) and a Current Slot Low Priority Pointer (CSLPP) operable to point to the current high priority and currently low priority slots, respectively, which are currently being serviced.
Claim 17
Dependent Claim
26 words
The apparatus of Claim 1, wherein said time slot ring is included in internal cache of a segmentation and re-assembly (SAR) applications specific integrated circuit (ASIC).
Claim 18
Independent Claim
116 words
A method for scheduling communications traffic over an ATM network, said method comprising the steps of: providing a time slot ring including an array of time slots, wherein each of said time slots includes a virtual channel identifier (VCID) of a virtual channel (VC) to be serviced; referencing a VC table including an array of VC descriptors, wherein said VCID stored in said time slot ring points to a VC descriptor in said VC table, said VC descriptor including pertinent information regarding processing of a specific VC; and circularly processing said time slots of said time slot ring in a continuous fashion at a predetermined rate thereby enabling scheduled transmission of ATM cells in said network.
Claim 19
Dependent Claim
25 words
The method of Claim 18, further including the step of queuing VCs in a pending queue prior to placement in one of said time slots.
Claim 20
Dependent Claim
66 words
The method of Claim 19, wherein said time slot ring includes a current slot pointer (CSP) for pointing to a current slot being serviced in said time slot ring, further including the steps of: servicing a VC in said current slot of said time slot ring referenced by said CSP; and scheduling a new target time slot for said VC after marking said current slot empty.
Claim 21
Dependent Claim
63 words
The method of Claim 20, further including the step of: checking if a target slot in said time slot ring is empty, a non-empty slot being indicative of a collision, queuing a current VC in said pending queue if said target slot is non-empty, and servicing a next VC in a pending queue upon encountering an empty slot in said time slot ring.
Claim 22
Dependent Claim
74 words
The method of Claim 18, wherein said time slot ring is divided into a plurality of clusters, each of said clusters including a predetermined number of slots indicative of a cluster_size, wherein each of said clusters includes at least first and second pointers of differing priority for accommodating transmission under various classes of service from said end-point, wherein multiple VCs for said first and second pointers in a cluster are linked to one another.
Claim 23
Dependent Claim
78 words
The method of Claim 22, wherein said time slot ring includes a current cell time pointer (CCTP), a current slot low priority pointer (CSLPP) and a current slot high priority pointer (CSHPP) to point to the current low priority and high priority slots, respectively, which are being serviced, wherein only the higher priority queues are serviced during backlog conditions in said time slot ring, a backlog condition being defined as a (CCTP/ cluster_size) value > a CSHPP value.
Claim 24
Dependent Claim
25 words
The method of Claim 23, including the step of emitting an unassigned cell before proceeding to a next cluster if a current cluster is empty.
Claim 25
Dependent Claim
75 words
The method of Claim 18, wherein each of said VC descriptors in said VC table includes a cell-to-cell spacing parameter for each VC, wherein said cell-to-cell spacing parameter is defined as the transmission rate of said output link divided by a required cell rate for said VC, further including the step of altering a cell rate in said time slot ring for different QOS requirements by altering said cell-to-cell spacing parameter in said VC descriptor.
Claim 26
Dependent Claim
53 words
The method of Claim 25, including the step of calculating a remainder variable for inclusion in said VC descriptor, said remainder variable defined as the accumulated difference between required cell-to-cell spacing and actual cell-to-cell spacing for a VC, said remainder variable operable to ensure that said cell-to-cell spacing averages to said required spacing.
Claim 27
Dependent Claim
30 words
The method of Claim 21, including the step of searching N consecutive time slots in said time slot ring upon encountering a collision to thereby locate an empty target slot.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.