Apparatus and methods for scheduling packets in a broadband data stream

• US 20020110134A1
• Filed: 12/15/2000
• Published: 08/15/2002
• Est. Priority Date: 12/15/2000
• Status: Active Grant

• Current Assignee: Tellabs Operations Incorporated (Infinera Corp.)
• Original Assignee: Tellabs San Jose, Inc. (Infinera Corp.)
• Inventors: Hsu, Kenneth C., Gracon, Glenn, Curry, David, Bowles, Murray
• Granted Patent: US 6,987,732 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 2012/5637 Leaky Buckets
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 49/203 ATM switching fabrics with multicast or broadcast capabilities
• 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

A packet scheduler includes a packet manager interface, a policer, a congestion manager, a scheduler, and a virtual output queue (VOQ) handler. The policer assigns a priority to each packet. Depending on congestion levels, the congestion manager determines whether to send a packet based on the packet'"'"'s priority assigned by the policer. The scheduler schedules packets in accordance with configured rates for virtual connections and group shapers. A scheduled packet is queued at a virtual output queue (VOQ) by the VOQ handler. In one embodiment, the VOQ handler sends signals to a packet manager (through the packet manager interface) to instruct the packet manager to transmit packets in a scheduled order.

Claims

1. A method for scheduling packets in a broadband data stream, comprising the steps of:

receiving a packet descriptor;

subtracting a header from said packet descriptor;

assigning a priority and a circuit parameter to said packet descriptor;

determining a schedule to send a packet associated with said packet descriptor based on said priority and said circuit parameter;

referencing said schedule in said packet descriptor to obtain a modified packet descriptor;

adding said header to said modified packet descriptor; and

sending said modified packet descriptor.

2. An apparatus for scheduling packets in a broadband data stream, comprising:

an interface; and

a packet scheduler, said packet scheduler including;

a policer;

a congestion manager;

a scheduler; and

a virtual output queue handler;

wherein said interface subtracts a header from a packet descriptor and passes said packet descriptor to said packet scheduler;

wherein said policer assigns a compliance identifier to said packet descriptor, said congestion manager determines whether to drop said packet descriptor based on said compliance identifier, said scheduler determines a schedule to send a packet associated with said packet descriptor and includes said schedule in said packet descriptor to obtain a modified packet descriptor, and said virtual output queue handler enforces said schedule through said interface; and

wherein said interface adds said header to said modified packet descriptor.

3. A method for policing packets in a data stream, comprising the steps of:

receiving a packet having an assigned input compliance identifier;

determining if said packet conforms to a policing rate;

if said packet conforms to said policing rate;

assigning a first compliance identifier to said packet; and

if said packet does not conform to said policing rate;

assigning a second compliance identifier to said packet;

comparing said first or said second compliance identifier to said assigned input compliance identifier; and

assigning a lower compliance identifier to said packet based on said comparing step.

4. The method of claim 3, wherein if said packet does not conform to said policing rate, instead of assigning a second compliance identifier to said packet, said packet is dropped.

5. The method of claim 3, wherein said determining step includes the steps of:

comparing an actual arrival time of said packet to a theoretical arrival time;

if said theoretical arrival time is greater than said actual arrival time;

comparing said theoretical arrival time to a sum of said arrival time and a packet limit;

wherein said packet is assigned said first compliance identifier if said theoretical arrival time is less than said sum and said packet is assigned said second compliance identifier if said theoretical arrival time is greater than or equal to said sum; and

updating said theoretical arrival time if said first compliance identifier is assigned.

6. The method of claim 5, further comprising the step of:

if said theoretical arrival time is less than or equal to said actual arrival time, setting said theoretical arrival time to equal said actual arrival time and assigning said first compliance identifier to said packet.

7. The method of claim 5, further comprising the step of calculating said theoretical arrival time based on said policing rate.

8. The method of claim 5, further comprising the step of calculating said packet limit based on a packet delay variation tolerance.

9. The method of claim 5, wherein said updating step includes the steps of:

determining an increment value; and

adding said increment value to said theoretical arrival time.

10. The method of claim 9, further comprising the step of calculating said increment value based on a basic time interval and a size of said packet.

11. The method of claim 10, further comprising the step of calculating said basic time interval based on said policing rate.

12. The method of claim 3, further comprising the steps of:

receiving a copy of said packet having a second input compliance identifier;

determining if said copy conforms to a second policing rate;

if said copy conforms to said second policing rate;

assigning said first compliance identifier to said copy; and

if said copy does not conform to said second policing rate;

assigning a third compliance identifier to said copy;

comparing said first or said third compliance identifier to said second input compliance identifier; and

assigning a lower compliance identifier between said first or third compliance identifier and said second input compliance identifier to said copy.

13. The method of claim 12, wherein if said copy does not conform to said second policing rate, instead of assigning a third compliance identifier to said copy, said copy is dropped.

14. The method of claim 12, wherein said first compliance identifier indicates greater compliance than said second compliance identifier and said second compliance identifier indicates a greater compliance than said third compliance identifier.

15. The method of claim 12, wherein said step of determining if said copy conforms to said second policing rate includes the steps of:

comparing a second actual arrival time of said copy to a second theoretical arrival time;

if said second theoretical arrival time is greater than said second actual arrival time;

comparing said second theoretical arrival time to a sum of said second arrival time and a second packet limit;

wherein said copy is assigned said first compliance identifier if said second theoretical arrival time is less than said sum and said copy is assigned said third compliance identifier if said second theoretical arrival time is greater than or equal to said sum; and

updating said second theoretical arrival time if said first compliance identifier is assigned.

16. The method of claim 15, further comprising the step of:

if said second theoretical arrival time is less than or equal to said second actual arrival time, setting said second theoretical arrival time to equal to said second actual arrival time and assigning said first compliance identifier to said copy.

17. The method of claim 15, further comprising the step of calculating said second theoretical arrival time based on said second policing rate.

18. The method of claim 15, further comprising the step of calculating said second packet limit based on said policing rate, said second policing rate, and a maximum burst size.

19. The method of claim 15, wherein said step of updating said second theoretical arrival time includes the steps of:

determining a second increment value; and

adding said second increment value to said second theoretical arrival time.

20. The method of claim 19, further comprising the step of calculating said second increment value based on a second basic time interval and a size of said packet.

21. The method of claim 20, further comprising the step of calculating said second basic time interval based on said second policing rate.

22. A computer program product for policing packets in a data stream, comprising:

logic code for receiving a packet having an assigned input compliance identifier;

logic code for determining if said packet conforms to a policing rate;

if said packet conforms to said policing rate;

logic code for assigning a first compliance identifier to said packet; and

if said packet does not conform to said policing rate;

logic code for assigning a second compliance identifier to said packet;

logic code for comparing said first or said second compliance identifier to said assigned input compliance identifier; and

logic code for assigning a lower compliance identifier to said packet based on said comparing.

23. The computer program product of claim 22, wherein if said packet does not conform to said policing rate, further comprises logic code for dropping said packet instead of assigning a second compliance identifier to said packet.

24. The computer program product of claim 22, wherein said logic code for determining includes:

logic code for comparing an actual arrival time of said packet to a theoretical arrival time;

if said theoretical arrival time is greater than said actual arrival time;

logic code for comparing said theoretical arrival time to a sum of said arrival time and a packet limit;

wherein said packet is assigned said first compliance identifier if said theoretical arrival time is less than said sum and said packet is assigned said second compliance identifier if said theoretical arrival time is greater than or equal to said sum; and

logic code for updating said theoretical arrival time if said first compliance identifier is assigned.

25. The computer program product of claim 24, further comprising:

if said theoretical arrival time is less than or equal to said actual arrival time, logic code for setting said theoretical arrival time to equal said actual arrival time and logic code for assigning said first compliance identifier to said packet.

26. The computer program product of claim 24, further comprising logic code for calculating said theoretical arrival time based on said policing rate.

27. The computer program product of claim 24, further comprising logic code for calculating said packet limit based on a packet delay variation tolerance.

28. The computer program product of claim 24, wherein said logic code for updating includes:

logic code for determining an increment value; and

logic code for adding said increment value to said theoretical arrival time.

29. The computer program product of claim 28, further comprising logic code for calculating said increment value based on a basic time interval and a size of said packet.

30. The computer program product of claim 29, further comprising logic code for calculating said basic time interval based on said policing rate.

31. The computer program product of claim 22, further comprising:

logic code for receiving a copy of said packet having a second input compliance identifier;

logic code for determining if said copy conforms to a second policing rate;

if said copy conforms to said second policing rate;

logic code for assigning said first compliance identifier to said copy; and

if said copy does not conform to said second policing rate;

logic code for assigning a third compliance identifier to said copy;

logic code for comparing said first or said third compliance identifier to said second input compliance identifier; and

logic code for assigning a lower compliance identifier between said first or third compliance identifier and said second input compliance identifier to said copy.

32. The computer program product of claim 31, wherein if said copy does not conform to said second policing rate, further comprises logic code dropping said copy instead of assigning a third compliance identifier to said copy.

33. The computer program product of claim 31, wherein said first compliance identifier indicates greater compliance than said second compliance identifier and said second compliance identifier indicates a greater compliance than said third compliance identifier.

34. The computer program product of claim 31, wherein said logic code for determining if said copy conforms to said second policing rate includes:

logic code for comparing a second actual arrival time of said copy to a second theoretical arrival time;

if said second theoretical arrival time is greater than said second actual arrival time;

logic code for comparing said second theoretical arrival time to a sum of said second arrival time and a second packet limit;

wherein said copy is assigned said first compliance identifier if said second theoretical arrival time is less than said sum and said copy is assigned said third compliance identifier if said second theoretical arrival time is greater than or equal to said sum; and

logic code for updating said second theoretical arrival time if said first compliance identifier is assigned.

35. The computer program product of claim 34, further comprising:

if said second theoretical arrival time is less than or equal to said second actual arrival time, logic code for setting said second theoretical arrival time to equal to said second actual arrival time and logic code for assigning said first compliance identifier to said copy.

36. The computer program product of claim 34, further comprising logic code for calculating said second theoretical arrival time based on said second policing rate.

37. The computer program product of claim 34, further comprising calculating said second packet limit based on said policing rate, said second policing rate, and a maximum burst size.

38. The computer program product of claim 34, wherein said logic code for updating said second theoretical arrival time includes:

logic code for determining a second increment value; and

logic code for adding said second increment value to said second theoretical arrival time.

39. The computer program product of claim 38, further comprising logic code for calculating said second increment value based on a second basic time interval and a size of said packet.

40. The computer program product of claim 39, further comprising logic code for calculating said second basic time interval based on said second policing rate.

41. A method for managing congestion of packets in a data stream, comprising the steps of:

determining a set of congestion regions by compliance levels, said compliance levels indicating a hierarchy of compliance;

receiving a packet having an assigned compliance identifier;

determining an instantaneous queue size;

comparing said instantaneous queue size to said set of congestion regions; and

passing said packet based on said comparing step and said assigned compliance identifier.

42. The method of claim 41, further comprising the steps of:

calculating a percentage in a congestion region;

generating a random number;

comparing said percentage to said random number;

dropping said packet if said percentage is greater than said random number.

43. The method of claim 41, further comprising the step of:

passing all packets when said instantaneous queue size is smaller than a lowest compliance congestion region.

44. The method of claim 43, wherein said lowest compliance congestion region is a passing region.

45. The method of claim 41, further comprising the step of:

dropping all packets when said instantaneous queue size is larger than or equal to a highest compliance congestion region.

46. The method of claim 45, wherein said highest compliance congestion region is a dropping region.

47. The method of claim 41, wherein said compliance levels are determined based on compliance per virtual circuit, per port and per priority for each packet.

48. The method of claim 41, further comprising the steps of:

receiving unused memory space information regarding a chip;

managing congestion level of said chip based on said unused memory space information;

said managing step including;

allocating a portion of said unused memory space to each traffic priority.

50. The computer program product of claim 49, further comprising:

logic code for calculating a percentage in a congestion region;

logic code for generating a random number;

logic code for comparing said percentage to said random number;

logic code for dropping said packet if said percentage is greater than said random number.

51. The computer program product of claim 49, further comprising:

logic code for passing all packets when said instantaneous queue size is smaller than a lowest compliance congestion region.

52. The computer program product of claim 51, wherein said lowest compliance congestion region is a passing region.

53. The computer program product of claim 49, further comprising:

logic code for dropping all packets when said instantaneous queue size is larger than or equal to a highest compliance congestion region.

54. The computer program product of claim 53, wherein said highest compliance congestion region is a dropping region.

55. The computer program product of claim 49, wherein said compliance levels are determined based on compliance per virtual circuit, per port and per priority for each packet.

56. The computer program product of claim 49, further comprising:

logic code for receiving unused memory space information regarding a chip;

logic code for managing congestion level of said chip based on said unused memory space information;

said logic code for managing including logic code for allocating a portion of said unused memory space to each traffic priority.

58. The method of claim 57, wherein said storing step includes the step of:

delaying said packet identifier on a connection timing wheel until a connection theoretical arrival time occurs or until a next time slot.

59. The method of claim 58, wherein said step of delaying said packet identifier on a connection timing wheel further includes the steps of:

delaying said packet identifier on a coarse connection timing wheel; and

delaying said packet identifier on a fine connection timing wheel.

60. The method of claim 57, wherein said servicing step includes the steps of:

delaying said group on a group timing wheel until a group theoretical arrival time occurs;

queuing said group into an output queue;

selecting said packet identifier from said group in said output queue;

sending said packet identifier.

61. The method of claim 60, wherein said step of delaying said group on a group timing wheel further includes the steps of:

delaying said group on a coarse group timing wheel; and

delaying said group on a fine group timing wheel.

62. The method of claim 59 or 61, further comprising the step of:

implementing an unspecified bit rate traffic class using said connection timing wheel and said group timing wheel.

49. A computer program product for managing congestion of packets in a data stream, comprising:

logic code for determining a set of congestion regions by compliance levels, said compliance levels indicating a hierarchy of compliance;

logic code for receiving a packet having an assigned compliance identifier;

logic code for determining an instantaneous queue size;

logic code for comparing said instantaneous queue size to said set of congestion regions; and

logic code for passing said packet based on said comparing and said assigned compliance identifier.

57. A method for scheduling packets in a broadband data stream, comprising the steps of:

receiving a packet identifier;

determining a connection associated with said packet identifier;

storing said packet identifier in a queue for said connection, said connection belonging to a group; and

servicing said queue based on a schedule.

63. An apparatus for scheduling packets in a broadband data stream, comprising:

a set of queues;

a set of connection timing wheels;

a set of group timing wheels;

a connection queue manager; and

a group queue manager;

wherein a received packet identifier is placed on a queue in said set of queues and said queue is first delayed on said set of connection timing wheels and then delayed on said set of group timing wheels in accordance with instructions from said connection queue manager and said group queue manager.

64. The apparatus of claim 63, wherein said set of connection timing wheels includes a coarse connection timing wheel and a fine connection timing wheel.

65. The apparatus of claim 64, wherein said queue is first delayed on said coarse connection timing wheel then on said fine connection timing wheel.

66. The apparatus of claim 63, wherein said set of group timing wheels includes a coarse group timing wheel and a fine group timing wheel.

67. The apparatus of claim 66, wherein said queue is first delayed on said coarse group timing wheel then on said fine group timing wheel.

69. The method of claim 68, further comprising the step of:

signaling a scheduler to stop sending scheduled packet identifier when said virtual output queue becomes full.

70. The method of claim 68, further comprising the steps of:

receiving a multicast source packet identifier;

generating a set of leaf packet identifiers based on said multicast source packet identifier; and

processing said set of leaf packet identifiers.

71. The method of claim 70, further comprising the steps of:

intercepting a drop signal;

parsing said drop signal; and

sending said drop signal to a FIFO if a leaf packet identifier is destined to be dropped by said drop signal.

72. The method of claim 70, wherein said generating step includes the steps of:

generating a count in a first leaf packet identifier;

said count referencing said multicast source packet identifier; and

referencing said count in other leaf packet identifiers generated for said multicast source packet identifier.

73. The method of claim 70, wherein said processing step includes the steps of:

sending said leaf packet identifiers to traffic engineering blocks, said traffic engineering blocks assigning a priority to each of said leaf packet identifiers and determining a schedule to send each of said leaf packet identifier based on said priority.

74. The method of claim 68, further comprising the steps of:

generating a monitor packet identifier based on said scheduled packet identifier; and

processing said monitor packet identifier.

75. The method of claim 74, wherein said processing step includes the steps of:

assigning a priority to said monitor packet identifier; and

determining a schedule to send said monitor packet identifier based on said priority.

68. A method for handling scheduled packets in a broadband data stream, comprising the steps of:

receiving a scheduled packet identifier;

receiving a feedback signal;

storing said scheduled packet identifier in a virtual output queue based on said feedback signal;

servicing said virtual output queue based on a schedule;

sending said scheduled packet identifier from said virtual output queue based on said servicing step.

76. A computer program product for handling scheduled packets in a broadband data stream, comprising:

logic code for receiving a scheduled packet identifier;

logic code for receiving a feedback signal;

logic code for storing said scheduled packet identifier in a virtual output queue based on said feedback signal;

logic code for servicing said virtual output queue based on a schedule;

logic code for sending said scheduled packet identifier from said virtual output queue based on said servicing.

77. The computer program product of claim 76, further comprising:

logic code for signaling a scheduler to stop sending scheduled packet identifier when said virtual output queue becomes full.

78. The computer program product of claim 76, further comprising:

logic code for receiving a multicast source packet identifier;

logic code for generating a set of leaf packet identifiers based on said multicast source packet identifier; and

logic code for processing said set of leaf packet identifiers.

79. The computer program product of claim 78, further comprising:

logic code for intercepting a drop signal;

logic code for parsing said drop signal; and

logic code for sending said drop signal to a FIFO if a leaf packet identifier is destined to be dropped by said drop signal.

80. The computer program product of claim 78, wherein said logic code for generating includes:

logic code for generating a count in a first leaf packet identifier;

said count referencing said multicast source packet identifier; and

logic code for referencing said count in other leaf packet identifiers generated for said multicast source packet identifier.

81. The computer program product of claim 78, wherein said logic code for processing includes:

logic code for sending said leaf packet identifiers to traffic engineering blocks, said traffic engineering blocks including logic code for assigning a priority to each of said leaf packet identifiers and logic code for determining a schedule to send each of said leaf packet identifier based on said priority.

82. The computer program product of claim 76, further comprising:

logic code for generating a monitor packet identifier based on said scheduled packet identifier; and

logic code for processing said monitor packet identifier.

83. The computer program product of claim 82, wherein said logic code for processing includes:

logic code for assigning a priority to said monitor packet identifier; and

logic code for determining a schedule to send said monitor packet identifier based on said priority.