Packet queueing within ring networks

In general, techniques are described for packet queuing within ring networks. In accordance with the techniques, a network device of a ring network comprises a memory having a different queue for each order-dependent pair of the network devices. Each pair represents a different order-dependent combination of the network devices that includes an ingress network device that provides an ingress to the ring network and an egress network device that provides an egress from the ring network. The network device further comprises an interface for receiving a packet from a neighboring one of the plurality of network devices and a control unit that, in response to receiving the packet, stores the packet to one of the queues based on which network devices is the ingress and which network device is the egress for the packet. The control unit forwards the stored packet via the ring network according to a scheduling algorithm.

TECHNICAL FIELD

The invention relates to computer networks and, more particularly, to transmitting packets within computer networks.

BACKGROUND

A computer network is a collection of interconnected computing devices that can exchange data and share resources. Often, in highly populated areas, the computer network includes an optical fiber backbone to facilitate the transfer of large amounts of data between the computing devices. Optical fiber backbones are preferred because data can be exchanged over the optical fiber at higher speeds with reduced attenuation when compared to conventional wire or cable links. In some configurations, an optical fiber backbone may be laid in the shape of a ring because a ring offers generous geographical coverage and reasonable resiliency. When shaped in a ring, the optical fiber network is referred to as a “ring network.”

Certain network devices, referred to as “switches,” provide access to the ring network. Computing devices couple to the switches to gain access to the ring network and thereby interconnect with other computing devices coupled to the fiber ring network. One of the switches may provide access to a public network, such as the Internet, or another private network, and this device is typically referred to as a “hub.” Via the hub, the computing devices may utilize the ring network to access the public or adjacent network.

While providing high transfer speeds, generous geographical coverage, and reasonable resilience, fiber ring networks often fail to treat data fairly as the data traverses around the ring, especially when the ring network comprises a packet-based ring that conveys information via packets instead of conventional multiplexed signals. In a packet-based ring network, each switch typically includes a single queue to store packets destined to traverse the ring. At a given switch, the queue, therefore, stores both packets originating from computing devices directly coupled to the switch as well as transit packets already traversing the ring without taking into consideration the position of each switch around the ring. Transit packets destined for a given hub but injected into the ring by switches distant from the hub are successively queued by each intermediary switch on the way to the destination hub, which may result in significant delays. As a result, those switches closer to the hub receive preferential access to the hub because packets injected by these switches experience fewer delays as the packet traverse fewer intermediary switches on the way to the hub. The successive delays may result in violation of agreed upon quality of service for end users of the ring.

Certain techniques, such as those employed by resilient packet rings (RPR), have been proposed as an attempt to correct this preferential treatment. In RPR, each switch includes a first queue to store packets entering the ring network at that switch and a second queue to store transit packets already present on or traversing the ring. The additional queue enables switches to execute more complicated packet scheduling algorithms to account for the preferential treatment to those packets entering the ring. Those packets already traversing the ring, however, still receive unfair treatment because, again, the switches do not take into consideration the position of each switch around the ring. As a result, delays occur even when implementing these proposed techniques, which, as above, often lead to violations of quality of service agreements with the end user.

SUMMARY

In general, techniques are described for fair packet queuing by network devices (e.g., L2 switches, L3 routers or combinations thereof) that forward packets within a packet-based ring network. As described herein, each network device maintains a queue for each possible order-dependent pair of the network devices within the ring network from which the network device may receive packets for forwarding on the ring network. Each network device may maintain a total of approximately N2queues, where N is the number of network devices residing within the ring network so as to form the ring topology. Thus, assuming no queues are separately allocated for multicast traffic, in a ring network comprising N network devices along the ring, each of the network devices maintains a set of queues that includes N×(N−1)≈N2distinct queues for forwarding traffic along the network ring. That is, each of the N network devices (including that same network device) may inject traffic to egress the ring at any of the other N−1 network devices, and a separate queue is maintained to store corresponding packets.

More specifically, a single order-dependent pair of queues for a ring network of N network devices requires two queues. For example, a node Nxof the ring network uses a first queue to store packets that were injected on the ring by a network device N1and are destined to leave the ring at a network device N2and another queue of the order-dependent pair of queues to store traffic entering the ring network from N2and exiting the ring network at N1(queue N2, N1). Thus, each queue is “order-dependent” in that a separate queue exists for each variation of the order of the pair of referenced devices, e.g., N1and N2, along the ring network. As described herein, each network device maintains order-dependent pairs of queues for each combination of network devices along the ring from which or to which the network device may receive or send packets. In this way, each network device of a ring network having N nodes may maintain on the order of N2queues for forwarding traffic along the ring, including queuing for traffic to ingress and egress the ring at that network device.

The preceding paragraph described queuing for “unicast” traffic that enters the ring at one device and egresses at one other device. In addition, network device may provide queues for multicast traffic that enters the ring at one device but egresses at several devices (perhaps all other devices, such as in broadcasting) on the ring. Thus, in addition to the N*(N−1) queues for unicast traffic, one node or network device may include another N queues for multicast traffic that enters the ring at each of N devices on the ring.

The techniques described herein may be applied so as to take into account quality of service (QoS) classes that define classes of traffic that require certain treatment with regard to resources within a network. To account for quality of service (QoS) classes, each network device along the ring may, instead of including a single queue for each order-dependent pair of network devices within the ring, include a separate queue for each QoS class for each order-dependent pair of network devices. As a result, each network device along the ring network may maintain a total of N2×M queues for forwarding traffic along the ring, where M is the number of QoS classes and N represents the number of network devices along the ring. Because a separate queue exists for each order-dependent pair (and separately for multicast traffic), the network devices (e.g., routers) may employ packet scheduling algorithms that enable fair treatment of downstream packets injected into the ring by switches remote from that particular network device. By further including a queue for each QoS class, the switches may further ensure that the best possible treatment be given to packets of QoS classes that promise high speeds/bandwidth, thereby reducing delays that may violate QoS agreements.

In an example embodiment, a network device of a plurality of network devices that form the ring network includes a forwarding component having one or more memories (e.g., in the form of addressable memory or dedicated, high-speed buffers) to store the plurality of packet queues. As described above, each of the queues may be used to store packets for a different order-dependent pair of the plurality of network devices. Alternatively, each of the queues may be used to store packets for different QoS classes for the different order-dependent pairs. Each pair of network devices can be logically defined as an entry network device at which a packet enters the ring network and an exit network device at which the packet exits the ring network. In some embodiments, queues for which the entry network device and the exit network device of the pair may be the same network device along the network ring, and the queue for this pair may be designated to store multicast packets forwarded by the entry network device, thereby facilitating the fair queuing of these multicast packets.

The network device further includes a plurality of interface cards for receiving packets originating from a neighboring network device along the ring as well as local computing devices that send or receive packets to or from the network ring. In general, each of the packets includes a source address and a destination address, and the destination address may be a unicast address or a multicast address. The forwarding component of the network device also includes a control unit that stores each of the packets to one of the plurality of queues based on the ingress network device that injected the packet in the ring and the egress network device that will remove the packet from the ring. In one example, the forwarding component is a layer 3 (L3) component that utilizes source and destination addresses (e.g., IP addresses) included within a header of each of the packets to make queuing decisions. For example, the network device may be a router that, based on the source and destination address, determines that the packet was injected into the ring from a network device N5and is will egress the ring at network device N7. As a result, the control unit stores the packet to a corresponding queue dedicated to storing packets for this ordered-pair of devices (e.g., queue N5, N7). Similarly, for multicast traffic, the network device may determine that the packet entered the ring at device Ng and thus store it in multicast queue Ng. The control unit may make similar decisions for other packets traversing the ring network so as to store the packets in the appropriate queues. Other information may be used, such as MPLS tags or other identifiers, including a tag or identifier added by the ingress network device that injected the packet into the ring. In any event, once stored, the control unit of the network device applies a scheduling algorithm to forward via the ring network the packets stored within the queues such that each of the queues receives an appropriate allocation of available bandwidth at that network device. As one example, the control unit of the network device may apply the scheduling algorithm to traverse the queues and schedule for forwarding first those packets stored to queues associated with network devices along the network ring that are distant from the network device prior to scheduling those packets stored to queues associated with network devices proximate to the hub. In addition, the scheduling algorithm takes into account QoS classes for the traffic.

The techniques described herein may provide one or more advantages. As one example, the techniques may provide fine-grain control of scheduling traffic for forwarding on the ring network. As another example, the techniques may allow the network devices along the ring network to inform each other as to the capacity of each of the distinct queues within each of the network devices such that the network devices may adjust packet scheduling and forwarding to account for near-capacity queues by refraining from transmitting packets destined for those near-capacity queues. This aspect of the fair packet queuing techniques enables network devices not only to adjust forwarding to prevent packets from being dropped but also may replace ‘hello’ messages, “keep alives” or other control plane messages used to determine status of the network devices along the ring. This may be especially useful when these conventional control messages otherwise utilized within the ring are sent at frequent intervals, e.g., on the order of milliseconds.

In one embodiment, a method comprises determining a number of packet forwarding network devices that provide ingress to or egress from to a packet-based, ring network, and within a first one of the network devices, allocating a queue for each order-dependent pair of the network devices, wherein each of the pairs represents a different order-dependent combination of the network devices that includes one of the network devices that provides an ingress for packets to the ring network and one of the network devices that provides an egress from the ring network for the packets. The method further comprises receiving, with the first one of the network devices, a packet forwarded by a neighboring one of the other plurality of network devices along the ring network and selecting one of the order-dependent pairs of the network devices based on the one of the network devices that provided the ingress for the packet to the ring network and the one of the network devices that will provide the egress for the packet from the ring network. The method also comprises selecting one of the plurality of queues within the first one of the network devices based on the selected order-dependent pair of network devices, storing the packet to the selected queue within the first one of the network devices, and forwarding the packet via the ring network.

In another embodiment, a network device of a plurality of network devices that form a ring network, the network device comprises a memory having a different queue for each order-dependent pair of the network devices, wherein each of the pairs represents a different order-dependent combination of the network devices that includes one of the network devices that provides an ingress for packets to the ring network and one of the network devices that provides an egress from the ring network for the packets, and an interface for receiving a packet from a neighboring one of the plurality of network devices. The network device further comprises a control unit that, in response to receiving the packet, stores the packet to one of the queues based on the one of the network devices that provided the ingress for the packet to the ring network and the one of the network devices that will provide the egress for the packet from the ring network, the control unit forwarding the stored packet via the ring network according to a scheduling algorithm.

In another embodiment, a system that forms a ring network, the system comprising a plurality of network devices. Each of the network devices comprises a memory having a different queue for each order-dependent pair of the network devices, wherein each of the pairs represents a different order-dependent combination of the network devices that includes one of the network devices that provides an ingress for packets to the ring network and one of the network devices that provides an egress from the ring network for the packets and a further set of queues for multicast traffic, and an interface for receiving a packet from a neighboring one of the plurality of network devices. Each of the network devices further comprises a control unit that, in response to receiving the packet, stores the packet to one of the queues based on the one of the network devices that provided the ingress for the packet to the ring network and the one of the network devices that will provide the egress for the packet from the ring network, the control unit forwarding the stored packet via the ring network according to a scheduling algorithm.

In another embodiment, the invention is directed to a computer-readable medium containing instructions. The instructions cause a programmable processor to determine a number of packet forwarding network devices that provide ingress to or egress from to a packet-based, ring network, and within a first one of the network devices, allocate a queue for each order-dependent pair of the network devices, wherein each of the pairs represents a different order-dependent combination of the network devices that includes one of the network devices that provides an ingress for packets to the ring network and one of the network devices that provides an egress from the ring network for the packets. The instructions further cause the processor to receive, with the first one of the network devices, a packet forwarded by a neighboring one of the other plurality of network devices along the ring network and select one of the order-dependent pairs of the network devices based on the one of the network devices that provided the ingress for the packet to the ring network and the one of the network devices that will provide the egress for the packet from the ring network. The instructions also cause the processor to select one of the plurality of queues within the first one of the network devices based on the selected order-dependent pair of network devices, store the packet to the selected queue within the first one of the network devices, and forward the packet via the ring network.

In another embodiment, a method comprising determining a number of packet forwarding network devices that provide ingress to or egress from to a packet-based, ring network and within a first one of the network devices, allocating a queue for each order-dependent pair of the network devices, wherein each of the pairs represents a different order-dependent combination of the network devices that includes one of the network devices that provides an ingress for packets to the ring network and one of the network devices that provides an egress from the ring network for the packets.

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating an example ring network10in which packet-forwarding network devices12A-12N operate in accordance with the fair packet queuing techniques described herein. In this example, network devices12A-12N (“network devices12”) are interconnected via optical fiber links14to form packet-based, optical fiber ring network10. Network devices12may be routers, hubs, switches, and any other type of network device capable of performing the fair packet queuing techniques described herein. While described herein with respect to optical fiber links14, the links may comprise any form of link, including radio frequency cable links, Ethernet cable links, or any other form of wired or even wireless communication mediums.

For example, network devices12may be layer three (L3) enabled devices, such as routers. Alternatively, network devices12may comprise layer two (L2), or data link layer, network devices, such as intelligent switches, hubs, or other L2 network devices. In some implementations, network devices12may implement both L2 forwarding and L3 routing functions. For purposes of illustration, network devices12may be referred to as switches or hubs herein.

As shown inFIG. 1, end-user devices16A-16M (“end-user devices16”) couple to respective network devices12B-12N. For ease of illustration, only one end-user device16is shown coupling to each of respective network devices16B-16N. However, more than one device16(and typically a corresponding network of devices16) may couple to each of network devices12B-12N and the principles of the invention should not be strictly limited to the illustrated example. End-user devices16may each comprise one of a laptop computer, a desktop computer, a personal digital assistant (PDA), a workstation, a cellular phone, or any other device capable of accessing ring network10via common network protocols, e.g., TCP/IP.

Often in ring networks, one or more of network devices12may be viewed as a hub where two or more separate networks interconnect. In the example ofFIG. 1, network device12A is a hub in that network device12A interconnects ring network10with a public network18. Public network18may comprise a network available for access by the public, such as the Internet. Network device12A may forward network traffic from public network18to network devices12within ring network10, i.e., provide an ingress for the network traffic to ring network12. Although shown as coupling to public network18, network device12A may interconnect with any type of network, both private and public, as well as with other ring networks. Moreover, although not shown inFIG. 1, multiple hubs may reside within ring network10.

Network devices12are interspersed around ring network10so as to provide end-user devices16located in disparate geographical locations with access to high-speed ring network10, and thereby to public network18. Moreover, in this example, each of network devices12provides an ingress to ring network10and an egress from ring network10. By forming a ring, ring network10offers resiliency because data may flow in two directions around the ring. That is, should one of links14fail or otherwise stop transmitting packets, network devices12adjacent to the failed link14may each forward packets away from the failed link14around ring network10to reach the desired destination. For example, if link14between network devices12A and12B fails, network device12A can forward packets destined for network device12B counter-clockwise around ring network10to reach network device12B. Similarly, network device12B can forward packets destined for network device12A clockwise around ring network10to reach network device12A. Thus, ring network10offers increased resiliency by providing access to each of network devices12in two directions, i.e., clockwise and counter-clockwise. In contrast, conventional meshed networks may be required to interconnect a pair of switches via two fiber links14in order to provide the same resiliency, which increases costs when compared to ring networks.

In order to detect a failed link14, network devices12may transmit control packets, often referred to as “hello messages,” in one direction around the ring, and may transmit data packets in the opposite direction around the ring. As shown inFIG. 1, network devices12forward control packets around ring network10in a clockwise direction and data packets in a counter-clockwise direction. This forwarding structure is merely representative of one embodiment, and in alternative embodiments, network devices12may perform more complex forwarding to reduce the number of intermediary network devices12between, for example, network device12E and network device12A. For example, assuming only six network devices12are interspersed around ring network10, network device12E may forward data packets clockwise to reach network device12A instead of counter-clockwise because clockwise forwarding requires the traversal of only one intermediary network devices12N, while counter-clockwise requires the traversal of three intermediary network devices12D,12C, and12B. Again, the embodiment depicted inFIG. 1is merely for purposes of illustration and the principles of the invention should not be strictly limited to the simple forwarding structure illustrated therein.

Network devices12may periodically forward control messages to adjacent network devices along the ring and maintain a maximum time interval (e.g., threshold) by which to determine whether one of links14has failed. For example, network device12B may send a control message to network device12A. If network device12B does not receive a response control message from network device12A within the maximum time interval, network device12B determines that link14coupling network device12A to network device12B has failed. Upon determining a failed link14, network device12B may send a control message, or failed link message, clockwise around ring network10to alert each of network devices12that the link14between network device12A and12B has failed. Network devices12may receive the control message and modify the forwarding of data packets around ring network10to account for failed link14. For example, each of network devices12may update stored forwarding information to reflect the change in topology of network10. In this manner, network devices12may detect a failed link14and modify the manner in which packets are forwarded within ring network10to account for the failed link14.

In the example ofFIG. 1, each of network devices12maintains a plurality of queues20. Each queue within the plurality of queues20stores packets associated with a different order-dependent pair of the plurality of network devices12. Thus, each of N network devices12along the network device maintains separate queues dedicated to queuing traffic for each possible order-dependent pair for the other N−1 devices, where an order-dependent pair of network devices represents the network device that injected the queued packets into the ring and the network device that will provide the egress for the queued packets. Additionally, each of the N network devices12may maintain N queues dedicated to queuing multicast traffic ingressing the ring at each of N network devices.

Although not shown inFIG. 1, other packet-forwarding network devices may be deployed along ring network10to forward or relay packets without providing either an ingress or egress for the network ring. In such cases, these packet-forwarding network devices may employ the queuing techniques described herein. Moreover, such devices need not necessarily be accounted for when determining the number of queues based on the various combinations of ordered-pairs of network devices as such devices neither ingress packets to or egress packets from ring network10.

In some cases, as explained below, for multicast packets, this may also include an order-dependent pair for which the originating device is equivalent to the destination device. Thus, any given intermediate network device12(e.g., network device12C) may maintain one queue to store packets injected into the ring network by network device12A to be egressed at network device12B, and a second queue to store packets ingressed at network device12C and to be egressed from the ring at network device12A. Thus, each queue is “order-dependent” in that a separate queue exists for each variation of the order of the pair of referenced devices, e.g., network devices12A,12C. Thus, in a ring network comprising N network devices12along the ring, each of the network devices12maintains a set of queues20that includes N×(N−1)≈N2distinct queues for forwarding traffic along the network ring. That is, assuming no queues are separately allocated for multicast traffic, each of the N network devices12(including that same network device) may inject traffic to egress the ring at any of the other N−1 network devices. Assuming for exemplary purposes that ring network10ofFIG. 1includes fourteen network devices12, each of network devices12configures a total of N*N−1 (or approximately 142) or 196 queues, an abbreviated listing of which proceeds below in Table 1, ingress device refers to the node that injected the packet into the ring (possibly after receiving the packet from a source end-user device) and egress device refers to the network device that will remove the packet from the ring network (and possibly forward the packet to a destination end-user device):

As shown in the above Table 1, queues20may include queues for storing packets where the ingress network device and egress network device reference the same device. By convention, these queues20may be designated to store both broadcast packets, e.g., packet to be sent to all nodes of the ring except for the ingress node, and multicast packets, e.g., packets to be sent in a point-to-multipoint (P2MP) fashion to members of a multicast group, wherein the originating/destination device may identify a multicast group associated with the packets. In one embodiment, a queue used to store multicast packets ingressing the ring at a network device using an order-dependent pair in which the originating device is the same as the destination device. See, for example, queues 0 and 195 above. In some embodiments, at any of network devices12, only one of the plurality of queues20need be used to store all multicast packets ingressing anywhere on the network ring, and network devices12may only define one such queue20with the understanding that all multicast packets be stored to this one of queues20. Alternatively, in networks10not requiring multicast packets, network devices12may eliminate these queues20thereby decreasing the total number of queues from N2to (N)×(N−1) queues or approximately N2, where N equals the number of network devices12interspersed around ring network10.

In some embodiments, network devices12may, instead of just configuring a single queue for each order-dependent pair of network devices along the network ring, configure a queue for each QoS class for each order-dependent pair for a total of approximately N2×M, where M equals the number of QoS classes. The following table 2 presents an abbreviated listing of these queues assuming N=14 and:

After internally configuring its own set of queues20, each of network devices12may receive packets from respective end-user devices16to be injected into ring network10. Network devices12may also receive packets from other network devices12that have already entered ring network10at one or more other network devices12. Each packet includes a source address and a destination address, where each address may comprise an L3 address (e.g., an internet protocol (IP) address) or an L2 address (e.g., MAC address). During forwarding of the packets on the network ring, each of network devices12may determine the ingress and egress network devices for each packet based on the address information within the packet and, based on that determination, select and store each packet to an appropriate one of queues20. For example, such determination may be made by routing data and/or forwarding data maintained internally by each of the network devices12. Network device12A may parse the packet to determine these addresses and, using these addresses as a key, determine to which of queues20to store the received packet. In this way, the source and destination address information of a packet may be compared to the routing data so that the network device12forwarding the packet is able to determine the point along network ring10the packet was injected as well as the point at which the packet will be removed from the ring.

As another example, when injecting a packet into the network ring, the ingress network device12may add a tag, label or other identifier to the packet that uniquely identifies the ingress and egress device of the packet. For example, each of network devices12may store commonly agreed upon identifiers associated with each of the order-dependent pairs (ingress device, egress device), and such identifiers may be used by each of the network devices12at the time of forwarding packets to select an appropriate one of the internal queues. One example of such labels is Multi Protocol Label Switching (MPLS) labels, and distinct label switched paths (LSPs) may be assigned to each of the order-dependent pairs of network devices along network ring10.

In instances where QoS classes are employed, network devices12may be further configured to tag each packet upon receipt from an end-user device16so as to further specify a QoS class for the tagged packet. For example, a packet conforming to a Voice over Internet Protocol (VoIP), such as a session initiation protocol (SIP), may be tagged to indicate a voice QoS class. When injecting packets into network ring10, network devices12may analyze each packet to determine the QoS class to which the packet corresponds and, based on this determination, assign an appropriate identifier (or identifiers) to the packet to indicate the ingress and egress network device as well as the QoS class for the packet. As discussed above, network devices12may make use of MPLS labels, and network devices12may negotiate and establish distinct LSPs around network10for each combination of order-dependent (ingress, egress) pairs and QoS class.

For example, assuming network device12B receives a transit packet from network device12A, network device12B may store the received packet to one of queues numbered 3, 4, or 5 within Table 2 based on the QoS tag and the source and destination addresses. Network device12A may have initially received the packet from end-user device16B, and may tag the packet to specify that the packet is associated with a voice QoS class and that the packet is associated with an LSP traversing network ring10from network device12A to network device12B. After tagging the packet (i.e., adding the appropriate MPLS label), network device12A injects the packet onto network ring10. Upon receiving the packet from network device12A, network device12B then parses the label stack of the packet to determine to which of queues20to store the packet. Considering that the tag (MPLS label in this example) indicates that the packet is associated with the voice QoS class, the packet was received via an LSP traversing the network ring from network device12A to network device12B, and using Table 2 as an example, network device12B stores the packet to queue number 3 of its internal queue20.

Each of network devices12forwards the various packets stored to queues20according to a scheduling algorithm, which is described below in more detail. Generally, network devices12implement the scheduling algorithm as a scheduling module (either in software or in hardware of a forwarding component), and the scheduling algorithm seeks to ensure that each of queues20receive an appropriate allocation of available bandwidth. The scheduling module may, for example, first schedule any packets stored to the voice QoS class queues, second schedule any packets stored to the business QoS class queues, and third schedule any packets stored to the best effort QoS class queues. For queues associated with the same QoS class, the scheduling algorithm may then seek to schedule packet forwarding fairly so as to overcome any preferential treatment to packets that originated at neighboring network devices. For example, the scheduling module of network device12A may schedule packets originating from other network devices12that are remote from network device12A prior to scheduling packets originating from network devices12that are proximate to hub network device12A along the network ring10. Because a queue20exists for each order-dependent pair, network devices12may implement sophisticated scheduling algorithms to account not only for the location of network devices12around ring network10but also for QoS classes for packet flows. Thus, by implementing the packet queuing techniques, network devices12may possibly reduce or even eliminate delays, as well as provide better assurance that QoS end user agreements will not be violated.

FIG. 2is a block diagram illustrating an example embodiment of network device12B ofFIG. 1in more detail. In this example, network device12B comprises a control unit22, a memory24, and interface cards26(“IFCs26”). Control unit22couples to both memory24and IFCs26, where control unit22may couple to IFCs26via a switch fabric (not shown). Although described in reference to network device12B, each of network devices12may include substantially similar components to those described below in reference to network device12B.

As shown inFIG. 2, control unit22may be logically divided into two portions, a control plane portion28A and a data plane portion28B. Control plane28A represents the hardware and software components that provide an operating environment for network protocols that are utilized to communicate with peer devices, e.g., other network devices12, and provision queues20. For example, control plane may include one or more microprocessors that execute an operating system on which the network protocols and other software execute. Data plane28B represents the hardware and software components for handling data or packet forwarding. Data plane28B may, for example, comprise a set of one or more dedicated ASICs for forwarding packets. Although shown as two portions28A,28B within a single control unit22, the two portions may each comprise separate hardware and software to provide for the functionality attributed to these portions herein.

Control plane28A includes a queue provisioning module32that is responsible for establishing queues20within memory24. In this example, queue provisioning module includes resource reservation protocol module30(“RSVP30”) that executes the RSVP protocol to negotiate with peer network devices12so as to establish LSPs and reserve bandwidth for those LSPs. Queue provisioning module32may utilize RSVP30to determine information pertinent to configuring queues20, such as the number of network devices12and QoS classes, as well as the amount of bandwidth to allocate to each of queues20.

Data plane28B includes queue scheduler module34, forwarding module36and queue maintenance module38. Queue scheduler module34represents a module that implements a scheduling algorithm, which, as described above, schedules currently stored packets for removal from queues20and forwarding over ring network10. Forwarding module36represents a module responsible for forwarding the scheduled packets along the ring network. Packets may, from a forwarding perspective, traverse the ring in one of three ways: clockwise, counter-clockwise, and sideways. Clockwise traversal, as the name suggests, indicates that the packet traverses ring network10(FIG. 1) in a clockwise direction. Counter-clockwise traversal, again as the name suggests, indicates that the packet traverses ring network10in a counter-clockwise direction. Sideways traversal indicates that the packet received from the ring network10by a network device12exits the ring network at that given network device12, thereby exiting or moving “sideways” from ring network10. Forwarding module36and queue maintenance module38may be implemented in hardware as an ASIC or other component, firmware, or as software executable on a microcontroller or embedded processor within dataplane28B.

Queue maintenance module38represents a module responsible for monitoring the status of each of queues20. In particular, maintenance module38may determine whether each of queues20are nearing capacity and, in response, generate a flow control message to indicate that the ingress network device associated with that particular queue20needs to reduce or possibly stop traffic destined for network device12B. Queue maintenance module38may regularly send these flow control messages, much like the hello messages described above. In some embodiments, queue maintenance module40may utilize these flow control messages in place of the above mentioned hello messages, as described in more detail below. Queue maintenance module38may be implemented in hardware as an ASIC or other component, firmware, or as software executable on a microcontroller or embedded processor within dataplane28B.

Memory24may comprise any combination of static memory, e.g., a hard drive, read only memory (ROM), electrically erasable programmable ROM (EEROM), and flash memory, and/or dynamic memory, e.g., random access memory (RAM), static RAM (SRAM), dynamic RAM (DRAM), and a cache. Memory24stores a plurality of queues20A-20N (“queues20”), a transmit queue40, and a queue bit vector42. Transmit queue40represents a queue (or plurality of queues, such as in instances where each of IFCs26include one transmit queue) that stores packets scheduled to be forwarded over ring network10via IFCs26. Queue bit vector42represents any data structure, not necessarily a queue, capable of representing the current state of each of queues20. In one embodiment, queue bit vector42comprises a bit for each of queues20, where each bit indicates whether the respective queue20is nearing capacity or is capable of storing additional packets.

Initially, upon being powered up or otherwise activated within ring network10, network device12B configures queues20within memory24. In particular, queue provisioning module32determines the number of network devices12interspersed around ring network10. Queue provisioning module32may be configured statically by a network administrator with the number of network devices and applicable QoS classes, and/or may automatically learn (i.e., discover) the number of network devices and applicable QoS classes dynamically from a provisioning system (not shown inFIG. 1) or via exchange of control-plane protocol messages, such as RSVP messages formulated in accordance with RSVP30. Queue provisioning module32configures queues20by allocating distinct queue data structures within memory24based on the number of queues necessary to support the ring topology in accordance with the queuing techniques described herein.

Queue provisioning module32may also be statically configured and/or may dynamically learn how much of the available bandwidth to allocate to each of queues20. Based on the bandwidth each queue is to receive, queue provisioning module32may adjust the size of the queue data structure, i.e., each of queues20, to allocate an appropriate amount of bandwidth to each of queues20. A larger queue data structure may be used to buffer packets for higher allocations of bandwidth by allowing that queue20to store more packets, which during times of congestion, may allow the associated queue20to store more packets before nearing capacity. A smaller relative queue data structure may be used for queues having allocations of less bandwidth by allowing that queue20to store less packets, which during times of congestion, may prohibit the associated queue20from storing packets, as the associated queue20may overrun its capacity more quickly.

Once queues20are configured, IFCs26of network device12B may begin receiving packets from other network devices12or from end-user device16A. The packets received by network device12B may include some information identifying one or more of which of the three forwarding actions to perform and to which queues20to store the packet. The information may comprise one or more multiprotocol label switching (MPLS) protocol labels formed in accordance with a MPLS protocol. Alternatively or in conjunction with MPLS, the information may comprise one or more of a virtual local area network (VLAN) protocol identifier (ID). Control plane28A therefore may include, as shown inFIG. 2, one or both of a RSVP protocol30(or a Label Distribution Protocol (LDP) module) for establishing MPLS LSPs and/or a VLAN protocol module (“VLAN31B”) for establishing VLANs.

When MPLS labels are employed for queue identification, queue scheduler module34may pop the MPLS label from the label stack and, based on this label, store the packet to the one of queues20associated with the LSP represented by the label. Thus, a mapping exists between the MPLS labels utilized for traversing the LSPs around ring network10and queues20internally maintained by network device12B. In other words, each queue may be associated with a corresponding MPLS label value, and each label may be associated by network device12B with a different ordered-pair of ingress/egress devices in combination with a particular QoS class. Queue provisioning module32may create and store this mapping and may install the mapping within queue scheduler module34to configure data plane28B. As a result, when forwarding a packet, queue scheduler module34may look up the MPLS label carried by the packet within the stored MPLS->queue mapping and determine an identifier of or pointer to the appropriate one of queues20that is associated with the MPLS label of the packet.

Similarly, when VLAN IDs are employed for queue identification, queue scheduler module34may extract the VLAN ID and, based on this ID, store the packet to the queue20mapped to that particular VLAN ID for the VLAN that is established for the particular ordered-pair of ingress/egress devices in combination with a particular QoS class. Again, a mapping may exist between each VLAN ID and a corresponding one of queues20, i.e., each queue may be associated with a corresponding VLAN ID. VLAN31B executes the VLAN protocol in the control plane to establish the VLANs with other network devices12and installs the mapping within queue scheduler module34when configuring the data plane28B. Queue scheduler module34may provide the packet having the VLAN ID to VLAN31B, which may look up the VLAN ID label value within the mapping maintained by VLAN31B and return to queue scheduler module34the number of the queue that is associated with the VLAN ID of the packet according to the mapping.

In addition to storing packet to queues20, queue scheduler module34concurrently implements a scheduling algorithm that, in one embodiment, seeks to provide fairer treatment of packets by taking into considering the placement of network devices12around ring network10and possibly even QoS classes for different packet flows. A variety of scheduling algorithms may be employed. As one example, queue scheduler module34may first traverse each of queues20and move buffered packets from those queues20that are both associated with a highest QoS class and that are used for buffering packets from network devices12remote from network device12B. Queue schedule module34moves those packets to a transmit queue40for direct output to the ring network10. Queue scheduler module34continues to traverse queues20and move to transmit queue40any packets from queues corresponding to network devices12more proximate to a hub, e.g., network device12A, and having a lower QoS class designations. In this example, queue scheduling module34traverses the queues20so as to prioritize packets based first the distance to the ingress network device and then, for packets ingressed by the same network device, based on quality of service. In this example, those packets bearing a “Best Effort” QoS class designation and from highly proximate network devices may be scheduled last. As another example, a different algorithm may be applied so as to prioritize packets based first on QoS class and then, for packets having the same QoS class, based on distance to the ingress network device that injected the packet. In addition, queue scheduler module34may implement a scheduling algorithm having a round-robin component so as to ensure that queue scheduler module34schedules at least one packet from each of queues20during a set period of time.

While queue scheduler module34schedules packets for forwarding, queue maintenance module38of control plane28A monitors queues20to determine whether any of queues20are within a threshold of its particular capacity. For each of queues20that is near its capacity, queue maintenance module38updates an associated bit within queue bit vector42to indicate that the corresponding queue is near its capacity. Queue maintenance module38may, at regular intervals or upon a change in one of the bits of queue bit vector42, generate a control message. The control message may include a copy of queue bit vector42or otherwise indicate the status of queues20, e.g., by including only those bits of queue bit vector42that indicate an associated queue is near capacity. Queue maintenance module38forwards the control message around ring network10, e.g., in the direction counter to that at which data plane packets are forwarded around the ring, as shown inFIG. 1. As successive network devices12receive the control message, those network devices12responsible for injecting the packets that have filled those queues indicated as near capacity within network device12B may pause injecting such packets onto ring network10so as to allow the near capacity queues20to transmit stored packets and free up space within those near capacity queues20. In order to use these control messages, each of network devices12may maintain a similar queue bit vector in which each bit corresponds to the same ordered-pair and such vector may be determined based on a mutually agreed-upon ranking of network devices12as well as agreed-upon ranking of QoS classes. In other words, the network devices12within ring network10employ a common queue labeling scheme so that the particular ordered-pair/QoS combination represented by each bit of the queue bit vector12is understood by each of the network devices.

As another example, an entire vector need not be sent and a control message may include one or more rank-ordered labels identifying only the particular queues at or near capacity.

Queue maintenance module38may, in some embodiments, send these control messages at regular intervals to keep network devices12apprised of the capacity of queues20of network device12A. In these embodiments, network devices12may be configured to forgo using conventional hello messages and instead employ these control messages for the additional purpose of detecting failed links14in place of the conventional hello messages. Thus, queue maintenance module38may also maintain a maximum response time interval by which network device12B should receive a control message from network device12A. If queue maintenance module38does not receive a flow control message from network devices12A within a time specified by maximum response interval, queue maintenance module38determines that the respective link14between network devices12A and network device12B has failed. Queue maintenance module38may then formulate and forward a failed link message (or more generally, a control message) to inform all of the other network devices12that a link has failed. As described above, upon receiving the failed link message, network devices12may update its forwarding module36to account for the failed link.

Forwarding module36, as described above, forwards to ring network10via IFCs26any packets stored within transmit queue40as well as and control messages produced by control plane28A. RSVP30and VLAN31B as well as any other network protocols executing within control plane28A install forwarding information (e.g., in the form of a radix tree mapping next hops to output ports) within forwarding module36to configure data plane28B and control packet forwarding. Forwarding component36utilizes the forwarding information in order to determine the appropriate direction, e.g., clockwise, counter-clockwise, or sideways, to forward a received packet. Based on headers within the packet, such as an MPLS label or VLAN id, forwarding module36forwards the packet to the appropriate IFC26, which in turn outputs the packet via one of links14to another one of network devices12along ring network10or to one of end-user devices16. In this manner, network device12B performs the packet queuing techniques to possibly reduce packet forwarding delays due to the ring structure of network10. Network device12B may also avoid violation of QoS agreements with end-users by taking QoS classes into consideration when queuing and scheduling packets for forwarding.

The fair packet queuing techniques are described above with respect to a number of modules and components; however, these modules and components are presented merely for purposes of illustration. The modules may be implemented as separate functionalities of a single hardware component or of a single software program. Moreover, the modules may be implemented as a combination of both hardware and software. For example, a computer-readable storage medium may store instructions (e.g., software) that cause a programmable processor (e.g., hardware) to perform the fair packet queuing techniques described herein. In addition, different criteria and scheduling algorithms may be used. The techniques, therefore, should not be strictly limited to the particular exemplary embodiments described herein and may include a number of other embodiments.

FIG. 3is a flow chart illustrating exemplary operation of a network device, such as network device12B ofFIG. 2, in performing the packet queuing techniques described herein. Prior to forwarding packets around a ring network, such as ring network10ofFIG. 1, network device12B first configures queues20(44). As described above, queue provisioning module32of network device12B configures a separate queue20for each order-dependent pair of network devices12and optionally for each combination of order-dependent pair and QoS class.

For example, queue provisioning module32may configure a first queue20A to store packets that enter the ring network at network device12A and will egress the ring at network device12B, queue20B to store packets that enter the ring network at network device12A and egress at network device12C, etc. Alternatively, queue provisioning module32may configure queue20A to store packet having, for example, a voice QoS class designation that ingress at network device12A and will egress at network device12B, queue20B to store packets having a business QoS class designation that ingress from network device12A and will egress at network device12C, etc. Queue provisioning module32may define a queue data structure and allocate to each queue data structure a portion of memory24, which, as described above, may apportion bandwidth to each queue (46). That is, the allocated portion of memory24may indicate the portion of the available bandwidth each queue is to receive. Queue provisioning module32may be configured with the allocated portion of bandwidth each of queues20are to receive statically and/or learn this information dynamically, as described above.

After configuring queues20, network device12B receives packets via IFCs26(48). Queue scheduler module34stores these packets to queues20in the manner described above, e.g., based on information carried within a header of the packets (50). For example, queue scheduler module34may employ inspect each of the received packets to determine an MPLS label, a VLAN ID or other information so as to determine to which of queues20to store the received packets based on an MPLS label or VLAN identifier within a header of the packets. Alternatively, or in conjunction with MPLS labels or VLAN identifiers, queue scheduler module34may parse the packets to determine source and destination addresses, and based on these addresses, determine to which of queues20to store the received packets. In any event, queue scheduler module34stores the received packets to an appropriate one of queues20as described herein. In this manner, queue scheduler module directs received packets into the appropriate queues for further processing.

Concurrent with this operation, queue scheduler module34also schedules packets currently stored in queues20for forwarding via ring network10(52). Queue scheduler module34may implement a scheduling algorithm based on a variety of factors, as described above. While particular scheduling algorithms are described above, other scheduling algorithms may be used, such as any scheduling algorithm may be employed that accounts for the position of network devices12around ring network10, e.g., with respect to a hub network device, in order to reduce delays associated with packet queuing in a ring network. Queue scheduler module34schedules packets for forwarding by moving the selected packets (or portions thereof, e.g., packet headers) from one of queues20to transmit queue40or by updating pointer references to the packets so as to mark the packets for forwarding without copying packet data.

Forwarding module36removes the packets from transmit queue40, and applies forwarding information to key information within the packets in a high-speed manner to identify the forwarding direction of the packet, and forwards the packet to one of IFCs26(e.g., in accordance with stored forwarding information). IFCs26, upon receiving the packet, forwards the packet via link14around ring network10(54). In this manner, a network device may possibly reduce delays by providing a separate queue for each order-dependent pair of network devices and possibly for each QoS class for each order-dependent pair of network devices. This higher-granularity queuing scheme, when compared to conventional queuing, enables more sophisticated and fine-grained scheduling algorithms that may take into account the position of the network devices around the ring and possibly the different QoS classes.

FIG. 4is a flowchart illustrating exemplary operation of a network device, such as network device12B ofFIG. 2, in configuring queues, such as queues20, in accordance with the fair packet queuing techniques described herein. In order to configure queues20, queue provisioning module32of network device12B initially determines the number of network devices (N) positioned around a ring network, such as ring network10(56).

Queue provisioning module32may determine the number of network devices12statically, dynamically, or a combination of both. That is, queue provisioning module32may be statically configured with the number of network devices by a network administrator via a command line interface or any other interface presented by network device12for receiving configuration commands. Alternatively or in conjunction with static configuration, queue provisioning module32may dynamically learn or determine the number of network devices via communications with a provisioning system. A provisioning system may comprise any system that stores network characteristics, such as QoS classes, the number of network devices, the addresses of network devices, the allocation of bandwidth to each network device or end-user device, or any other characteristic pertinent to forwarding packets around a ring network, such as ring network10. Typically, the provisioning system is configured by an administrator with such network characteristics so that the network administrator need not configure each of network devices12individually and reconfigure devices12each time the network characteristics change.

Queue provisioning module32may also determine the number of quality of service (QoS) classes (M) offered by ring network10statically, dynamically, or a combination of both (58). As above, queue provisioning module32may be statically configured with the number of quality of service classes by a network administrator. Also similar to above, queue provisioning module32may dynamically learn or determine via communications with the provisioning system the number of QoS classes.

In order to configure queues20, queue provisioning module32may also determine a portion of the available bandwidth that should be allocated to each of queues20(60). Again, queue provisioning module32may be statically configured with this bandwidth information or may dynamically learn this information from the provisioning system. Moreover, queue provisioning module32may employ a protocol, such as RSVP30, to dynamically learn or determine the bandwidth allocation from other network devices12.

Upon learning the number of network devices, the number of QoS classes, and the bandwidth allocations, queue provisioning module32configures queues20(62). In instances where no QoS classes are defined, queue provisioning module32may configure queues20such that one queue exists for each order-dependent pair of network devices12(i.e., ingress/egress pairs), as described above, for a total number of queues on the order of N2queues within each of the network devices. In instances, however, where a plurality of QoS classes exists, queue provisioning module32configures queues20such that one queue exists for each QoS class for each order-dependent pair of network devices12, as described above, for a total number of queues on the order of N2×M queues within each of the network devices. In instances where multicast traffic is present, queue provisioning module32configures queues for multicast traffic entering the ring at each of network devices12. Queue provisioning module32configures queues20by defining queue data structures within memory24, whereby queue provisioning module32may allocate more memory to those queues having greater bandwidth allocation and less memory to those queues having less bandwidth allocation. In this manner, network device12B configures queues20such that one queue exists for each order-dependent pair of network devices12distributed around ring network10.

FIG. 5is a flowchart illustrating exemplary operation of a network device, such as network device12B, in monitoring queues20in accordance with the fair packet queuing techniques described herein. As described above, queues20may be configured such that each of queues20are allocated an amount of memory reflective of each of queues20associated bandwidth. Therefore, to prevent bandwidth overruns, queue maintenance module38of network device12B monitors each of queues20to ensure that bandwidth overruns do not occur. Queue maintenance module38further ensures that packets stored to near capacity queues20are not dropped, which may result in violations of QoS agreements with end users.

Queue maintenance module38monitors each of queues20by first determining the state of each of queues20(64). Queue maintenance module38may determine the state of each of queues20by determining whether each of queues20is near capacity (66). Near capacity queues20may be identified by measuring the current amount of memory occupied by packets stored to each of queues20against the total amount of memory allocated to each of queues20. Queue maintenance module38may be configured by an administrator statically or may dynamically learn or determine capacity thresholds, e.g., ratios between occupied and total memory space, for each queue20that indicate when that particular queue is considered near capacity (e.g., 0.8 or 0.95). If the current capacity, e.g., ratio between the occupied and allocated memory space, exceeds or equals the established capacity level for that queue, queue maintenance module38sets a corresponding bit within queue bit vector42to indicate the associated one of queues20is nearing capacity (68).

Upon updating queue bit vector42, queue maintenance module38generates a control message that includes queue bit vector42, as described above (72). Next, queue maintenance module38forwards the control message by, for example, storing the control message to either one of queues20or transmit queue40(74). Queue maintenance module38may store the control message directly to transmit queue40as the control message may indicate critical capacity concerns that require immediate action.

However, upon determining that the queue is not near capacity (e.g., does not exceed the established capacity levels), queue maintenance module38updates queue bit vector42to indicate that the associated one of queues20is not near capacity (70). Queue maintenance module38may similarly generate a control message and forward the control message (72,74), especially in the event such control messages are used by network devices12in place of keep alives or other periodic status messages. If not, queue maintenance module38may skip the operation of generating and forwarding a control message if none of the queues are near capacity.

In this manner, network devices within a ring network may apprise other network devices within the ring network of the capacity of queues20such that other network devices may adjust packet forwarding to account for near capacity queues by refraining from transmitting packets destined for those near capacity queues20. This aspect of the fair packet queuing techniques enables network devices not only to adjust forwarding to prevent packets from being dropped but also may replace the above described hello messages, especially when these control messages are sent at frequent intervals, e.g., on the order of milliseconds. Various embodiments of the invention have been described. These and other embodiments are within the scope of the following claims.