Earliest deadline first communications cell scheduler and scheduling method for transmitting earliest deadline cells first

US6028843A · kind A · utility

Assignee

• International Business Machines Corporation · US

Inventors

• Gary S. Delp · Rochester, US
• Victor Firoiu · Westford, US
• Roch Guerin · Newtown Square, US
• Philip Lynn Leichty · Rochester, US
• David Richard Poulter · Rochester, US
• Vinod Gerard John Peris · Croton-on-Hudson, US
• Rajendran Rajan · Philadelphia, US
• John H. Shaffer · Cleveland, US

Key dates

• Filing date: Mar 25, 1997
• Grant date: Feb 22, 2000
• Expiry date: Mar 25, 2017

Classification

• Technology area (CPC H): Electricity
• CPC primary: H04L2012/5679
• WIPO field: Telecommunications
• WIPO sector: Electrical engineering

Abstract

A method and apparatus are provided for scheduling the transmission of cells of a plurality of data streams in a communications network. An earliest deadline first (EDF) scheduler is provided for scheduling the transmission of cells of a plurality of data streams in a communications network to ensure that the connection or data stream with the earliest deadline is transmitted first. Each of the multiple data streams has a delay bound or deadline. Data of each data stream is enqueued to a corresponding data cell queue. A timing wheel time slot based on an identified target transmission time for each data cell queue is calculated utilizing an addition of a maximum delay value. A move forward timing mechanism includes a scan forward feature to identify a succession of virtual connection or data stream cell queues for transmission. A multiple tier cell scheduler is provided that includes at least two scheduling timing wheels. The priority of a first timing wheel is higher than the priority of a second timing wheel. The priority of the second timing wheel is higher than the priority of an optional third timing wheel. The third timing wheel includes a best effort operational mode. The re…