Source: http://www.freepatentsonline.com/6862621.html
Timestamp: 2019-12-12 19:30:18
Document Index: 398160094

Matched Legal Cases: ['art 33', 'art 33', 'art 33', 'art 31', 'art 31', 'art 33', 'art 33', 'art 33', 'art 31']

Flow controlling apparatus and node apparatus - Fujitsu Limited
United States Patent 6862621
Takada, Syuji (Kawasaki, JP)
09/902843
370/235, 370/236, 370/412, 709/223, 709/235, 709/236
H04L12/813; H04L12/823; (IPC1-7): G06F15/173
709/223-224, 709/232-236, 370/236, 370/230, 709/203, 370/235, 370/412
Download PDF 6862621 PDF help
6246687 Network switching system supporting guaranteed data rates 2001-06-12 Siu 370/395.71
5694390 Method and apparatus for controlling congestion in communication network 1997-12-02 Yamato et al. 370/230
1. A flow controlling apparatus comprising: a rate-based congestion controlling section for adjusting a rate of a sequence of input packets to a value lower than or equal to a prescribed upper limit value for every flow where the input packets individually belong; queues provided corresponding to classes to which said input packets can belong, for storing and sending said input packets according to first-in first-out; a queue monitoring section for identifying, from said queues, a queue wherein an amount of information in a stored packet exceeds a prescribed threshold value; and a buffer managing section for discarding new packets at a predetermined frequency in every flow to which the new packets belong, said new packet whose rate is adjusted by said rate-based congestion controlling section and being to be stored in said identified queue.
2. The flow controlling apparatus according to claim 1, wherein said buffer managing section for identifying a flow to which an input packet belongs comprises a section which is integral with/provided in said rate-based congestion controlling section.
3. The flow controlling apparatus according to claim 1, further comprising a rate monitoring section for monitoring said rate of said sequence for every flow, and wherein said buffer managing section stores said rate-adjusted packet at a frequency in one of said queues corresponding to classes of said rate-adjusted packet, the frequency being an equivalent of a proportion of said monitored rate in each class to a total of said monitored rates in all the classes, or an equivalent of a proportion as an increasing function of the proportion of said monitored rate in each class.
4. The flow controlling apparatus according to claim 2, further comprising a rate monitoring section for monitoring said rate of said sequence for every flow, and wherein said buffer managing section stores said rate-adjusted packet at a frequency in one of said queues corresponding to classes of said rate-adjusted packet, the frequency being an equivalent of a proportion of said monitored rate in each class to a total of said monitored rates in all the classes, or an equivalent of a proportion as an increasing function of the proportion of said monitored rate in each class.
5. The flow controlling apparatus according to claim 1, wherein said buffer managing section records a past result of packet discard for every flow, and performs one of: excluding a new packet of a flow having said past result from being a subject of discarding; and discarding said new packet at a lower frequency than a frequency at which new packets of a flow not having said past result are to be discarded.
6. The flow controlling apparatus according to claim 1, wherein said buffer managing section counts the number of times packet(s) is/are discarded for every flow, and performs one of: excluding, from a subject of discarding, a new packet of a flow where packet(s) is/are discarded a number of times greater than or equal to a prescribed value; and discarding said new packet at a lower frequency than a frequency at which new packets of a flow where packet(s) is/are discarded a number of times smaller than said prescribed value, are to be discarded.
7. The flow controlling apparatus according to claim 5, wherein said buffer managing section keeps a past result of packet discard for every flow to which the discarded packets belong, and performs one of: excluding, from a subject of discarding, a packet which belongs to a flow whose past result is kept and which is to be stored in said queue identified by said queue monitoring section; and discarding said packet to be stored at a lower frequency than a frequency at which new packets of a flow not having said past result are to be discarded.
8. The flow controlling apparatus according to claim 6, wherein said buffer managing section keeps the number of times packet(s) is/are discarded for every flow, and performs one of: excluding, from a subject of discarding, a packet which belongs to a flow where packet(s) is/are discarded a number of times greater than a predetermined value and is to be stored in said identified queue; and discarding said packet to be stored at a lower frequency than a frequency at which packets belonging to a flow where packet(s) is/are discarded a number of times smaller than said predetermined value, are to be discarded.
9. The flow controlling apparatus according to claim 6, wherein said buffer managing section keeps a number of times packet(s) is/are discarded, whose importance of the kept data is weighed lighter as time elapses, the number being kept corresponding to a flow to which said packet belongs, and performs one of: excluding, from a subject of discarding, a packet of a flow whose number of times packet(s) is/are discarded is kept, and is to be stored in said identified queue; and discarding said packet to be stored at a frequency which is lower, the smaller said number of times said packet is discarded becomes.
10. The flow controlling apparatus according to claim 1, wherein: said queue monitoring section identifies a degree in which said amount of information in packets stored in said queues exceeds said prescribed threshold value; and said buffer managing section discards new packets to be stored in said queue at a frequency which is higher, the higher said identified degree is.
11. The flow controlling apparatus according to claim 1, wherein said buffer managing section: is given in advance a maximum value conforming to said classes respectively corresponding to said queues; and discards new packets of said classes at a frequency lower than or equal to said maximum value.
12. The flow controlling apparatus according to claim 1, wherein said buffer managing section: is given in advance, for every flow, a number, which is the maximum of the number of new packets allowed to be discarded, the packets being in a range of transmission bandwidth to be secured; and refrains from discarding a new packet, subsequent to new packets of a maximum number, after said maximum number of new packets are discarded.
13. The flow controlling apparatus according to claim 1, further comprising a transmission bandwidth monitoring section for recognizing a maximum transmission bandwidth to be secured for each of said classes respectively corresponding to said queues, and wherein said buffer managing section: is given in advance, for every flow, a number, which is the maximum of the number of new packets allowed to be discarded, the packets being in a range of transmission bandwidth to be recognized by said transmission bandwidth monitoring section; and refrains from discarding a new packet, subsequent to new packets of a number greater than or equal to the maximum number, after the number greater than or equal to said maximum number of new packets are discarded.
14. The flow controlling apparatus according to claim 1, wherein said buffer managing section: is given a reference value conforming to a transmission bandwidth to be secured for each of possible flows and classes to which a packet to be stored in said queue identified by said queue monitoring section belongs; and refrains from discarding a new packet, subsequent to new packets having a difference and a ratio greater than or equal to said reference value, after the difference or the ratio between a sum of the numbers or amount of information in packets becomes greater than or equal to said reference value, said packets being previously discarded packets and not discarded packets.
17. A node apparatus comprising: a flow controlling apparatus comprising a rate-based congestion controlling section for adjusting a rate of a sequence of input packets to a value lower than or equal to a prescribed upper limit value for every flow where the packets individually belong, queues provided corresponding to classes to which said input packets can belong, for storing and sending said packets according to first-in first-out, a queue monitoring section for identifying, from said queues, a queue wherein an amount of information in stored packets exceeds a prescribed threshold value, and a buffer managing section for discarding new packets at a predetermined frequency in every flow to which the new packets belong, said new packets whose rate is adjusted by said rate-based congestion controlling section and being to be stored in said identified queue; and communication interfacing section for sending a packet stored in said queue, to a predetermined link or terminal.
FIGS. 4a and 4b is an operation flow chart of a band monitoring part of the first to fifth embodiments of the invention;
Keeps the pair including the new packet and passes the pair to the queue administering part 33 (indicated by symbol (1) in FIG. 4a) when the rate of the new packet included in the pair is lower than the contracted bandwidth.
Discards the pair including the new packet (indicated by symbol (2) in FIG. 4a) when, conversely, the rate of the packet exceeds the contracted bandwidth.
(a) Discards the pair being held (indicated by symbol (3) in FIG. 4b).
(b) Identifies a flow to which the new packet belongs by referring to a prescribed field of the new packet included in the pair (indicated by symbol (4) in FIG. 4b).
(c) Sets, at an initial value “0,” the values of the discarded flag fields of all the records (corresponding to all the flow identifies) corresponding to the class identifier included in the pair among the records of the discard controlling register 31Ra (indicated by symbol (5) in FIG. 4b).
(a) Identifies a flow to which the new packet belongs by referring to a prescribed field of the new packet included in the pair being held (indicated by symbol (6) in FIG. 4b).
(b) Judges whether the values of the discarded flag fields of all the records (corresponding to all the flow identifies) corresponding to the class identifier included in the pair among the records of the discard controlling register 31Ra are the initial value “0” (indicated by symbol (7) in FIG. 4b).
(c) Sets the values of the discarded flag fields of all the records at “1” only when the judgment result is true (indicated by symbol (8) in FIG. 4b).
(d) Judges whether the value of the discarded flag field of the record (hereinafter referred to as “target record”) corresponding to the flow identifier indicating the above flow and the class identifier concerned among the records of the discard controlling register 31Ra is “0” (indicated by symbol (9) in FIG. 4b).
(e) Discards the pair concerned and sets the value of the discarded flag field of the target record at “0” (indicated by symbol (10) in FIG. 4b) when the judgment result is false.
(f) Supplies the queue administering part 33 with a flow determining notice indicating the judgment result (indicated by symbol (11) in FIG. 4b) when, conversely, the judgment result is true.
Discards the pair including the new packet (indicated by symbol (2) in FIG. 4a) when, conversely, the rate of the new packet exceeds the contracted bandwidth.
(c) Sets, at an initial value “0,” the values of the number-of-discarded-packets fields of all the records (corresponding to all the flow identifies) corresponding to the class identifier c included in the pair among the records of the discard controlling register 31Rb (indicated by symbol (5) in FIG. 4b).
Upon receiving a congestion expiry notice including the identifier (for simplicity, it is assumed here to be the same as a class identifier c) of one of the queues 53-1 to 53-3 from the queue administering part 33, the band monitoring part 31 saves the values of the number-of-discarded-packets fields of all the records, corresponding to the class identifier c included in the congestion expiry notice among the records of the discard controlling register 31Rc, in the number-of-previously-discarded-packets field (indicated by symbol (a) in FIG. 4a).
The procedure of processing (indicated by symbols (1) and (2) in FIG. 4a) that is performed by the band monitoring part 31 to pass a certain new pair to the queue administering part 33 is the same as in the second embodiment, and hence will not be described.
Saves the values of the number-of-discarded-packets fields in the number-of-previously-discarded-packets field (indicated by symbol (b) in FIG. 4b).
Sets the values of the number-of-discarded-packets fields at an initial value “0”, (indicated by symbol (c) in FIG. 4b).
(b) Judges whether the values of the number-of-previously-discarded-packets field of all the records (corresponding to all the flow identifies) corresponding to the class identifier c included in the pair among the records of the discard controlling register 31Rb are the initial value “0” (indicated by symbol (d) in FIG. 4b).
(c) Sets the values of the number-of-discarded-packets fields of all the records at initial values Ncf (described above) (indicated by symbol (e) in FIG. 4b) when the judgment result is true.
(d) Copies the values of the number-of-previously-discarded-packets field of all the records to the number-of-discarded-packets fields (indicated by symbol (f) in FIG. 4b) when, conversely, the judgment result is false.
(e) Judges whether the value of the number-of-discarded-packets field of the target record corresponding to the flow identifier indicating the above flow and the class identifier concerned among the records of the discard controlling register 31Rc is “0” (indicated by symbol (g) in FIG. 4b).
(f) Discards the pair concerned and decrements the value of the number-of-discarded-packets field of the target record (indicated by symbol (h) in FIG. 4b) when the judgment result is false.
(g) Supplies the queue administering part 33 with a flow determining notice indicating the judgment result (indicated by symbol (11) in FIG. 4b) when, conversely, the judgment result is true.
(1) When the judgment result is false, discards the pair being held and sets, at an initial value “0,” the values of the number-of-discarded-packets fields of all the records corresponding to the class identifier c included in the pair among the records of the discard controlling register 31Rb (indicated by symbols (3), (4), and (A) in FIG. 4b) according to the same procedure as in the second embodiment.
(a) Acquires the congestion quotient included in the judgment result (indicated by symbol (B) in FIG. 4b).
(b) Identifies a flow to which the new packet belongs by referring to a prescribed field of the new packet included in the pair being held (indicated by symbol (6) in FIG. 4b).
When receiving a congestion expiry notice including the identifier (for simplicity, it is assumed here to be the same as a class identifier c) of one of the queues 53-1 to 53-3 from the queue administering part 33, the band monitoring part 31 saves the values of the number-of-discarded-packets fields of all the records corresponding to the class identifier c among the records of the discard controlling register 31Rc in the number-of-previously-discarded-packets field (indicated by symbol (a) in FIG. 4a).
Sets the values of the number-of-discarded-packets fields at an initial value “0” (indicated by symbols (3), (4), and (A) in FIG. 4b).
(b) Judges whether the values of the number-of-previously-discarded-packets field of all the records (corresponding to all the flow identifies) corresponding to the class identifier c included in the pair among the records of the discard controlling register 31Rc are the initial value “0” (indicated by symbol (d) in FIG. 4b).
(c) Sets the values of the number-of-discarded-packets fields of all the records at the initial values Ncf (described above) irrespective of the judgment result (indicated by symbol (e) in FIG. 4b).
(d) Adds the values of the number-of-previously-discarded-packets field to the values of the number-of-discarded-packets fields of all the records (indicated by symbol (i) in FIG. 4b) when the judgment result is false.
<- Previous Patent (Web page monitoring ...) | Next Patent (Transmission control...) ->