Distance-sensitive scheduling of TDM-over-packet traffic in VPLS

• US 7,391,777 B2
• Filed: 11/03/2003
• Issued: 06/24/2008
• Est. Priority Date: 11/03/2003
• Status: Expired due to Fees

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Sridhar, Kamakshi, Kim, Taeho
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): WONG, XAVIER S
• Application Number:
  US10/700,023
• Publication Number:
  US 20050094645A1
• Time in Patent Office: 1,695 Days
• Field of Search: 370/395.21, 370/395.42, 370/412, 370/238, 370/413, 370/428, 370/429
• US Class Current: 370/395.21
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/502 Frame based
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04L 47/28 in relation to timing considerations
• CPC Class Codes: H04L 47/286 Time to live
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/566 Deadline varies as a function of time spent in the queue
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

A method of scheduling high-priority packets in a metro Ethernet switch is described. In one embodiment, the method comprises the steps of determining a maximum queuing delay allowed for at least two high-priority packets in an output queue in the switch; determining which one of the at least two high-priority packets has the smallest maximum queuing delay allowed; and scheduling the one of the at least two high-priority packets determined to have the smallest maximum queuing delay allowed before the remaining ones of the at least two high-priority packets.

Claims

1. A method of scheduling high-priority packets in a metro Ethernet switch, the method comprising the steps of:

determining a maximum per-hop queuing delay allowed for at least two high-priority packets in a queue in the switch, wherein the maximum per-hop queuing delay for a particular one of said high-priority packets is a respective maximum per-hop queuing delay calculated dependent upon a number of hops in a label switched path (“

LSP”

) between the switch and a designated destination of the particular one of said high-priority packets and wherein said the respective maximum per-hop queuing delay is calculated only during set-up of the LSP and dependent upon a specified maximum end-to-end delay;

determining which one of the at least two high-priority packets has a smallest node exit delay requirement, wherein a node exit delay requirement for a designated high-priority packet is the sum of the maximum per-hop queuing delay allowed for the designated high-priority packet and a time of entry at the switch for the designated high-priority packet; and

scheduling the one of the at least two high-priority packets determined to have the smallest node exit delay requirement before the remaining ones of the at least two high-priority packets.

2. The method of claim 1 wherein the step of determining which one of the at least two high-priority packets has the smallest node exit delay requirement comprises the steps of:

creating a POS table that lists, for each high-priority packet that has entered the switch, a position of the high-priority packet in a queue of the switch, a time the high-priority packet entered the queue, and an intended destination of the high-priority packet;

creating a Qmax table for storing a maximum allowed per-hop queuing delay for each of several possible intended destinations; and

using the Qmax table and the POS table to determine a node exit delay requirement for each of the high-priority packets in the queue of the switch.

3. The method of claim 2 wherein the step of creating a Qmax table comprises the steps of, for each label switched path (“

LSP”

) between the switch and one of the possible intended destinations;

determining a number of hops along the LSP; and

dividing a maximum queuing delay allowed for the LSP by the number of hops along the LSP to determine the maximum allowed per-hop queuing delay.

4. The method of claim 2 wherein the step of creating a Qmax table is performed only once during LSP setup.

5. The method of claim 2 further comprising the step of updating the POS table each time a new high-priority packet enters the queue.

6. The method of claim 1 wherein the steps of determining a maximum per-hop queuing delay allowed, determining which one of the at least two high-priority packets has the smallest node exit delay requirement, and scheduling the one of the at least two high-priority packets determined to have the smallest node exit delay requirement before the remaining ones of the at least two high-priority packets are performed each time a new high-priority packet enters the queue.

7. The method of claim 1 wherein the queue is capable of performing an n-packet look-ahead.

8. A method of scheduling high-priority packets in a metro Ethernet switch, the method comprising the steps of:

creating a first table that lists, for each high-priority packet that has entered the switch, a position of the high-priority packet in a queue of the switch, a time the high-priority packet entered the queue, and an intended destination of the high-priority packet;

creating a second table for storing a maximum allowed per-hop queuing delay for each of several possible intended destinations, wherein the maximum per-hop queuing delay for a particular one of said intended destinations is a respective maximum per-hop queuing delay calculated dependent upon a number of hops in a label switched path (“

LSP”

) between the switch and the particular one of said intended destination and wherein the respective maximum per-hop queuing delay is calculated only during set-up of the LSP and dependent upon a specified maximum end-to-end delay; and

using the first and second tables to determine a node exit delay requirement for each of the high-priority packets in the queue of the switch, wherein a node exit delay requirement for a designated high-priority packet is the sum of the maximum allowed per-hop queuing delay for the designated high-priority packet and a time of entry at the switch for the designated high-priority packet.

9. The method of claim 8 further comprising the step of:

determining a maximum per-hop queuing delay allowed for at least two high-priority packets in a queue in the switch, wherein the maximum per-hop queuing delay for a particular one of said high-priority packets is a respective maximum per-hop queuing delay calculated dependent upon a number of hops in a label switched path (“

LSP”

) between the switch and a designated destination of the particular one of said high-priority packets.

10. The method of claim 9 further comprising the step of:

determining which one of the at least two high-priority packets has smallest node exit delay requirement.

11. The method of claim 10 further comprising the step of:

scheduling the one of the at least two high-priority packets determined to have the smallest node exit delay requirement before the remaining ones of the at least two high-priority packets.

12. The method of claim 8 wherein the step of creating a second table comprises the steps of, for each label switched path (“

LSP”

) between the switch and one of the possible intended destinations;

determining a number of hops along the LSP; and

dividing a maximum queuing delay allowed for the LSP by the number of hops along the LSP to determine the maximum allowed per-hop queuing delay.

13. The method of claim 8 wherein the step of creating a second table is performed only once during LSP setup.

14. The method of claim 8 further comprising the step of updating the first table each time a new high-priority packet enters the queue.

15. The method of claim 8 wherein the queue is capable of performing an n-packet look-ahead.

16. Apparatus for scheduling high-priority packets in a metro Ethernet switch, the apparatus comprising:

means for determining a maximum per-hop queuing delay allowed for at least two high-priority packets in a queue in the switch, wherein the maximum per-hop queuing delay for a particular one of said high-priority packets is a respective maximum per-hop queuing delay calculated dependent upon a number of hops in a label switched path (“

LSP”

) between the switch and a designated destination of the particular one of said high-priority packets and wherein said the respective maximum per-hop queuing delay is calculated only during set-up of the LSP and dependent upon a specified maximum end-to-end delay;

means for determining which one of the at least two high-priority packets has smallest node exit delay requirement, wherein a node exit delay requirement for a designated high-priority packet is the sum of the maximum per-hop queuing delay allowed for the designated high-priority packet and a time of entry at the switch for the designated high-priority packet; and

means for scheduling the one of the at least two high-priority packets determined to have the smallest node exit delay requirement before the remaining ones of the at least two high-priority packets.

17. The apparatus of claim 16 wherein the means for determining which one of the at least two high-priority packets has the smallest node exit delay requirement comprises:

a POS table that lists, for each high-priority packet that has entered the switch, a position of the high-priority packet in a queue of the switch, a time the high-priority packet entered the queue, and an intended destination of the high-priority packet;

means for creating a Qmax table for storing a maximum allowed per-hop queuing delay for each of several possible intended destinations; and

means for using the Qmax table and the POS table to determine a node exit delay requirement for each of the high-priority packets in the queue of the switch.

18. The apparatus of claim 17 wherein the means for creating a Qmax table comprises, for each label switched path (“

LSP”

);

means for determining a number of hops along the LSP; and

means for dividing a maximum queuing delay allowed for the LSP by the number of hops along the LSP to determine the maximum allowed per-hop queuing delay.

19. The apparatus of claim 17 wherein the Qmax table is created during LSP setup.

20. The apparatus of claim 17 further comprising means for updating the POS table each time a new high-priority packet enters the queue.

21. The apparatus of claim 16 wherein the queue is capable of performing an n-packet look-ahead.

22. A packet switch comprising:

a queue containing a plurality of packets received at the switch; and

a scheduler for scheduling transmission of the packets in the queue, wherein when the queue contains at least two high-priority packets, the scheduler schedules the one of the at least two high-priority packets determined to have a smallest node exit delay requirement before the remaining ones of the at least two high-priority packets, wherein a node exit delay requirement for a designated high-priority packet is the sum of a maximum per-hop queuing delay allowed for the designated high-priority packet and a time of entry at the switch for the designated high-priority packet, wherein the maximum per-hop queuing delay for a particular one of said high-priority packets is a respective maximum per-hop queuing delay calculated dependent upon a number of hops in a label switched path (“

LSP”

) between the switch and a designated destination of the particular one of said high-priority packets and wherein said the respective maximum per-hop queuing delay is calculated only during set-up of the LSP and dependent upon a specified maximum end-to-end delay.

23. The packet switch of claim 22 further comprising a state machine for:

maintaining a POS table that lists, for each high-priority packet that has entered the switch, a position of the high-priority packet in a queue of the switch, a time the high-priority packet entered the queue, and an intended destination of the high-priority packet; and

maintaining a Qmax table for storing a maximum allowed per-hop queuing delay for each of several possible intended destinations.

24. The packet switch of claim 23 wherein the scheduler uses the Qmax table and the POS table to determine the node exit delay requirement for each of the high-priority packets in the queue of the switch.

25. The packet switch of claim 23 wherein the maximum allowed per-hop queuing delay for each of several possible intended destinations is determined by determining a number of hops along the LSP and dividing a maximum queuing delay allowed for the LSP by the number of hops along the LSP to determine the maximum allowed per-hop queuing delay.