Network switch with packet scheduling

• US 7,274,691 B2
• Filed: 12/22/2000
• Issued: 09/25/2007
• Est. Priority Date: 12/23/1999
• Status: Expired due to Fees

• Current Assignee: Arlington Technologies, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Rogers, Steven A.
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): Scheibel, Robert C
• Application Number:
  US09/746,744
• Publication Number:
  US 20010036181A1
• Time in Patent Office: 2,468 Days
• Field of Search: 370/389, 370/395.2, 370/395.21, 370/395.4, 370/395.42, 370/395.43, 370/395.52, 370/352, 370/356
• US Class Current: 370/389
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An apparatus and method for switching data packet flows by assigning schedules to guaranteed delay and bandwidth traffic. Scheduled bandwidth is subtracted from the available bandwidth, and the remaining unscheduled bandwidth is available for standard “best-efforts” packet transmissions, or other guaranteed packet flows. Guaranteed bandwidth is assigned on a schedule basis, and packet flows are assigned schedules which are mutually acceptable to both transmitters and receivers. Flows transmit and expect to receive packets in accordance with their assigned schedules. Schedules are negotiated between packet transmitter applications and packet receiver applications. During scheduled periods, packets sent by the packet transmitter are directly and immediately forwarded to the assigned packet receiver. Other traffic destined for the receiver is placed in a delay queue, and other packets are not transmitted to the packet receiver during the assigned schedule, as long as the transmitter is still sending guaranteed packets.

Claims

1. A method for switching data packet flows with guaranteed delay and bandwidth, comprising:

receiving expected packet arrival time information at a switch, wherein said expected packet arrival time information is associated with a packet flow, and wherein said expected packet arrival time information indicates an expected packet arrival time at which at least one packet associated with said packet flow is expected to be received by said switch;

storing, within said switch, schedule information defining at least one packet flow schedule, wherein said schedule information defines scheduled reception and transmission times for at least one packet associated with said at least one packet flow, wherein the scheduted reception time indicates an expected packet arrival time at which said at least one packet associated with said at least one packet flow is expected to be received by said switch;

receiving forwarding information associated with said packet flow, wherein said forwarding information indicates how said switch should forward a packet that arrives at said expected packet arrival time, and associating said forwarding information with said expected packet arrival time;

receiving a reference packet at a reference time;

determining a schedule interval start time in response to said reference time;

determining said expected packet arrival time based on said expected packet arrival time information and said schedule interval start time;

pre-establishing a path through said switch for a predetermined period of time that includes said expected packet arrival time;

receiving a packet at said expected packet arrival time;

subjecting said packet to a layer 2 processing or a higher layer processing, said layer 2 processing or a higher layer processing including at least one of switching said packet and routing said packet; and

forwarding, via said pre-established path through said switch, said packet based on said forwarding information associated with said expected packet arrival time.

2. The method of claim 1, further comprising:

receiving packet transmission time information at said switch, wherein said packet transmission time information is associated with said packet flow, wherein said packet transmission time information indicates a packet transmission time at which said switch may transmit said packet associated with said packet flow; and

wherein said forwarding said packet includes transmitting said packet at said packet transmission time.

3. The method of claim 2, further comprising:

associating said expected packet arrival time information with a first port of said switch; and

wherein said receiving of said packet is at said first port of said switch.

4. The method of claim 3, further comprising:

associating said packet transmission time information with a second port of said switch; and

wherein said transmitting of said packet is at said second port of said switch.

5. The method of claim 4, further comprising:

wherein said packet flow is associated with a real-time application;

receiving another packet associated with a non-real-time application; and

delaying transmission of said non-real-time packet in order to perform said transmitting of said packet associated with said real-time application.

6. The method of claim 5, wherein said receiving of said packet associated with said non-real-time application occurs prior to said receiving of said packet associated with said real-time application.

7. The method of claim 1, wherein said expected packet arrival time information includes a packet flow offset value, and wherein said determining said expected packet arrival time includes adding said packet flow offset value to said schedule interval start time.

8. The method of claim 1, wherein said packet transmission time information includes a packet flow offset value, and wherein said determining said packet transmission time includes adding said packet flow offset value to said schedule interval start time.

9. The method of claim 2, further comprising:

transmitting said packet transmission time information to a second switch; and

receiving acknowledgement of said packet transmission time information, wherein said acknowledgement of said packet transmission time information includes either approval or disapproval.

26. The method of claim 1, wherein:

said pre-establishing said path through said switch comprises establishing said path from a first port of said switch to a second port of said switch, according to said forwarding information.

27. The method of claim 26, further comprising:

after the predetermined period of time, disestablishing said path through said switch.

28. The method of claim 26, further comprising:

periodically re-establishing said path, from said first port to said second port, through said switch, for said predetermined period of time; and

forwarding any received packets received at said first port, while said path is established, by transmitting said any received packets at said second port, in accordance with said forwarding information associated with said packet flow.

29. The method of claim 28, wherein:

said expected packet arrival time information further indicates a repeat time interval between packets that are associated with said packet flaw and that are expected to be received by said switch; and

said periodically re-establishing said path comprises periodically re-establishing said path according to said repeat time interval.

30. The method of claim 1, wherein:

said expected packet arrival time information further indicates a repeat time interval between packets that are associated with said packet flow and that are expected to be received by said switch; and

further comprising;

receiving subsequent packets at times corresponding to said expected packet arrival time and said repeat time interval; and

forwarding said subsequent packets based on said forwarding information associated with said expected packet arrival time.

31. The method of claim 1, wherein:

said forwarding said packets comprises forwarding said packet without referencing destination information with said packet.

10. An apparatus for switching data packet flows with guaranteed delay and bandwidth, comprising:

control logic for receiving expected packet arrival time information at a switch, wherein said expected packet arrival time information is associated with a packet flow, and wherein said expected packet arrival time information indicates an expected packet arrival time at which at least one packet associated with said packet flow is expected to be received by said switch;

control logic for storing within said switch, schedule information defining at least one packet flow schedule, wherein said schedule information defines scheduled reception and transmission times for at least one packet associated with said at least one packet flow, wherein the scheduled reception time indicates an expected packet arrival time at which said at least one packet associated with said at least one packet flow is expected to be received by said switch;

control logic for receiving forwarding information associated with said packet flow, wherein said forwarding information indicates how said switch should forward a packet that arrives at said expected packet arrival time, and associating said forwarding information with said expected packet arrival time;

control logic for—

receiving a reference packet at a reference time;

control logic for determining a schedule interval start time in response to said reference time;

control logic for determining said expected packet arrival time based on said expected packet arrival time information and said schedule interval start time;

control logic for pre-establishing a path through said switch for a predetermined period of a time that includes said expected packet arrival time;

control logic for receiving a packet at said expected packet arrival time;

control logic for subjecting said packet to a layer 2 processing or a higher layer processing, said layer 2 processing or a higher layer processing including at least one of switching said packet and routing said packet; and

control logic for forwarding, via said pre-established path through said switch, said packet based on said forwarding information associated with said expected packet arrival time.

11. The apparatus of claim 10, further comprising:

control logic for receiving packet transmission time information at said switch, wherein said packet transmission time information is associated with said packet flow, wherein said packet transmission time information indicates a packet transmission time at which said switch may transmit said packet associated with said packet flow; and

wherein said control logic for forwarding said packet includes control logic for transmitting said packet at said packet transmission time.

12. The apparatus of claim 11, further comprising:

control logic for associating said expected packet arrival time information with a first port of said switch; and

wherein said control logic for receiving of said packet is associated with said first port of said switch.

13. The apparatus of claim 12, further comprising:

control logic for associating said packet transmission time information with a second port of said switch; and

wherein said control logic for transmitting said packet is associated with said second port of said switch.

14. The apparatus of claim 13, wherein:

said packet flow is associated with a real-time application; and

further comprising;

control logic for delaying transmission of a received non-real-time packet in order to perform said transmitting of said packet associated with said real-time application.

15. The apparatus of claim 14, wherein said control logic for delaying said transmission of said received non-real-time packet is operable to delay said transmission of said received non-real-time packet in the event that said non-real-time packet is received prior to said receiving of said packet associated with said real-time application.

16. The apparatus of claim 10, wherein said expected packet arrival time information includes a packet flow offset value, and wherein said control logic for determining said expected packet arrival time includes control logic for adding said packet flow offset value to said schedule interval start time.

17. The apparatus of claim 10, wherein said packet transmission time information includes a packet flow offset value, and wherein said control logic for determining said packet transmission time includes control logic for adding said packet flow offset value to said schedule interval start time.

18. The apparatus of claim 11, further comprising:

control logic for transmitting said packet transmission time information to a second switch; and

control logic for receiving acknowledgement of said packet transmission time information, wherein said acknowledgement of said packet transmission time information includes either approval or disapproval.

19. A network of communication devices including a plurality of packet switching devices according to claim 11, and wherein a first subset of said plurality of switching devices are originators of reference packets including said expected packet arrival time information and said packet transmission time information, and a second subset of said plurality of packet switching devices are receivers of said reference packets including said expected packet arrival time information and said packet transmission time information.

20. A network of communication devices including a plurality of packet switching devices according to claim 11, and wherein a predetermined one of said plurality of switching devices operates as a centralized scheduling agent and originates reference packets including said expected packet arrival time information and said packet transmission time information.

32. The apparatus of claim 10, wherein:

said control logic for pre-establishing said path through said switch comprises a crosspoint matrix communicably coupled to said control logic for receiving said packet and to said control logic for forwarding said packet and operable to establish said path, from a first port to a second port, through said switch, according to said forwarding information.

33. A network of communication devices including a plurality of packet switching devices according to claim 11, further comprising a centralized scheduling agent that originates reference packets including said expected packet arrival time information and said packet transmission time information.

21. A schedule-based packet switch, comprising:

a master clock system, said master clock system operative to determine a beginning of a schedule interval;

schedule information defining at least one packet flow schedule, wherein said schedule information defines scheduled reception and transmission times for at least one packet associated with said at least one packet flow, wherein the scheduled reception time indicates an expected packet arrival time at which said at least one packet associated with said at least one packet flow is expected to be received by said switch;

logic for subjecting said packet to a layer 2 processing or a higher layer processing, said layer 2 processing or a higher layer processing including at least one of switching said packet and routing said packet; and

logic for receiving a reference packet at a reference time;

logic for determining a schedule interval start time in response to said reference time;

logic far determining said expected packet arrival time based on said expected packet arrival time information and said schedule interval start time;

a plurality of interface ports, each of said interface ports having transmit control logic and receive control logic, wherein each of said transmit and receive logic is responsive to said schedule information and said master clock system, wherein said transmit control logic of at least one of said plurality of interface ports is operable to determine a transmit time of a received packet associated with said at least one packet flow in response to a transmit time offset into said schedule interval defined by said packet flow schedule.

22. The schedule-based packet switch of claim 21, wherein said receive control logic of at least one of said plurality of interface ports is operable to determine an expected reception time of a packet associated with said at least one packet flow in response to a reception time offset into said schedule interval defined by said packet flow schedule.

23. The schedule-based packet switch of claim 21, wherein said master clock system is responsive to an external clock reference, wherein said external clock reference is based on a received heartbeat packet.

24. A method for schedule-based packet switching in a scheduled packet switch, comprising:

determining, by a master clock system in said scheduled packet switch, a beginning of a schedule interval;

storing, within said scheduled packet switch, schedule information defining at least one packet flow schedule, wherein said schedule information defines scheduled reception and transmission times for at least one packet associated with said at least one packet flow, wherein the scheduled reception time indicates an expected packet arrival time at which said at least one packet associated with said at least one packet flow is expected to be received by said scheduled packet switch;

determining, at a transmit control logic of an interface port of said scheduled packet switch, and responsive to said schedule information and said master clock system, a transmit time of a received packet associated with said at least one packet flow in response to a transmit time offset into said schedule interval defined by said packet flow schedule;

receiving a reference packet at a reference time;

determining a schedule interval start time in response to said reference time;

determining said expected packet arrival time based on said expected packet arrival time information and said schedule interval start time; and

subjecting said packet to a layer 2 processing or a higher layer processing, said layer 2 processing or a higher layer processing including at least one of switching said packet and routing said packet.

25. The method of claim 24, further comprising determining, at a receive control logic of an interface port of said scheduled packet switch, and responsive to said schedule information and said master clock system, an expected reception time of a packet associated with said at least one packet flow in response to a reception time offset into said schedule interval defined by said packet flow schedule.

34. A method for switching data packet flows with guaranteed delay and bandwidth, comprising:

receiving expected packet arrival time information at a switch, wherein said expected packet arrival time information is associated with a packet flow, and wherein said expected packet arrival time information indicates an expected packet arrival time at which at least one packet associated with said packet flow is expected to be received by said switch;

storing, within said switch, schedule information defining at least one packet flow schedule, wherein said schedule information defines scheduled reception and transmission times for at least one packet associated with said at least one packet flow, wherein the scheduled reception time indicates an expected packet arrival time at which said at least one packet associated with said at least one packet flow is expected to be received by said switch;

receiving forwarding information associated with said packet flow, wherein said forwarding information indicates how said switch should forward a packet that arrives at said expected packet arrival time, and associating said forwarding information with said expected packet arrival time;

receiving a reference packet at a reference time;

determining a schedule interval start time in response to said reference time;

determining said expected packet arrival time based on said expected packet arrival time information and said schedule interval start time;

pre-establishing a path through said switch for a predetermined amount of time, based on said expected packet arrival time;

receiving a packet during said predetermined amount of time;

subjecting said packet to a layer 2 processing or a higher layer processing, said layer 2 processing or a higher layer processing including at least one of switching said packet and routing said packet; and

forwarding, via said pre-established path through said switch, said packet based on said forwarding information associated with said expected packet arrival time.

35. The method of claim 34, further comprising:

receiving packet transmission line information at said switch, wherein said packet transmission time information is associated with said packet flow, wherein said packet transmission time information indicates a packet transmission time at which said switch may transmit said packet associated with said packet flow; and

wherein said forwarding said packet includes transmitting said packet at said packet transmission time.

36. The method of claim 34, wherein:

said pre-establishing said path through said switch comprises establishing said path from a first port of said switch to a second port of said switch, according to said forwarding information.

37. The method of claim 36, further comprising:

periodically re-establishing said path, from said first port to said second port, through said switch, for said predetermined period of time; and

forwarding any received packets received at said first port, while said path is established, by transmitting said any received packets at said second port, in accordance with said forwarding information associated with said packet flow.

38. The method of claim 37, wherein:

said expected packet arrival time information further indicates a repeat time interval between packets that are associated with said packet flow and that are expected to be received by said switch; and

said periodically re-establishing said path comprises periodically re-establishing said path according to said repeat time interval.

39. The method of claim 34, wherein:

said forwarding said packet comprises forwarding said packet without referencing destination information within said packet.