Protected UBR

[0001] The present invention is related to transferring UBR traffic. More specifically, the present invention is related to transferring UBR traffic which is protected from congestion.

[0002] UBR traffic in an ATM network generally has the lowest status in regard to transference of all types of traffic on an ATM network. Because of its status, it has in the network relative to the other clones of traffic which travel on the ATM network, it has the greatest chance of experiencing congestion. The present invention identifies desired UBR traffic of the UBR traffic and protects it from congestion.

[0003] The present invention pertains to a switch for transferring UBR traffic on an ATM network. The switch comprises a mechanism for receiving UBR traffic from the network and sending UBR traffic to the network. The switch comprises a mechanism for prohibiting a predefined condition in the UBR traffic, the prohibiting mechanism connected to the receiving and sending mechanism.

[0004] The present invention pertains to a switch for transferring UBR traffic on an ATM network. The switch comprises a mechanism for receiving UBR traffic in connections from the network and sending UBR traffic in the connections to the network. The switch comprises a mechanism for dynamic analysis of the connections of UBR traffic to determine whether the connections have UBR traffic which behaves or which misbehaves.

[0005] The present invention pertains to a switch for transferring UBR traffic on an ATM network. The switch comprises a mechanism for receiving UBR traffic in connections from the network and sending UBR traffic in the connections to the network. The switch comprises a mechanism for reevaluating connections to determine whether the connections have UBR traffic which behaves or which misbehaves at a predetermined interval.

[0006] The present invention pertains to a method for transferring UBR traffic on an ATM network. The method comprises the steps of forming connections having UBR traffic with a switch of an ATM network. Then there is the step of receiving UBR traffic on the connections at the switch. Next there is the step of determining whether the connections have misbehaving UBR traffic or behaving UBR traffic. Then there is the step of prohibiting congestion of the UBR traffic by discarding misbehaving UBR traffic received by the switch on connections having misbehaving UBR traffic. Next there is the step of sending behaving UBR traffic to the network.

[0015] Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically to FIG. 1 thereof, there is shown a switch 10 for transferring UBR traffic on an ATM network 12. The switch 10 comprises a mechanism for receiving UBR traffic from the network 12 and sending UBR traffic to the network 12. The switch 10 comprises a mechanism for prohibiting a predefined condition in the UBR traffic, the prohibiting mechanism 16 connected to the receiving and sending mechanism 14.

[0016] Preferably, the prohibiting mechanism 16 includes a mechanism 18 for separating the UBR traffic into a first type of UBR traffic and a second type of UBR traffic. The prohibiting mechanism 16 preferably discards the second type of UBR traffic to prohibit the predetermined condition congestion in the UBR traffic. Preferably, the prohibiting mechanism 16 places a tag with the second type UBR traffic.

[0017] The prohibiting mechanism 16 preferably discards second type UBR traffic with the tag when a predetermined threshold is exceeded regarding the second type UBR traffic. Preferably, the prohibiting mechanism 16 gives weight to the first type of UBR traffic and second type of UBR traffic which remains after any second type of UBR traffic is discarded, and the prohibiting mechanism 16 includes a server 20. The server 20 provides service to the first type of UBR traffic and second type of UBR traffic according to the weight of the first type of UBR traffic and the second type of UBR traffic.

[0018] The prohibiting mechanism 16 preferably performs a dynamic analysis of UBR traffic to determine whether the UBR traffic is first type UBR traffic or second time UBR traffic. Preferably, the UBR traffic is associated with connections and wherein the prohibiting mechanism 16 reevaluates the connections of UBR traffic received by the receiving and sending mechanism 14 at a predetermined interval to determine whether the connections have the second type of UBR traffic or have the first type of UBR traffic. The prohibiting mechanism 16 preferably only reevaluates the connections, which have changed during the interval.

[0019] Preferably, the prohibiting mechanism 16 untags any traffic which is tagged that is received by the receiving and sending mechanism 14. The UBR traffic preferably includes cells each of which having a CLP field and wherein the prohibiting mechanism 16 places the tag in the CLP field of each cell of a connection of the second type of UBR traffic. Preferably, the predetermined condition is congestion and connections having the first type of UBR traffic are guaranteed service by the server 20. The first type of UBR traffic preferably is behaved UBR traffic and the second type of UBR traffic is misbehaved UBR traffic.

[0020] Preferably, the dynamic analysis occurs according to ${\mathrm{AllocatedBWVC}}_x=\frac{W_x}{\sum _i{W}_i}\times <\mathrm{PortLineRate}>$
where W₁ is estimated bandwidth for i^th connection and W_x is a weighted sum of all bandwidth over all connections. The receiving and sending mechanism 14 preferably includes a receive side 22 having input ports 24 for receiving UBR traffic from the ATM network 12,. and a second side 25 having output ports 26 for sending packets to the ATM network 12.

[0021] The present invention pertains to a switch 10 for transferring UBR traffic on an ATM network 12. The switch 10 comprises a mechanism for receiving UBR traffic in connections from the network 12 and sending UBR traffic in the connections to the network 12. The switch 10 comprises a mechanism 28 for dynamic analysis of the connections of UBR traffic to determine whether the connections have UBR traffic which behaves or which misbehaves.

[0022] The present invention pertains to a switch 10 for transferring UBR traffic on an ATM network 12. The switch 10 comprises a mechanism for receiving UBR traffic in connections from the network 12 and sending UBR traffic in the connections to the network 12. The switch 10 comprises a mechanism 30 for reevaluating connections to determine whether the connections have UBR traffic which behaves or which misbehaves at a predetermined interval.

[0023] The present invention pertains to a method for transferring UBR traffic on an ATM network 12. The method comprises the steps of forming connections having UBR traffic with a switch 10 of an ATM network 12. Then there is the step of receiving UBR traffic on the connections at the switch 10. Next there is the step of determining whether the connections have misbehaving UBR traffic or behaving UBR traffic. Then there is the step of prohibiting congestion of the UBR traffic by discarding misbehaving UBR traffic received by the switch 10 on connections having misbehaving UBR traffic. Next there is the step of sending behaving UBR traffic to the network 12.

[0024] Preferably, the prohibiting step includes the step of placing a tag with traffic of connections having misbehaving UBR traffic. The discarding step preferably includes the step of discarding tagged misbehaving UBR traffic when a predetermined threshold is exceeded regarding the misbehaving UBR traffic. Preferably, the prohibiting step includes the steps of giving weight to behaving UBR traffic connections and misbehaving UBR traffic which remain after any misbehaving UBR traffic is discarded, and providing service with a server 20 to the behaving UBR connections and the misbehaving UBR traffic according to the weight of the connections.

[0025] The prohibiting step preferably includes the step of performing dynamic analysis on the UBR traffic of the connections to determine whether the UBR traffic of the connections is behaving UBR traffic or misbehaving UBR traffic. Preferably, the prohibiting step includes the step of reevaluating the connections of UBR traffic received at the switch 10 at a predetermined interval to determine whether the connections have behaving UBR traffic or misbehaving UBR traffic. The reevaluating step preferably includes the step of reevaluating only the connections, which have changed in the interval.

[0026] Preferably, after the receiving step, there is the step of untagging any UBR traffic which is tagged that is received by the switch 10. The tagging step preferably includes the step of placing a tag in the CLP field of each cell of a connection having UBR traffic which misbehaves.

[0027] In the operation of the preferred embodiment, the present invention identifies a new traffic class, Protected UBR, that will be supported in the ASX- 4000 product of Fore Systems, Inc., Warrendale, Pa. Protected UBR is similar to UBR in that it identifies best-effort traffic scheduling in the switch 10. Protected UBR differs from UBR only during periods of sustained overload. Under Protected UBR, each “well-behaved” UBR VC is protected from other UBR VCs that may not be “well-behaved”. A protected UBR VC is guaranteed switch 10 resources up to a defined “well-behavior” limit. Above that limit, resources are allocated fairly among all VCs. By guaranteeing switch 10 resources, a protected UBR VCs performance can be predicted during sustained overload periods.

[0028] UBR and Protected UBR perform identically until traffic is offered to the switch 10 that overloads a single output port for a sustained period of time such that a queue memory 36 is filled and a cell must be dropped. UBR and Protected UBR differ only in the identification of the which cells to drop once a queue memory 36 is filled. UBR drops cells fairly based on the offered load of the switch 10 and Protected UBR drops cells fairly based on a defined output limit.

[0029] As an example, and referring to FIG. 2, consider three UBR VCs (A, B and C) that arrive as input to an ASX- 4000 on three separate OC-12 ports and are transmitted on output port D:

[0030]

	offered load	UBR	Protected UBR
	A	0.33	0.20	0.33
	B	0.33	0.20	0.33
	C	1.00	0.60	0.33

[0031] Under standard UBR, all three VCs are treated fairly. They receive equal access to the output scheduler 34 and queue memory 36 locations. During a sustained overload period, the egress scheduler 34 memory 36 becomes full and cells are dropped. Cells are dropped at the admission process to the cell memory 36. Cells are admitted fairly based on their arrival rate to the egress scheduler 34. Consider an offered load of 0.33, 0.33 and 1.0 of OC-12 line rate for VCs A, B and C, respectively. Once memory 36 is filled, all arriving cells are treated fairly and are admitted based on their arrival rate. Cells from VC C are admitted at three times the rate of cells from VCs A and B. Due to the admission process, the output rates of the VCs are 0.2, 0.2 and 0.6, respectively, which maintains the three to one fairness based on the VC arrival rates.

[0032] Under Protected UBR, VCs A and B are “protected” from VC C which is causing the overload of output port D. If VCs A, B and C are to be treated equally, they are each allocated ⅓rd of the output BW of port D. The admission policy at the egress scheduler 34 is modified to admit cells based on the intended output rate of the VCs. Under Protected UBR, the output rates of VCs A, B and C are 0.33, 0.33 and 0.33. The exact calculation for the allocation of the output BW and how Protected UBR is implemented in the ASX- 4000 is given below.

Configuring Protected UBR occurs in the following way.

[0033] Protected UBR is not signaled and must be configured at each switch 10. To aid in flexibility at the switch 10, Protected UBR is configured on a port-by-port basis. Each link in the network 12 is identified as either a “UBR-link”, or a “Protected UBR-link” as shown in FIG. 3. To facilitate the link mode, the switch 10 ports at both connections of the link are programmed as either UBR mode (by default), or Protected UBR mode.

[0034] Since ports can be configured individually, a switch 10 can support both UBR and Protected UBR links simultaneously.

[0035] To implement Protected UBR, the desired output bandwidth for each VC on a Protected UBR output port must be calculated. Each VC is allocated a fraction of the output bandwidth of the output port and is then guaranteed enough switch 10 resources to guarantee that it can always achieve that bandwidth. The fraction of the output bandwidth that is allocated to a Protected UBR VC is calculated using the estimated bandwidth, W_i, assigned to the VC in the load balanced weighted UBR constraint-based routing protocol. The bandwidth allocated to a particular VC, VC_x, is the weighted sum of all of VC_x over all of the VCs, VC_i, on the output port: ${\mathrm{AllocatedBWVC}}_x=\frac{W_x}{\sum _i{W}_i}\times <\mathrm{PortLineRate}>$
where W_i is estimated bandwidth for i^th connection and W_x is a weighted sum of all bandwidths over all connections.

[0036] If no estimated value is given for a particulate VC, a programmable default value is used. In the example presented above, if VCs A, B and C all have weight 100, then they are each allocated ⅓rd of the output port bandwidth.

[0037] In the ASC-4000 switch 10, there are two resources that must be allocated to implement Protected UBR: the fabric 32 and the output scheduler 34. The fabric 32 receives all cells that are received at input ports 24 of the switch 10. The fabric 32 input stage can always accept cells provided that its memory 36 is not full. Once the memory 36 is full, the cell admission process is based on the CLP bits first, and then based fairly on the cell arrival rate. For queuing purposes, the output scheduler 34 operates in a similar fashion to the fabric 32. All cells that arrive at the output scheduler 34 are queued in memory 36 and scheduled for output provided that its memory 36 is not full. Once full, the admission process is first based on the CLP bits of the cells, and then based fairly on the cell arrival rate.

[0038] Fore UBR VCs, all cells have CLP=0 and the fabrics and output schedulers treat all cells fairly for queue admission, based on their arrival rate. Protected UBR is implemented in the ASX-4000 using the CLP bit in each cell to alter the admission process at the fabric 32 and output scheduler 34. For each output port that is implementing Protected UBR the desired output rate for each VC on the port is calculated using the equation given above. The input port policer for each VC is programmed to clear any arriving CLP=1 bit to CLP=0 and then set the CLP=1 bit for any cell that arrives above the desired output rate threshold. The fabric 32 is programmed to admit all cells (CLP=1 and CLP=0) until it approaches saturation. Once the fabric memory 36 is near full, only CLP=0 cells are admitted and it approaches saturation. Once the fabric memory 36 is near full, only CLP=0 cells are admitted and CLP=1 cells are dropped. The egress scheduler 34 admission policy is programmed in a similar fashion. All cells are admitted until the memory 36 approaches saturation. Once saturated, only CLP=0 cells are accepted for admission. Finally, the egress scheduler 34 is programmed to transmit the UBR VCs in a weighted round-robin fashion, based on the weights calculated above.

[0039] During non-oversubscribed operation, all queues are not full and both CLP=0 and CLP=1 cells are accepted and transmitted. During a sustained oversubscription period, a queue memory 36 becomes full and only CLP=0 cells are accepted. Furthermore, all CLP=0 cells must be accepted, since the weights in the policers are calculated such that all CLP=0 cells are at (or below) line rate for each output port. Thus, during oversubscription the VC throughputs in the switch 10 default to the rate of the CLP=0 cells for each VC. This operation yields the desired results: all cells (CLP=0 and CLP=1) are queued and transmitted during non-oversubscribed periods, and VCs are guaranteed at least their desired resources (CLP=0 cells) during sustained oversubscribed periods.

[0040] In the previous example, as shown in FIG. 4, VC inputs A, B and C have equal UBR-w weights of 100 and are calculated to each run at ⅓rd of line rate of port D during over-subscription. The input stage policers admit CLP=0 cells up to ⅓rd the line rate of port D. All other cells that arrive above ⅓rd the line rate of port D are marked CLP=1. Since all CLP=0 cells are admitted at each stage, each input VC is guaranteed to achieve at least its output rate of ⅓rd the line rate of port D.

[0041] In regard to performance guarantees, by using the CLP bits throughput the switch 10, Protected UBR VCs operate correctly across all port types, including OC-3, OC-12 and OC-48. The following two guarantees can be made about VCs that are transmitted on a Protected UBR link.

• • [0042] G1. The output bandwidth of any Protected UBR VC (VC_x) is guaranteed to be at least equal to its calculated output bandwidth of BW-VC_x≧W_x/ΣW_i.

[0043] Since all CLP=0 cells are guaranteed to be accepted at both the fabric 32 and egress scheduler 34, each Protected UBR VC will achieve at least its calculated output rate. If one of the VCs on the output port is transmitting below its rate, the remaining bandwidth is allocated fairly (based on the cell arrival rate) to the other VCs.

• • [0044] G2. The cell transit delay of any Protected UBR VC that is transmitting below its calculated output bandwidth is guaranteed to be well bounded.

[0045] A low delay bound can be derived from the operation of the egress scheduler 34. To implement Protected UBR, the egress scheduler 34 is programmed to use weighted round-robin for the transmitted cells. The weights for the scheduler 34 are the same as those used to calculate the policer CLP=0 rate. Each VC is guaranteed to have its output cells scheduled at its desired rate if cells are available. Furthermore, the scheduled output rate could exceed that rate if other VCs do not have cells to transmit. Thus, for well-behaved VCs the transmission rate is scheduled at greater than or equal to the input arrival rate at the egress scheduler 34. The delay imposed by the scheduler 34 approaches zero, since the queue will empty.

[0046] Using the example three VCs given above, for well behaved VCs (A and B), the egress scheduler 34 receives cells at ≦⅓rd of the line rate of port D, as shown in FIG. 5. Since all three VCs are equally weighted, they are guaranteed to get ≧⅓rd of the output line rate. The queue depth for VCs A and B will remain close to zero in the egress scheduler 34.

[0047] ASX-4000 side effects using Protected UBR VC. The following side effects are apparent when implementing Protected UBR on the ASX-4000.

• • [0048] 1. Due to the usage of the estimated bandwidth parameters for load balanced UBR that is provided in ForeThought PNNI of Fore Systems, Inc., Warrendale, Pa., incorporated by reference herein, Protected UBR requires the use of ForeThought PNNI with SPVCs and the load balanced UBR option enabled.
  • [0049] 2. For any output port that is implementing Protected UBR, both CLP=0 and CLP=1 cells are transmitted. The ASX-4000 can clear and set the CLP bits in the policer at the input stage of the switch 10. To let the CLP bits be visible at subsequent stages of the switch 10 (fabric 32 and egress scheduler 34 ), they must also be transmitted on the output port. This does not affect transmission of the cells. Subsequent ASX-4000s that receive the cells, first clear the incoming CLP bits and then recalculate the CLP bits based on its output port weights. The CLP bits are also not expected to affect other ATM equipment, since both CLP=0 and CLP=1 cells are always received and transmitted normally. Due to CLP transmission, Protected UBR can be enabled on a per-port basis. In case of future problems with CLP=1 cells, Protected UBR can be disabled on any port that this might cause trouble.
  • [0050] 3. The accuracy of Protected UBR is a function of the accuracy of the input stage policer. The policer can be inaccurate at up to 3% at OC-12 rates.
  • [0051] 4. To maintain call set-up rates, the policer and egress scheduler 34 rates are calculated as a periodic background task. When a new Protected UBR VC is added or deleted, the standard UBR call setup procedure is invoked and a flag is set to indicate that the weights need to be recalculated. Periodically, the flags are examined and the weights are recalculated. A side effect of this implementation is that weights can be inaccurate for a brief period of time following call setup. The switch 10 operates correctly, except that the guaranteed output rates will be slightly incorrect for a brief period of time. The background task period is programmable and is expected to operate at roughly once per second.
  • [0052] 5. For Protected UBR to operate correctly at the fabric 32 level, Protected UBR must be enabled on all ports that are serviced by that fabric 32.

[0053] Although the invention has been described in detail in the foregoing embodiments for the purpose of illustration, it is to be understood that such detail is solely for that purpose and that variations can be made therein by those skilled in the art without departing from the spirit and scope of the invention except as it may be described by the following claims.