Network switch with packet scheduling

• US 20010036181A1
• Filed: 12/22/2000
• Published: 11/01/2001
• Est. Priority Date: 12/23/1999
• Status: Active Grant

• Current Assignee: Arlington Technologies, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Avaya Incorporated
• Inventors: Rogers, Steven A.
• Granted Patent: US 7,274,691 B2
• Time in Patent Office: Days
• 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 packet arrival time information at a switch, wherein said packet arrival time information is associated with a packet flow, and wherein said packet arrival time information indicates a packet arrival time at which said switch will receive a packet associated with a packet flow;

receiving forwarding information associated with said packet flow, said forwarding information associated with said packet flow indicating how said switch should forward received packets associated with said packet flow;

receiving said packet associated with said packet flow at said packet arrival time; and

forwarding said packet based on said packet arrival time in accordance with said forwarding information associated with said packet flow.

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 based on said packet arrival time includes transmitting said packet at said packet transmission time.

3. The method of

claim 2

, further comprising:

associating said 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

, further comprising:

receiving a reference packet at a reference time;

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

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

8. The method of

claim 7

, wherein said packet arrival time information includes a packet flow offset value, and wherein said determining said packet arrival time includes adding said packet flow offset value to said schedule interval start time.

9. The method of

claim 2

, further comprising:

receiving a reference packet at a reference time;

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

determining said packet transmission time based on said packet transmission time information and said schedule interval start time.

10. The method of

claim 9

, 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.

11. 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.

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

control logic for receiving packet arrival time information at a switch, wherein said packet arrival time information is associated with a packet flow, and wherein said packet arrival time information indicates a packet arrival time at which said switch will receive a packet associated with a packet flow;

control logic for receiving forwarding information associated with said packet flow, said forwarding information associated with said packet flow indicating how said switch should forward received packets associated with said packet flow;

control logic for receiving said packet associated with said packet flow at said packet arrival time; and

control logic for forwarding said packet based on said packet arrival time in accordance with said forwarding information associated with said packet flow.

13. The apparatus of

claim 12

, 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 based on said packet arrival time includes control logic for transmitting said packet at said packet transmission time.

14. The apparatus of

claim 13

, further comprising:

control logic for associating said 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.

15. The apparatus of

claim 14

, 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.

16. The apparatus of

claim 15

, further comprising:

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

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.

17. The apparatus of

claim 16

, 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.

18. The apparatus of

claim 12

, further comprising:

control logic for processing receiving a reference packet at a reference time;

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

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

19. The apparatus of

claim 18

, wherein said packet arrival time information includes a packet flow offset value, and wherein said control logic for determining said packet arrival time includes control logic for adding said packet flow offset value to said schedule interval start time.

20. The apparatus of

claim 13

, further comprising:

control logic for receiving a reference packet and for recording a reference time at which said reference packet was received;

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

control logic for determining said packet transmission time based on said packet transmission time information and said schedule interval start time.

21. The apparatus of

claim 20

, 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.

22. The apparatus of

claim 13

, 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.

23. A network of communication devices including a plurality of packet switching devices according to

claim 13

, and wherein a first subset of said plurality of switching devices are originators of reference packets including said 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 packet arrival time information and said packet transmission time information.

24. A network of communication devices including a plurality of packet switching devices according to

claim 13

, and wherein a predetermined one of said plurality of switching devices operates as a centralized scheduling agent and originates reference packets including said packet arrival time information and said packet transmission time information.

25. 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 said at least one packet flow; and

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 functions are responsive to said schedule information and said master clock system, wherein said transmit control logic of at least one of said plurality of interface port 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.

26. The schedule based packet switch of

claim 25

, wherein said receive control logic of at least one of said plurality of interface port is operable to determine a 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.

27. The schedule based packet switch of

claim 25

, wherein said master clock is responsive to an external clock reference, wherein said external clock reference is based on a received heartbeat packet.

29. The method of

claim 27

, 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, a 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.

30. The method of

claim 26

, further comprising:

receiving a heartbeat packet; and

determining, by said master clock system in response to said heartbeat packet, said beginning of said schedule interval.

28. 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 said at least one packet flow; and

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.