Technique for bandwidth sharing in internet and other router networks without per flow state record keeping
View Patent ↗In a network of interconnected edge and core routers, where packet data flows are received at edge routers and then transmitted toward intended destinations via a path through one or more core routers, fair bandwidth sharing is achieved without per-flow state monitoring in the interior routers. Each edge router is arranged to divide each input data flow into a set of layers each having an associated level, based on rate. The division process is done without reference to the content of the flow, and can use layers of equal or unequal size. The packets in a flow are marked at an edge router with their layer level, in a globally consistent manner. Each core router maintains a layer level threshold, based upon buffer management conditions, and drops layers whose level exceeds the threshold. During congestion, the level threshold is decreased; when congestion clears, the level threshold is increased.
1. In a network of interconnected edge routers and core routers, a method of processing packets in a plurality of packet data flows received at said edge routers for transmission toward intended destinations via a path through one or more of said core routers, said method comprising the steps of
assigning a level indicator to packets in each of said packet data flows, each said level indicator representing one of a plurality of layers that cumulatively represent a rate of said packet data flow of which said packets are a part, said packets being randomly assigned said level indicator with a probability determined by said rate of said layers;
establishing a threshold level in each of said core routers, based upon network congestion conditions, and
dropping in said core routers, packets whose level indicator exceeds said threshold level.
2. The method of claim 1 , wherein said threshold level is decreased when network congestion occurs and increased when network congestion clears.
3. The method of claim 1 , wherein said layers are unequal in size.
4. The method of claim 3 , wherein said layers have sizes arranged in an exponential order.
5. The method of claim 1 , wherein said assigning step includes distributing packets that are a part of a particular packet data flow among the layers that cumulatively represent the rate of said packet data flow, such that the number of packets assigned to a given layer is proportional to the size of that layer.
6. The method of claim 1 , said layers being assigned from bottom up with smaller level indicators assigned before said layers with large values.
7. The method of claim 1 , wherein each of said packet data flows requires the same grade of service at each router in said path.
8. The method of claim 1 , wherein said threshold is initially set to a maximum value of said layers.
9. In a network of interconnected edge routers and core routers, a method of processing packets in a plurality of packet data flows received at said edge routers for transmission toward intended destinations via a path through one or more of said core routers, said method comprising the steps of
determining a rate at which each of said packet data flows are received at said edge routers;
responsive to said determining step, establishing a plurality of layers, such that (a) the size of each layer corresponds to a portion of a maximum rate at which said each packet data flow is received at said edge routers, and (b) the total size of said layers cumulatively represents said maximum rate of said each packet data flow,
assigning packets in said each packet data flow to one of said layers such that an average number of packets assigned to each layer is proportional to the relative size of that layer as compared to the cumulative size of all of said layers;
associating a level indicator with each of said layers, said packets being randomly assigned said level indicator based on a probabilistic level assignment scheme;
establishing a threshold level in each of said core routers, based upon network congestion conditions, and
dropping in said core routers, packets whose level indicator exceeds said threshold level.
10. The method of claim 9 , wherein said threshold is initially set to a maximum value of said layers.
11. The method of claim 9 , wherein said rate at which each of said packet data flows are received at said edge routers is calculated as
r i new =(1 −e− T i k /K ) l i k / T i k +e− ( T i k /K ) r i old
where T i k = T i k − T i k−1 and K is a constant.
12. The method of claim 9 , wherein said establishing said plurality of layers is done without reference to the content of said packet data flows.
13. In a network of interconnected edge routers and core routers, a method of processing packets in a plurality of packet data flows received at said edge routers for transmission toward intended destinations via a path through one or more of said core routers, said method comprising the steps of
determining a rate at which each of said packet data flows are received at said edge routers;
responsive to said determining step, establishing a plurality of layers each having an associated level value, such that (a) the size of each layer corresponds to a portion of a maximum rate at which said each packet data flow is received at said edge routers, and (b) the total size of said layers cumulatively represents said maximum rate of said each packet data flow,
assigning packets in said each packet data flow to one of said layers such that an average number of packets assigned to each layer is proportional to a relative size of that layer as compared to a cumulative size of all of said layers; and
transmitting each packet toward its destination together with information representing the level value associated with the layer to which said each packet is assigned.
14. The method of claim 13 , wherein said rate at which each of said packet data flows are received at said edge routers is calculated as
r i new =(1 −e− T i k /K ) l i k / T i k +e− ( T i k /K ) r i old
where T i k = T i k − T i k−1 and K is a constant.
15. In a network of interconnected edge routers and core routers, a method of processing packets in a plurality of packet data flows received at said core routers from one of said edge routers,
establishing a threshold level in each of said core routers, based upon network congestion conditions,
examining a threshold value associated with each packet received in said core router, and
dropping in said core routers, packets whose level indicator exceeds said threshold level,
wherein said threshold value is determined in said edge router by
determining a rate at which each of said packet data flows are received at said edge routers;
responsive to said determining step, establishing a plurality of layers, such that (a) the size of each layer corresponds to a portion of a maximum rate at which said each packet data flow is received at said edge routers, and (b) the total size of said layers cumulatively represents said maximum rate of said each packet data flow, and
assigning packets in said each packet data flow to one of said layers such that an average number of packets assigned to each layer is proportional to the relative size of that layer as compared to a cumulative size of all of said layers.
16. The method of claim 15 , wherein said threshold is initially set to a maximum value of said layers.
17. The method of claim 15 , wherein said rate at which each of said packet data flows are received at said edge routers is calculated as
r i new =(1 −e− T i k /K ) l i k / T i k +e− ( T i k /K ) r i old
where T i k = T i k − T i k−1 and K is a constant.