Source: https://patents.google.com/patent/US8792352B2/en
Timestamp: 2019-07-20 20:52:47
Document Index: 384236432

Matched Legal Cases: ['Application No. 200880003496', 'Application No. 200580034646', 'Application No. 200880003496', 'Application No. 200580034646', 'Application No. 05812799', 'Application No. 05810244', 'Application No. 05810800', 'Application No. 08728248', 'Application No. 1347', 'Application No. 1345', 'Application No. 1348']

US8792352B2 - Methods and devices for backward congestion notification - Google Patents
US8792352B2
US8792352B2 US13/101,870 US201113101870A US8792352B2 US 8792352 B2 US8792352 B2 US 8792352B2 US 201113101870 A US201113101870 A US 201113101870A US 8792352 B2 US8792352 B2 US 8792352B2
US13/101,870
US20110273983A1 (en
2005-10-11 Priority to US11/248,933 priority Critical patent/US7961621B2/en
2011-05-05 Priority to US13/101,870 priority patent/US8792352B2/en
2011-11-10 Publication of US20110273983A1 publication Critical patent/US20110273983A1/en
2014-07-29 Publication of US8792352B2 publication Critical patent/US8792352B2/en
This application is a divisional of U.S. application Ser. No. 11/248,933, entitled “Methods and Devices for Backward Congestion Notification,” filed on Oct. 11, 2005, by Davide Bergamasco et al, which is incorporated herein by reference in its entirety for all purposes. The present application claims priority to and benefit of this application.
This application is related to U.S. patent application Ser. No. 11/155,388, entitled “ACTIVE QUEUE MANAGEMENT METHODS AND DEVICES” and filed on Jun. 16, 2005 (the “AQM Application”), which is hereby incorporated by reference for all purposes.
Some exemplary high-speed, low latency networks having relatively small buffers, which will be referred to herein as Data Center Ethernet (“DCE”) or the like, are described in U.S. patent application Ser. No. 11/084,587, entitled “Ethernet Extension for the Data Center” and filed on Mar. 18, 2005, to U.S. patent application Ser. No. 11/078,992, entitled “Fibre Channel Over Ethernet” and filed on Mar. 10, 2005 and to U.S. patent application Ser. No. 11/094,877, entitled “Network Device Architecture for Consolidating Input/Output and Reducing Latency” and filed on Mar. 30, 2005, (the “DCE Applications”), all of which are incorporated by reference for all purposes.
More advanced congestion control mechanisms tailored for networks characterized by operational parameters similar to DCE have been considered. One such mechanism is Fibre Channel Congestion Control (“FCC”), a congestion management mechanism for Fibre Channel networks that is described in co-pending U.S. patent application Ser. No. 10/777,886, entitled “End-to-End Congestion Control in a Fibre Channel Network” and filed on Feb. 11, 2004, which is a continuation-in-part of co-pending U.S. patent application Ser. No. 10/026,583, entitled “Methods and Apparatus for Network Congestion Control” and filed on Dec. 18, 2001, both of which are incorporated herein by reference for all purposes.
One exemplary BCN frame is depicted in FIG. 3. BCN frame 305 has a Destination Address (“DA”) 310 that is equal to the Source Address of the sampled frame. BCN frame 305 also has a Source Address (“SA”) 315 equal to an address (here a MAC address) associated with the congestion point. This allows BCN Frame 220 to be routed back to the source of the traffic causing congestion (in this example, to edge switch 110) with a valid source address.
Version field 330 indicates the version of the BCN protocol. In this example, three bits following version field 330 change the semantics of the BCN message when they are set. The meaning of these bits will be described below. Q bit 331 indicates that Qdelta is saturated. In the example described below, Qdelta is saturated when its value is either equal to −2Qeq or −2Qeq. M bit 332 indicates a condition of mild congestion, whereas S bit 333 indicates a condition of severe congestion. Reserved bits in field 335 are not used in this example. Instead, they are set to zero on transmission and ignored on reception. Future versions of the BCN protocol may redefine all or some of the reserved bits.
FIG. 5 illustrates an example of an extended BCN frame 505 that may be used in networks employing MAC-in-MAC encapsulation. Such methods may be implemented, for example, according to a conventional MAC-in-MAC scheme as described in IEEE standard draft 802.1 ah or according to novel methods described in U.S. patent application Ser. No. 11/152,991, entitled “FORWARDING TABLE REDUCTION AND MULTIPATH NETWORK FORWARDING” and filed on Jun. 14, 2005, both of which are hereby incorporated by reference.
According to some implementations of the invention, the rate control algorithm used by rate limiters 740 works according to a Feedback Signal Fb that is calculated, e.g., according to Equation (1):
Special handling of the BCN message is required when any of the Q bits is set in the BCN Frame. When this bit is set, the Qdelta parameter is saturated at 2Qeq or −2Qeq. When this happens, a stronger rate adjustment must be performed because the system is working outside of the linear region. The saturation feedback signal is calculated as follow:
If Fbsat<0 R=R·(1−Gd·|Fbsat|)
In this example, when the occupancy of buffer 905 increases beyond mild congestion threshold (“Bmc”), the M bit will be set in the BCN frame (e.g., in reserved area 335 of frame 305 (see FIG. 3)). The reaction point (e.g., an edge switch) will detect that the M bit has been set and will double the effect of any negative feedback. Positive feedback sent from a congestion point according to the condition of an individual queue with the M bit set will be ignored.
1. A method of controlling a rate of traffic injected into a network, the method comprising:
receiving a first feedback message from a congestion point of a network, the first feedback message comprising an Ethernet frame having embedded therein:
an instantaneous congestion value in a first field of the Ethernet frame;
a congestion change value in a second field of the Ethernet frame, the second field being separate from the first field; and
a congestion point identifier associated with the congestion point;
calculating a rate control value based, at least in part, on the instantaneous congestion value and the congestion change value; and
adjusting a flow rate of traffic addressed to the congestion point according to the rate control value.
2. The method of claim 1, wherein the Ethernet frame includes an EtherType field value that identifies the Ethernet frame as a backwards congestion notification message.
3. The method of claim 1, wherein the Ethernet frame includes first and second congestion condition bits, wherein the first congestion condition bit indicates whether mild congestion is present, and the second congestion condition bit indicates whether severe congestion is present.
4. The method of claim 1, wherein the first feedback message further comprises an indication that an occupancy of a buffer of the congestion point is above a buffer congestion threshold, wherein calculating the rate control value comprises calculating a maximum negative value of the rate control value.
5. The method of claim 1, further comprising adding a tag to frames sent to the congestion point, the tag including data responsive to the first feedback message.
6. An apparatus for controlling a rate of traffic injected into a network, comprising:
a congestion change value in a second field of the Ethernet frame, the second field being separate from the first field, the congestion change value indicating a change in an amount of congestion at the congestion point; and
7. The apparatus of claim 6, wherein the first feedback message identifies a network flow.
8. The apparatus of claim 6, wherein the first feedback message further comprises an indication that an occupancy of a buffer of the congestion point is above a buffer congestion threshold, wherein said calculating step the rate control value comprises calculating a maximum negative value of the rate control value.
9. The apparatus of claim 6, at least one of the processor or the memory being further configured for adding a tag to frames sent to the congestion point, the tag including data responsive to the first feedback message.
10. A device for controlling a rate of traffic injected into a network, the device comprising:
means for receiving a first feedback message from a congestion point of a network, the first feedback message comprising an Ethernet frame having embedded therein:
means for calculating a rate control value based, at least in part, on the instantaneous congestion value and the congestion change value;
means for adjusting a flow rate of traffic addressed to the congestion point according to the rate control value; and
means for adding data responsive to the first feedback message to frames sent to the congestion point.
11. The device of claim 10, wherein the device comprises an ingress port of an edge switch.
12. The device of claim 10, wherein the device comprises an egress port of a host device.
13. A congestion management method, comprising:
detecting network congestion at a first congestion point of a network
determining a current queue level of the congested entity;
sending a first feedback message to a first reaction point of the network, the first reaction point being associated with one or more traffic flows at least partly causing the congestion, the first feedback message comprising an Ethernet frame having embedded therein:
a congestion point identifier associated with the congested; and
determining whether the congestion change value exceeds a predetermined threshold;
wherein the predetermined threshold decreases as a number of active virtual output queues (“VOQs”) in a buffer of the first congestion point increases and wherein the predetermined threshold increases as the number of active VOQs in the buffer decreases.
14. The method of claim 1, wherein the congestion change value is associated with a change in length of a queue.
15. The method of claim 1, wherein the congestion change value indicates a change in a level of congestion since a previous time.
16. The method of claim 1, further comprising adding data responsive to the first feedback message to frames sent to the congestion point.
US13/101,870 2005-10-11 2011-05-05 Methods and devices for backward congestion notification Active 2026-03-05 US8792352B2 (en)
US11/248,933 US7961621B2 (en) 2005-10-11 2005-10-11 Methods and devices for backward congestion notification
US13/101,870 US8792352B2 (en) 2005-10-11 2011-05-05 Methods and devices for backward congestion notification
US14/304,676 US10171328B2 (en) 2005-10-11 2014-06-13 Methods and devices for backward congestion notification
US11/248,933 Division US7961621B2 (en) 2005-10-11 2005-10-11 Methods and devices for backward congestion notification
US14/304,676 Division US10171328B2 (en) 2005-10-11 2014-06-13 Methods and devices for backward congestion notification
US20110273983A1 US20110273983A1 (en) 2011-11-10
US8792352B2 true US8792352B2 (en) 2014-07-29
US11/248,933 Active 2029-01-23 US7961621B2 (en) 2005-10-11 2005-10-11 Methods and devices for backward congestion notification
US13/101,870 Active 2026-03-05 US8792352B2 (en) 2005-10-11 2011-05-05 Methods and devices for backward congestion notification
US14/304,676 Active 2026-01-05 US10171328B2 (en) 2005-10-11 2014-06-13 Methods and devices for backward congestion notification
WO (1) WO2007050250A2 (en)
CN106789701B (en) * 2016-12-30 2019-04-26 北京邮电大学 Adaptive ECN labeling method and device in a kind of data center
EP1028600B1 (en) 1999-02-12 2005-08-31 Juniper Networks, Inc. An optimal buffer management scheme with dynamic queue length thresholds for ATM switches
US6946313B2 (en) 2000-10-13 2005-09-20 Emcore Corporation Method of making an aligned electrode on a semiconductor structure
EP1698600A1 (en) 2003-12-26 2006-09-06 Sekisui Chemical Co., Ltd. Intermediate film for laminated glass and laminated glass
US20070233887A1 (en) 2006-03-28 2007-10-04 Nubani Samer I Method and apparatus for neighborhood discovery across disparate point-to-point networks
US20070280207A1 (en) 2004-03-03 2007-12-06 Mitsubishi Electric Corporation Layer 2 Switch Network System
US8121138B2 (en) 2008-06-20 2012-02-21 Fujitsu Limited Communication apparatus in label switching network
2005-10-11 US US11/248,933 patent/US7961621B2/en active Active
2006-10-03 EP EP20060816262 patent/EP1935137A2/en not_active Withdrawn
2006-10-03 WO PCT/US2006/038858 patent/WO2007050250A2/en active Application Filing
2006-10-03 CN CN 200680032204 patent/CN101253729A/en not_active Application Discontinuation
2011-05-05 US US13/101,870 patent/US8792352B2/en active Active
2014-06-13 US US14/304,676 patent/US10171328B2/en active Active
US20120195310A1 (en) 2004-10-22 2012-08-02 Cisco Technology, Inc. Fibre channel over ethernet
US20120307638A1 (en) 2007-08-21 2012-12-06 Cisco Technology, Inc. Backward congestion notification
CN First Office Action dated Apr. 3, 2009 issued in CN 200680032204.7.
CN First Office Action dated Aug. 11, 2011 issued in Chinese Application No. 200880003496.0.
CN Fourth Office Action dated Dec. 31, 2011, in Chinese Application No. 200580034646.0.
CN Second Office Action dated Jan. 18, 2012 issued in Chinese Application No. 200880003496.0.
CN Third Office Action dated Jul. 6, 2011, in Chinese Application No. 200580034646.0.
EPO Extended Search Report dated Jun. 1, 2011 issued in EP Application No. 05812799.4.
EPO Extended Search Report dated Nov. 12, 2012 issued in EP 05 851 226.0.
EPO Extended Search Report dated Nov. 8, 2012 issued in EP 05 810 293.0.
EPO Office Action dated Apr. 12, 2011, issued in EP Application No. 05810244.3.
EPO Office Action dated May 19, 2011 issued in EP Application No. 05810800.2.
EPO Office Action dated Nov. 18, 2011, issued in EP Application No. 08728248.9.
IN Office Action dated Apr. 12, 2013, issued in IN Application No. 1347/KOLN/2007.
IN Office Action dated Mar. 22, 2013 issued in IN Application No. 1345/KOLNP/2007.
India First Examination Report dated May 29, 2013, issued in IN Application No. 1348/KOLNP/2007.
International Preliminary Report on Patentability and Written Opinion dated Jan. 5, 2010 issued in PCT/US2008/069154.
International Search Report and Written Opinion dated Oct. 15, 2008 issued in PCT/US2008/069154.
K. Ramakrishnan et al., "The Addition of Explicit Congestion Notification (ECN to IP," RFC 3168, Sep. 2001.
U.S. Appl. No. 10/777,886, entitled "End-to-End Congestion Control", filed on Feb. 11, 2004.
US Final Office Action dated Sep. 16, 2011 issued in U.S. Appl. No. 11/400,671.
US Notice of Allowance dated Apr. 4, 2012 issued in U.S. Appl. No. 11/400,671.
US Notice of Allowance dated Aug. 26, 2011 issued in U.S. Appl. No. 12/485,337.
US Notice of Allowance dated Dec. 13, 2011 issued in U.S. Appl. No. 12/485,337.
US Notice of Allowance dated May 1, 2012 issued in U.S. Appl. No. 11/670,544.
US Notice of Allowance dated May 10, 2013 issued in U.S. Appl. No. 12/885,339.
US Notice of Allowance dated May 19, 2011, issued in U.S. Appl. No. 11/084,587.
US Notice of Allowance dated Nov. 18, 2011 issued in U.S. Appl. No. 11/670,544.
US Notice of Allowance dated Nov. 23, 2010 issued in U.S. Appl. No. 11/248,933.
US Notice of Allowance dated Nov. 25, 2011 issued in U.S. Appl. No. 11/825,631.
US Notice of Allowance dated Oct. 7, 2011 issued in U.S. Appl. No. 11/842,866.
US Notice of Allowanced dated Jun. 17, 2013 issued in U.S. Appl. No. 13/112,824.
US Office Action dated Apr. 18, 2013 issued in U.S. Appl. No. 13/444,556.
US Office Action dated Dec. 22, 2011 issued in U.S. Appl. No. 11/400,671.
US Office Action dated Feb. 15, 2013 issued in U.S. Appl. No. 13/112,824.
US Office Action dated Jun. 20, 2013 issued in U.S. Appl. No. 13/357,443.
US Office Action dated May 26, 2011 issued in U.S. Appl. No. 11/825,631.
US Office Action dated May 27, 2011 issued in U.S. Appl. No. 11/842,866.
US Office Action dated Oct. 23, 2012 issued in U.S. Appl. No. 12/885,339.
Wei Cao Huawei Technologies: "IEEE 802.1ah Mode for Ethernet Over MPLS; draft-cao-pwe3-801-1ah-00.txt" IETF Standard-Workingdraft, Internet Engineering Task Force, IETF, CH, Oct. 16, 2006, XP015047518 ISSN: 000-0004.
US20070081454A1 (en) 2007-04-12
US20150124619A1 (en) 2015-05-07
US7961621B2 (en) 2011-06-14
CN101253729A (en) 2008-08-27
WO2007050250A2 (en) 2007-05-03
US20110273983A1 (en) 2011-11-10
EP1935137A2 (en) 2008-06-25
WO2007050250A3 (en) 2007-11-29
US10171328B2 (en) 2019-01-01