Universal edge node

• US 7,606,262 B1
• Filed: 06/06/2006
• Issued: 10/20/2009
• Est. Priority Date: 12/26/2001
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Daspit, Paul F., Edwards, Harold G., Beshai, Maged E.
• Primary Examiner(s): Pham, Chi H
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US11/447,030
• Time in Patent Office: 1,232 Days
• Field of Search: 370231-234, 370/236.1, 370/395.1, 370/395.4, 370/395.41, 370/395.42, 370/395.43, 370/395.7, 370/375, 370/386, 370/391, 370/468, 370/477
• US Class Current: 370/468
• CPC Class Codes: H04Q 3/5455 Multi-processor, parallelism, distributed systems

Abstract

A universal electronic switching node serves as an edge node in a high-capacity network with an optical core. The universal edge node may handle a variety of traffic classes and may control traffic admission, connection definition, connection routing and core node configuration. The provided capabilities significantly simplify network operation and control. The universal edge node includes input ports for receiving data streams, output ports for transmitting the data streams though the optical core, a switching fabric for communicating these data streams between input and output ports and a controller for controlling this communicating. In particular, the controller can select a route through the optical core, schedule the communication between input and output ports and adaptively allocate the bitrate of this communication.

Claims

1. A method of scheduling a transfer of data segments through a switching fabric from a plurality of input ports of said switching fabric to a plurality of output ports of said switching fabric wherein a scheduling frame having a predetermined number of time slots and an equal, predetermined duration is associated with each of said plurality of input ports, said method comprising:

dividing said duration of each said scheduling frame into a plurality of time windows by a switching fabric device;

dividing said plurality of input ports into input-port groups;

for each said scheduling frame, forming a plurality of non-intersecting scheduling domains, where each said scheduling domain associates one of said input-port groups with one of said plurality of time windows;

concurrently executing scheduling processes, one scheduling process for each of said non-intersecting scheduling domains, each said scheduling process determining a schedule that indicates, for a given scheduling domain, a timing for a transfer of data segments to selected ones of said plurality of output ports from said input ports associated with said time window in said given scheduling domain; and

at least where said executing does not use all said time windows of a given scheduling frame, repeating said forming and said executing for pairs of said input-port groups and time windows.

2. The method of claim 1 wherein, for a scheduling frame associated with a given input port, said executing scheduling process includes allocating at least one time slot to an output port to which said given input port has non-zero traffic.

3. The method of claim 2 wherein said executing said scheduling process for a given scheduling domain comprises sequentially executing said scheduling process for said input ports of said input-port group of said given scheduling domain.

4. The method of claim 1 further comprising receiving, from each of said plurality of input ports, a demand vector, where said demand vector indicates a required number of time slots per scheduling frame for each of said plurality of output ports and wherein said demand vector is structured as an aggregate-demand ring-list including a plurality of data records, each said data record including a field indicating a preceding record identifier, a field indicating a succeeding record identifier, a field indicating an output port identifier, and a field indicating a non-zero number of required time slots per scheduling frame.

5. The method of claim 1 further comprising receiving, from each of said plurality of input ports, a demand vector, where said demand vector indicates a required number of time slots per scheduling frame for each of said plurality of output ports and wherein said demand vector is structured as a flat-demand ring-list including a plurality of data records, each said data record including a field indicating a preceding record identifier, a field indicating a succeeding record identifier, and a field indicating an output port identifier.

6. The method of claim 1 further comprising limiting an execution time period for each said scheduling process.

7. The method of claim 6 wherein said limited execution time period varies with each of said repeating of said concurrently executing a scheduling process.

8. The method of claim 1 wherein said switching fabric is a space switch.

9. The method of claim 1 wherein said switching fabric is a rotator-based switch having a plurality of middle memories.

10. The method of claim 9 wherein, for each said input port, a time slot is uniquely associated with one of said plurality of middle memories.

11. The method of claim 1 further comprising using said schedule, determined for said duration of said scheduling frame, for a configuration period, where the duration of said configuration period is an integer multiple of said duration of scheduling frame.

12. A method of scheduling transfer of data segments from a plurality of input ports of a switching fabric to a plurality of output ports of said switching fabric comprising:

dividing a scheduling time frame into a plurality of time windows by a switching fabric device;

dividing said plurality of input ports into input-port groups;

forming a plurality of non-intersecting scheduling domains, where, in each scheduling domain of said plurality of scheduling domains, one of said input-port groups is associated with one of said plurality of time windows;

concurrently executing scheduling processes for at least two of said non-intersecting scheduling domains, each said scheduling process determining a schedule that indicates, for a given scheduling domain among said plurality of scheduling domains, a timing for a transfer of selected ones of said data segments to selected ones of said plurality of output ports; and

where said executing does not use all said time windows during said scheduling time frame, repeating said executing for an unused time window.

13. The method of claim 12 wherein said time windows are of equal duration.

14. The method of claim 13 further comprising dividing said scheduling time frame into a plurality of time slots of equal duration.

15. The method of claim 14 wherein said dividing said scheduling time frame into said plurality of time windows comprises forming a given time window of said plurality of time windows from selected time slots among said plurality of time slots.

16. The method of claim 15 wherein said selected time slots in said given time window are non-adjacent in said scheduling time frame.

17. The method of claim 12 wherein said executing is performed for each of said scheduling domains once during a period of said scheduling time frame.

18. The method of claim 12 wherein said executing is performed for each of said scheduling domains once during a configuration period, said configuration period being an integer multiple of a duration of said scheduling frame.

19. The method of claim 12 further comprising forming said data segments from data packets waiting at input queues associated with said plurality of input ports.

20. The method of claim 12 wherein said selected ones of said data segments are to be formed from data packets which are anticipated based on an adaptive bitrate estimate of data to be transferred from input ports in said plurality of input ports to output ports in said plurality of output ports.