Methods and apparatus for packet routing with improved traffic management and scheduling

• US 20030081624A1
• Filed: 10/24/2002
• Published: 05/01/2003
• Est. Priority Date: 02/28/2001
• Status: Abandoned Application

• Current Assignee: Gotham Networks, Inc.
• Original Assignee: Gotham Networks, Inc.
• Inventors: Aggarwal, Vijay, Boland, Wayne, Beardsley, Alan, Flanders, John, McKinley, Brittain
• Application Number:
  US10/281,340
• Publication Number:
  US 20030081624A1
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5658 using the AAL5
• CPC Class Codes: H04L 2012/5665 Interaction of ATM with other protocols
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3027 Output queuing
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/505 Corrective measures
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9036 Common buffer combined with individual queues
• CPC Class Codes: H04Q 11/0478 : Provisions for broadband connections

Abstract

The present invention provides systems for improved quality of service and traffic management in network routers and other devices. This is achieved, according to one aspect of the invention, by coupling a plurality of queue processors to a plurality of input interfaces that receive data from one or more respective network connections. Each queue processor, in coordination with an associated scheduler that schedules dequeing of data from one or more queues, maintains the quality of service levels with respect to throughput, and delivers the data for a particular output context based on priority to a respective output interface. The output interface is coupled to the plurality of queue processors and transfers the data to one or more respective network connections. In addition, a plurality of output interfaces can be coupled to respective pluralities of queue processors for transferring data therefrom to one or more destination network connections. Packets, cell, datagrams and so forth passing through the router are disassembled and marked with one or more priority levels. Prior to exiting the router they re reassembled (based on those priorities, inter alia) into their constituent forms for continued routing on the network.

Claims

1. A network device, comprising:

a plurality of input interfaces, each receiving data from one or more respective network connections,

an output interface for transmitting data to one or more respective network connections, each of which is associated with a plurality of network contexts.

a plurality of queue processors, each coupled to a respective input interface and to the output interface, each queue processor transferring selected data received from the respective input interface to the output interface,

the plurality of queue processors so transferring the data as to maintain quality of service levels with respect to throughput of data from the plurality of input interfaces to the output interface.

2. The network device of claim 1, wherein the queue processors perform any one of receiving data, queuing data, dequeing data, discarding data, and maintaining data statistics.

16. The network device of claim 1, wherein a queue is selected for dequeing by a scheduler that is coupled to and interfaces with one or more queue processors to identify a queue processor requiring service and a particular priority queue associated with that queue processor that corresponds to a network context.

17. The network device of claim 16, wherein the scheduler polls each queue processor to determine their respective status in relation to a corresponding network context.

18. The network device of claim 17, wherein the queue processors that have data for a corresponding network context, respond to the scheduler by indicating the priority of the data and whether any given queue has not been serviced within a certain time threshold.

19. The network device of claim 16, wherein the scheduler schedules dequeing of data by selecting a specific queue processor and corresponding priority queue to dequeue.

20. The network device of claim 19, wherein the dequeing of data is performed according to the priority of the data in a particular queue.

21. The network device of claim 20, wherein the scheduler selects a specific queue processor and corresponding priority queue for dequeing by evaluating which queues have priority to send and which queues have not been serviced within a certain time threshold.

22. The network device of claim 21, wherein the queues that have not been serviced within a certain time threshold are starved queues.

3. The network device of 1, wherein each queue processor comprises a plurality of queues, each storing data for a selected network context.

4. The network device of claim 3, wherein the queue processors dequeue data based on parameters defined as a function of network context.

5. The network device of claim 3, further comprising a scheduler coupled to the queue processors that schedules dequeing of data from their respective queues for transfer to the output interface.

6. The network device of claim 5, wherein the scheduler polls each queue processor to determine its respective status in relation to the queuing of data for selected network contexts.

7. A network device, comprising:

a plurality of input interfaces, each receiving data from one or more respective network connections,

an output interface for transmitting data to one or more respective network connections, each of which is associated with a plurality of network contexts.

a plurality of queue processors, each coupled to a respective input interface and to the output interface, each queue processor transferring selected data received from the respective input interface to the output interface,

a scheduling table having a plurality of entries that define an order for potential transfer of data to the output interface,

the plurality of queue processors transferring the data as a function of network contexts identified in the scheduling table.

8. The network device of claim 7, wherein

each queue processor comprises a plurality of queues, each storing data for a selected network context, the device further comprising

a scheduler coupled to the queue processors and to the scheduling table, the scheduler polling the queue processors to determine their respective statuses in relation to data queued for selected network contexts identified in the scheduling table.

9. The network device of claim 8, wherein the scheduler schedules transfer of data from the queues to the output interface as a function of network contexts identified in the scheduling table and as a function of the respective statuses of the queue processors in relation to data queued for selected network contexts.

10. The network device of claim 9, wherein dequeing of data is based on a response received from the queue processors regarding their status.

11. In a network device the improvement comprising,

a plurality of queue processors, each coupled to a respective input interface and associated with one or more queues that store data, each queue processor:

receiving data from the respective interface, storing the data into a queue associated with that queue processor, and

dequeing the data per context by priority from a selected queue, and transmitting the data to an output interface that is coupled to the plurality of queue processors for transferring data therefrom to one or more network connections.

12. The network device of claim 11, wherein the queue processors additionally perform any one of discarding the data, and maintaining a list of statistics and parameters in memory.

13. The network device of claim 11, wherein the data is stored in linked-list queue structures.

14. The network device of claim 13, wherein each queue processor is associated with a plurality of queues storing data, each queue having a different priority level, and each respective plurality corresponding to a network connection that data is transferred to from the queues.

15. The network device of claim 14, wherein the priority level has any one of four values.

23. In a network device, the improvement comprising,

a plurality of queues that store data,

one or more queue processors associated with a plurality of queues,

a scheduler coupled to the queue processors that schedules dequeing of data from one or more queues based on priority.

24. The network device of claim 23, wherein a queue is selected for dequeing by a scheduler that is coupled to and interfaces with one or more queue processors to identify, a queue processor requiring service and a particular priority queue associated with that queue processor that corresponds to a network context.

25. The network device of claim 24, wherein the scheduler polls each queue processor to determine their respective status in relation to a corresponding network context.

26. The network device of claim 25, wherein the queue processors that have data for a corresponding network context, respond to the scheduler by indicating the priority of the data, and whether any given queue has not been serviced within a certain time threshold.

27. In a network device, the improvement comprising,

a plurality of queues that store data being transferred between one or more input interfaces of the network device to one or more output interface of the network device,

a scheduler that schedules dequeing of data from the queues for transfer to the one or more output interfaces, the scheduler normally scheduling dequeing to proceed in a predetermined order,

a starve indicator associated with each of one or more queues, the starve indicator representing whether the associated queue has been dequeued within a certain time threshold,

the scheduler responding to the starved indicator by scheduling dequeing of the associated queues out of sequence.

28. The system of claim 27, wherein the scheduler schedules a queue associated with the starve indicator for dequeing before a queue that is not associated with the starve indicator.

29. The system of claim 28, wherein

the starve indicator has an initial numerical value, and

wherein a queue processor modifies that value each time the scheduler does not select the queue associated with that indicator for dequeing.

30. The system of claim 29, wherein

the starve indicator has an initial positive numerical value, and

wherein a queue processor decrements that value each time the scheduler does not select the queue associated with that indicator for dequeing.

31. The system of claim 30, wherein the queue processor increments the starve indicator into a positive numeric range when the associated queue is scheduled for dequeing.

32. In a network device the improvement comprising,

a plurality of queues that store data,

a scheduler that schedules dequeing of data from one or more queues,

an aggregation mask associated with one or more queues, the aggregation mask indicating that dequeing of data from queues is only permitted for queues that have not been dequeued within a certain time threshold,

the scheduler responding to the aggregation mask by scheduling dequeing of only associated queues.

33. The system of claim 32, comprising a starve indicator associated with each of one or more queues that have not been dequeued within a certain time threshold.

34. The network device of claim 33, the starve indicator has an initial numerical value, and wherein logic modifies that value each time the associated queue is polled but not selected for dequeuing.

35. The network device of claim 34, wherein the logic resets the value of the starve indicator each time the associate queue is dequeued.

36. In a network device the improvement comprising,

a plurality of queues that store data being transferred between one or more input interfaces of the network device to one or more output interface of the network device,

one or more queue processors associated with a plurality of queues, each queue processor selectively dequeing data from one or more associated queues and selectively generating a status signal indicating the status of the associated queues,

a scheduler that polls the queue processors for the status of their associated queues and that signals a selected queue processor to dequeue data from an associated queue,

a master indicator associated with a selected queue processor,

the selected queue processor generating a status signal on behalf of one or more other queue processors in response to polling by the scheduler,

the scheduler signaling a queue processor to dequeue data based on a response of the selected queue processor.

37. A network device, comprising:

a plurality of input interfaces, each receiving data from one or more respective network connections,

an output interface for transmitting data to one or more respective network connections.

a plurality of queue processors, each coupled to a respective input interface and to the output interface, each queue processor transferring selected data received from the respective input interface to the output interface,

the plurality of queue processors so transferring the data as to maintain quality of service levels with respect to throughput of data from the plurality of input interfaces to the output interface,

a scheduler coupled to the queue processors that schedules dequeing of data from their respective queues for transfer to the output interface,

the scheduler signaling a queue processor for dequeing of data based on at least one of a priority of that data and a time period since data was last dequeued from a respective queue associated with a particular queue processor.

38. The network device of claim 37, further comprising

a scheduling table having a plurality of entries, wherein each entry storing at least one of

a context number identifying a particular output network connection to which data is to be transferred in sequence,

an aggregation mask associated with one or more context numbers and indicating that dequeing is only queues that have not been serviced within a certain time threshold,

master indicator indicates that signaling to the scheduler from the queue processors is to be taken from one queue processor only, which serves as a collecting point for at least certain responses of all the queue processors for a given context number,

the scheduler signaling a queue processor for dequeing of data by context number based on the aggregation mask value and master indicator value.

39. The network device of claim 38, wherein the scheduling table lists context numbers in an order and frequency that insures quality of service for each destination network.

40. The network device of claim 38, wherein the scheduler selects a context number from the scheduling table and polls one or more queue processors to determine if the queue processors are ready to transfer data for that context number, to the corresponding network connections.

41. The network device of claim 40, wherein the scheduler selects an entry from the scheduling table at predetermined intervals to determine a context number to be serviced

42. The network device of claim 40, wherein the queue processors that have data for a corresponding context number, respond to the scheduler by signaling the priority of the data for that context number, and whether any given queue has not been serviced in a predetermined period.

43. The network device of claim 42, wherein the priority level can be any one of four possible levels.

44. The network device of claim 43, wherein the indicator showing priority level is a ready state.

46. A network device, comprising:

an input section receiving any of cells, frames, datagrams, or other packets (collectively, “

packets”

) from one or more respective network connections, and fragmenting at least selected received packets into one or more respective units,

an output section transmitting packets to one or more respective network connections, each of which is associated with a plurality of network contexts,

a routing mechanism, coupled to the input section and to the output section, the routing mechanism transferring units from the input section to the output section,

the output section including a reassembly unit that reassembles into respective packets a plurality of intermingled units received by the output section from the routing mechanism, the reassembly unit reassembling the units on the basis of at least the context associated with the network connection to which the respective packets are directed.

45. The network device of claim 51, wherein the scheduler selects queues that have not been serviced for the predetermined period before servicing all other queues regardless of priority.

47. The network device of claim 46, wherein the input section assigns an ingress priority to each received packet, and transfers the units to the routing mechanism intermingled, if at all, on at least the basis of the ingress priority.

48. The network device according to claim 47, wherein the input section utilizes the ingress priority to associate each corresponding packet with an identifier that is utilized to determine one or more routing path parameters for each unit, including an egress priority that pertains to a priority level associated with a queue in the routing mechanism that the unit is destined for.

49. The network device according to claim 47, wherein the reassembly unit reassembles the intermingled units into their respective packets based on the context and priority of the respective units.

50. The network device of claim 48, wherein the routing mechanism transfers units to the output section intermingled on at least the basis of context, slot number, ingress priority, and egress priority.

51. The network device according to claim 50, wherein the reassembly unit reassembles the intermingled units into their respective packets based on the context, slot number, ingress priority, and egress priority of the respective units.

52. The network device according to claim 50, wherein the output section checks the received units for errors and timeouts, reassembles the intermingled units into their respective packets, discards packets having errors, and forwarding the packets to their respective destination network connections based on priority.

53. In a network router, the improvement comprising:

one or more output interfaces receiving intermingled portions of different respective packets,

the one or more output interfaces including a reassembly unit that reassembles the portions into their respective packets in accord with at least the context associated with the network connection to which the respective packets are directed.

54. The network router of claim 53, wherein the one or more output interfaces include a transfers packets received from the reassembly unit to corresponding network connections based on egress priority.

55. The network router of claim 53, wherein the reassembly unit reassembles the units based on all or any one of a context, priority, and slot number.

56. The network router of claim 55, wherein the priority comprises at least one ingress priority, and at least one egress priority.

57. A network device, comprising:

one or more input interfaces, each receiving any of cells, frames, datagrams, or other packets (collectively, “

packets”

) from one or more respective network connections, and fragmenting at least selected received packets into one or more respective units,

one or more routing mechanisms, coupled to the one or more input interfaces and to one or more output interfaces, that transfer units from the one or more input interfaces to the one or more output interfaces,

the one or more output interfaces transmitting packets to one or more respective network connections, each of which is associated with a plurality of network contexts,

the one or more output interfaces receiving intermingled units of different respective packets and reassembling those units into their respective packets in accord with at least the context associated with the network connection to which the respective packets are directed,

the input interface including an aggregation module that (i) associates each received packet with an ingress priority and identifier and that (ii) fragments each packet into one or more respective fragments, and (iii) forwards each fragment to a standardizer.

58. The network device of claim 57, wherein the standardizer module utilizes the identifier associated with each fragment to determine routing thereof, reassembles the fragments into packets, segments the packets into one or more units for transfer to the one or more routing mechanisms.

59. The network device of claim 58, wherein the standardizer module associates each unit with at least one of a context, output slot number, and egress priority.

60. The network device of claim 57, wherein the one or more routing mechanisms receive intermingled units, each having a respective ingress priority and egress priority, store the units into one or more queues in accord with egress priority, and transmit the units to the one or more output interfaces in accord with the egress priority level.

61. The network device of claim 60, wherein the reassembly unit reassembles the units into their respective packets in accord with (i) a context associated with the network connection to which the respective packets are directed, (ii) an ingress priority and (iii) an egress priority.

62. A network device, comprising:

an input interface that receives any of cells, frames, datagrams, or other packets (collectively, “

packets”

) from one or more respective network connections and that fragments at least selected received packets into one or more respective units,

a routing mechanism, coupled to the input interface and to an output interface, that transfers the units from the input interface to the output interface,

the output interface receiving units of different respective packets that are intermingled with one another and reassembles the units into their respective packets in accord with at least the context associated with the network connection to which the packets are directed,

wherein the routing mechanism includes a plurality of queues, each storing the received units for a selected network context, the queues being associated with one or more digital data processors that transfer units received from the respective input interface to the output interface based on a priority scheme.

63. The network device of claim 62, wherein the digital data processors dequeue units as a function of priority and context.

64. The network device of claim 62, wherein the routing mechanism stores the intermingled units each having a respective ingress and egress priority level into one or more queues that correspond to an egress priority level.

65. The network device of claim 64, wherein at least the egress priority level has any one of four values.

66. The network device of claim 62, wherein the reassembly unit reassembles the units into their respective packets in accord with at least the context associated with the network connection to which those units are directed, and with one or more priorities associated with the units.

67. The network device of claim 66, wherein the priorities comprise at least one ingress priority that pertains to the priority level associated routing of the unit through the input interface and at least one egress priority that pertains to the priority level associated with dequeuing of the unit within routing mechanism.

68. The network device of claim 66, wherein the reassembly unit reassembles the units into their respective packets by all or any combination of context, priority, and slot number.

69. The network device of claim 62, wherein the reassembly unit reassembles the units into one or more respective packets based on slot number, ingress priority, egress priority and context.