Atm cell scheduler which uses a heap memory and associates timestamps with each channel

Abstract

A network hub and Asynchronous Transfer Mode (ATM) translator system (,) for use in a Local Area Network (LAN)-based communications system is disclosed. The network hub and ATM translator system (,) includes a host controller (,) that serves as the LAN hub, and which interfaces with a translator card (,) which includes a segmentation and reassembly device (,) in connection with SONET receive/transmit circuitry (,) that communicates with a transceiver (,) to transmit and receive ATM packet cells over a communications facility (FO). The translator card (,) also includes a scheduler (,) that includes a heap sort state machine (,) which maintains a sorted list of entries, in a heap fashion, in on-chip parameter memory (,) and off-chip parameter memory (,). The entries include, for each ATM channel, a channel identifier and a timestamp that indicates the time at which the next cell for the channel will be due for transmission. A due comparator (,) compares the timestamp of the root value in the heap (i.e., the channel with the next due cell) to a global time generated by a reference timer (,), and indicates to a source behavior processor (,) in the scheduler (,) that a cell is due for transmission. The scheduler than issues a transmit credit for the cell, and communicates this event with the SAR device (,) to effect the transmission as appropriate.