Method for quantifying reponsiveness of flow aggregates to packet drops in communication network

• US 20040233846A1
• Filed: 04/16/2004
• Published: 11/25/2004
• Est. Priority Date: 04/17/2003
• Status: Active Grant

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Shayman, Mark A., Khandani, Mehdi K.
• Granted Patent: US 7,391,740 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/225 Determination of shaping rate, e.g. using a moving window
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/431 using padding or de-padding
• CPC Class Codes: H04L 63/1458 Denial of Service

Abstract

In a communication network, the responsiveness of the transmission rate of data packets to packet drops is quantified for an aggregate of flows as opposed to on a per-flow basis. In an Aggregate Perturbation Method (APM), a small number of data packets is intentionally dropped from the aggregate at a switching node and a response thereto is measured. Traffic not conforming to the predetermined transmission control protocol may be discovered as a decrement in the reduction in traffic rate compared to that anticipated based on the rate of dropped packets. To prevent interference from the simultaneous application of APM at multiple switching nodes, an orthogonal drop rate signature defining the instantaneous drop rate is assigned thereto. The orthogonal drop rate signature is based on the code division multiple access (CDMA) coding of data, and for that reason, APM with the application of orthogonal drop rate signatures is termed CDMA-based APM, or CAPM. APM or CAPM may be utilized as a component in fair congestion control or in mitigating distributed denial of service (DDoS) attacks of the Internet.

Claims

1. A method for determining the responsiveness of a data transmission rate of data packets to packet drops in a communication network, each of the data packets having appended to data thereof a packet designator including an address of a source node and an address of a destination node, each of the data packets being assigned to a corresponding one of a plurality of flows such that the packet designators of the data packets in each of the plurality of flows have equivalent corresponding source node addresses and equivalent corresponding destination node addresses, the communication network including a plurality of switching nodes having a set of the plurality of flows respectively traversing therethrough, the method comprising the steps of:

selecting at each of the plurality of switching nodes at least one aggregating property;

forming a respective aggregate from the set of flows at each of the plurality of switching nodes in accordance with a corresponding one of said at least one aggregating property;

setting a packet drop rate for each of said respective aggregates;

dropping from each of said respective aggregates a number of packets according to said packet drop rate;

measuring a perturbed packet transmission rate for each of said respective aggregates subsequent to said packet dropping step; and

estimating the responsiveness to packet drops of each of said respective aggregates from said perturbed packet transmission rate.

2. The method for determining the responsiveness to packet drops as recited in claim 1, whereby said packet drop rate setting step further includes the steps of:

assigning to each of the plurality of switching nodes a corresponding drop rate signature for specifying an instantaneous drop rate, said drop rate signature at each of the plurality of switching nodes being orthogonal to said drop rate signature of all other ones of the plurality of switching nodes when each of said plurality of drop rate signatures are compensated for a DC offset; and

setting said packet drop rate to said instantaneous drop rate.

3. The method for determining the responsiveness to packet drops as recited in claim 2, whereby said responsiveness estimation step includes the steps of:

providing an output filter at each of the plurality of switching nodes, said output filter responsive only to said drop rate signature assigned thereto; and

applying said output filter to said perturbed packet transmission rate corresponding to each of said respective aggregates, said output filter providing at an output thereof said estimation of the responsiveness to packet drops corresponding to each of said respective aggregates.

4. The method for determining the responsiveness to packet drops as recited in claim 3, whereby said responsiveness estimation step further includes the step of compensating said drop rate signature for said DC offset prior to said output filter applying step.

5. The method for determining the responsiveness to packet drops as recited in claim 4, whereby said drop rate signature is a temporal waveform having a sinusoidal profile.

6. The method for determining the responsiveness to packet drops as recited in claim 4, whereby said drop rate signature is a temporal waveform having a substantially rectangular profile.

7. The method for determining the responsiveness to packet drops as recited in claim 6, whereby said rectangular temporal waveform is controlled by a pattern of binary-valued bits by which a bit thereof in a first bit state sets said instantaneous drop rate to a predetermined drop rate and a bit thereof in a second bit state sets said instantaneous drop rate to zero.

8. The method for determining the responsiveness to packet drops as recited in claim 7, whereby said pattern of binary-valued is selected by a code division multiple access code selection algorithm.

9. The method for determining the responsiveness to packet drops as recited in claim 1, whereby said responsiveness estimating step includes the steps of:

maintaining a running time average of a total packet transmission rate corresponding to each said respective aggregates as a corresponding nominal packet transmission rate; and

subtracting said nominal packet transmission rate from said corresponding perturbed packet transmission rate.

10. The method for determining the responsiveness to packet drops as recited in claim 1, further including the step of providing the packet designator with a source port number and a destination port number.

11. The method for determining the responsiveness to packet drops as recited in claim 1, whereby said aggregating property is selected from the group consisting of a source port number, a destination port number and a network application as determined from said source port number or said destination port number.

12. A method for determining an amount of traffic in a communication network non-conforming to a predetermined transmission control protocol, the traffic being transported in flows of data packets, each of the data packets having appended to data thereof a packet designator including an address of a source node and an address of a destination node, each of the data packets being assigned to a corresponding one of a plurality of flows such that the packet designators of the data packets in each of the plurality of flows have equivalent corresponding source node addresses and equivalent corresponding destination node addresses, the communication network including a plurality of switching nodes having a set of the plurality of flows respectively traversing therethrough, the method comprising the steps of:

selecting at each of the plurality of switching nodes at least one aggregating property;

forming a respective aggregate from the set of flows at each of the plurality of switching nodes in accordance with a corresponding one of said at least one aggregating property;

setting a packet drop rate for each of said respective aggregates;

dropping from each of said respective aggregates a number of packets according to said packet drop rate;

measuring a perturbed packet transmission rate for each of said respective aggregates subsequent to said packet dropping step;

estimating a responsiveness coefficient of each of said respective aggregates from said perturbed packet transmission rate;

maintaining an average of said responsiveness coefficient for each of said respective aggregates as a nominal responsiveness coefficient; and

calculating the amount of non-conforming traffic as a ratio of said responsiveness coefficient to said nominal responsiveness coefficient.

13. The method for determining an amount of non-conforming traffic as recited in claim 12, whereby said packet drop rate setting step further includes the steps of:

assigning to each of the plurality of switching nodes a corresponding drop rate signature for specifying an instantaneous drop rate, said drop rate signature at each of the plurality of switching nodes being orthogonal to said drop rate signature of all other ones of the plurality of switching nodes when each of said plurality of drop rate signatures are compensated for a DC offset; and

setting said packet drop rate to said instantaneous drop rate.

14. The method for determining an amount of non-conforming traffic as recited in claim 13, whereby said responsiveness coefficient estimation step includes the steps of:

providing an output filter at each of the plurality of switching nodes, said output filter responsive only to said drop rate signature assigned thereto; and

applying said output filter to said perturbed packet transmission rate corresponding to each of said respective aggregates, said output filter providing at an output thereof said estimation of said responsiveness coefficient corresponding to each of said respective aggregates.

15. The method for determining an amount of non-conforming traffic as recited in claim 14, whereby said responsiveness coefficient estimation step further includes the step of compensating said drop rate signature for said DC offset prior to said output filter applying step.

16. The method for determining an amount of non-conforming traffic as recited in claim 15, whereby said drop rate signature is a temporal waveform having a sinusoidal profile.

17. The method for determining an amount of non-conforming traffic as recited in claim 15, whereby said drop rate signature is a temporal waveform having a substantially rectangular profile.

18. The method for determining an amount of non-conforming traffic as recited in claim 17, whereby said rectangular temporal waveform is controlled by a pattern of binary-valued bits by which a bit thereof in a first bit state sets said instantaneous drop rate to a predetermined drop rate and a bit thereof in a second bit state sets said instantaneous drop rate to zero.

19. The method for determining an amount of non-conforming traffic as recited in claim 18, whereby said pattern of binary-valued is selected by a code division multiple access code selection algorithm.

20. The method for determining an amount of non-conforming traffic as recited in claim 12, further including the step of providing the packet designator with a source port number and a destination port number.

21. The method for determining an amount of non-conforming traffic as recited in claim 12, whereby said aggregating property is selected from the group consisting of a source port number, a destination port number and a network application as determined from said source port number or said destination port number.