Method and system for processing multiple channel data

• US 5,563,885 A
• Filed: 05/24/1995
• Issued: 10/08/1996
• Est. Priority Date: 05/24/1995
• Status: Expired due to Term

• Current Assignee: Retro Reflective Optics
• Original Assignee: Loral Fairchild Corp. (Newell Brands Inc.)
• Inventors: Witchey, Michael D.
• Primary Examiner(s): Kizou, Hassan
• Application Number:
  US08/447,543
• Time in Patent Office: 503 Days
• Field of Search: 370/60, 370/60.1, 370/94.1, 370/94.2, 370/94.3, 370/84, 370/17, 370/85.6, 370/112, 395/200.13
• US Class Current: 370/391
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5672 Multiplexing, e.g. coding, scrambling
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and system for scheduling multiple channel data output. A multi-channel data processor stores ATM cells received from a network data input stream in channel FIFOs of a cell buffer. The input interval between cells received at a channel FIFO and the channel FIFO fullness is monitored to determine an optimum cell output interval for each channel. This optimum cell output interval is established such that the rate at which cells are output is substantially constant compared to the input cell rate and drives each channel FIFO fullness towards a nominal value. Optimum cell departure times are then calculated based on the optimum cell output interval for each channel. These optimum cell departure times are sorted and prioritized to create an overall optimum cell transmission schedule. By removing cells from channel FIFOs according to this optimal cell transmission schedule, data returns to the network having a restored temporal sequence in each channel without requiring embedded timing information. Establishing an output rate and sequence which optimizes FIFO fullness and minimizes gaps in the output data, also reduces buffering requirements for downstream network equipment.

Claims

1. A system for scheduling multiple channel data for asynchronous transport through a data network comprising:

buffering means for storing and outputting cells of multiple channel data received at varying rates from said network; and

processing means for scheduling cells to be removed from said buffering means such that data is output at a substantially constant rate in each respective channel back into said data network,

wherein said buffering means comprises a plurality of channel FIFOs having a nominal FIFO fullness and said processing means further includes means for scheduling cells to be removed from said channel FIFOs such that the FIFO fullness of said channel FIFOs are driven toward said nominal FIFO fullness.

2. The system according to claim 1, wherein said processing means further includes means for scheduling cells to be removed from said buffering means such that gaps in said data output in each channel back into the network are reduced compared to gaps in said data input into said buffering means to reduce delay in data transport and to lower buffering requirements for network equipment downstream from said buffering means.

3. The system according to claim 1, wherein said processing means schedules cells to be removed from said buffering means by determining cell departure times for said multiple channels of data and sorting said cell departure times.

4. A system for transporting data in multiple channels comprising:

buffering means for storing data received from said multiple channels, said buffering means including a plurality of channel FIFOs, wherein each channel FIFO stores cells of data corresponding to a respective channel;

processing means for generating a cell transmission schedule identifying a sequence of cells to be removed from said plurality of channel FIFOs; and

output means for outputting said cells from said channel FIFOs according to said sequence identified in said cell transmission schedule,

wherein said processing means comprises;

means for determining for each channel a cell input interval representative of the average cell input rate of cells received at the channel FIFO;

means for determining for each channel a deviation in current FIFO fullness from a nominal FIFO fullness;

means for determining for each channel a cell output interval, said cell output interval representing an average cell output rate for outputting cells in said channel FIFO to restore a temporal sequence in data output in said channel and to drive the current FIFO fullness of said channel FIFO towards said nominal FIFO fullness;

means for determining cell departure times for each channel based on said respective cell output interval and the number of cells in each channel FIFO; and

means for sorting said cell departure times to generate said cell transmission schedule.

5. The system according to claim 4, wherein said means for determining a cell input interval for each channel includes counters for counting the number of cells input during a schedule time period and means for dividing said number of cells inputted by said schedule time period.

6. The system according to claim 4, wherein said means for determining a cell input interval further includes means for filtering the input cell rate for each channel.

7. The system according to claim 4, wherein said means for determining a deviation includes means for determining current FIFO fullness comprising:

input and output counters for counting the number of cells input and output respectively from said channels FIFOs,

a subtractor for subtracting the number of cells output from the number of cells input to determine the net number of cells inserted on each channel during a schedule period, and

an adder for adding a previous FIFO fullness value, if any, based on said net number of inserted cells to determine said current FIFO fullness.

8. The system according to claim 4, wherein said means for determining a deviation further includes means for determining and filtering the current FIFO fullness for each channel.

9. The system according to claim 4, wherein said means for determining a cell output interval includes means for filtering said deviation for each channel.

10. The system according to claim 4, further comprising a plurality of cell departure time FIFOs corresponding to said channel, each cell departure time FIFO storing said cell departure times for data in a respective channel.

11. The system according to claim 10, wherein said cell transmission schedule comprises a period of cell egress times and said means for sorting said cell departure times comprises means for multiplexing cell departure time and channel identifier information from each cell departure time FIFO, said cell departure times being sorted by magnitude and further prioritized by channel in said multiplexing means and said channel identifiers corresponding to said multiplexed cell departure times being assigned to corresponding egress cell times covering said cell transmission schedule period.

12. The system according to claim 4, further comprising:

an input port for receiving said multiple channel data from an input data stream in said data network and providing said multiple channel data to said buffering means; and

wherein said output means includes an egress port for outputting said multiple channel data from said buffering means into an output data stream in said data network.

13. A method for asynchronous transport of multiple channel data through a data network comprising the steps of:

storing cells of multiple channel data received at varying rates from said data network in respective channel FIFOs; and

determining a schedule for removing said cells from said channel FIFOs such that said data is output from said channel FIFOS at a substantially constant rate in each respective channel,

wherein said schedule determining step further includes the step of scheduling cells to be removed from said channel FIFOs such that the FIFO fullness of said channel FIFOs are driven toward a nominal FIFO fullness.

14. The method according to claim 13 wherein said schedule determining step further includes the step of scheduling cells to be removed from said channel FIFOs such that gaps in said data output in each channel back into the data network are reduced compared to gaps in said data received from said data network.

15. The method according to claim 13 wherein said schedule determining step comprises the step of scheduling cells to be removed from said channel FIFOs by determining cell departure times for each of said cells and then sorting said cell departure times.

16. A method for asynchronous transport of multiple channel data through a data network comprising the steps of:

storing cells of multiple channel data received at varying rates from said data network in respective channel FIFOs; and

determining a schedule for removing said cells from said channel FIFOs such that said data is output from said channel FIFOs at a substantially constant rate in each respective channel,

wherein said schedule determining step comprises the steps of;

determining for each channel a cell input interval representative of the average cell input rate of cells received at the channel FIFO;

determining for each channel a deviation in current FIFO fullness from a nominal FIFO fullness;

determining for each channel a cell output interval, said cell output interval representing an average cell output rate for outputting cells in said channel FIFO to restore a temporal sequence in data output in said channel and to drive the current FIFO fullness of said channel FIFO towards said nominal FIFO fullness;

determining cell departure times for each channel based on said respective cell output interval and the number of cells in each channel FIFO; and

sorting said cell departure times to generate said cell transmission schedule.

17. The method according to claim 16, wherein said schedule determined in said schedule determining step comprises a period of cell egress times and said sorting step comprises the steps of:

multiplexing cell departure times and corresponding channel identifier information, said cell departure times being sorted by magnitude and further prioritized by channel to obtain a sequence of channel identifier information identifying in order in which cells are to be output from said channel FIFOs during said period of cell egress times.