Packet network

• US 6,538,989 B1
• Filed: 11/02/1998
• Issued: 03/25/2003
• Est. Priority Date: 09/09/1997
• Status: Expired due to Term

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Carter, Simon F, Hodgkinson, Terence G, OʼNeill, Alan W
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/180,102
• Time in Patent Office: 1,604 Days
• Field of Search: 370/389, 370/229, 370/395.2, 370/399, 370/395.21, 370/395, 370/31, 370/395.4, 370/394.41, 370/395.42, 370/395.61, 370/395.65, 370/230, 370/230.1, 370/232, 370/233, 370/234, 370/235, 370/235.1, 370/237, 370/351, 370/352, 370/413-419, 370/411, 370/465, 370/469, 370/470, 370/471, 370/472, 370/474, 370/476, 370/468, 370/477
• US Class Current: 370/229
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/525 by redistribution of residual bandwidth
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/627 policing
• CPC Class Codes: H04L 47/6285 Provisions for avoiding starvation of low priority queues

Abstract

A new approach to providing both bounded-delay and best-effort operation in a packet network node is described. The bounded-delay mode is capable of providing a firm end-to-end delay bound, but in contrast to the combination of RSVP and Guaranteed service proposed within the IETF, it does this with minimal complexity.

Network nodes are provided with dual packet buffers associated with bounded delay and best effort classes of service respectively. Appropriate dimensioning, if necessary enforced through CAC methods, ensure that packets admitted to the bounded delay buffer are provided the firm delay bound. CAC methods are described which are applicable for packet flows as small as a single packet.

A means is also offered for removing the traditional network signalling phase.

A related architecture for use with hosts is also described.

Claims

1. A packet network element comprising:

at least one input for receiving flow based packets;

at least one output of predetermined bandwidth;

wherein a received packet is associable with a first or second class of service;

means for directing each received packet on the basis of its class to a first or a second corresponding packet buffer,

said first packet buffer being allocated a predetermined portion of the output bandwidth;

said second packet buffer being allocated the remaining portion of the output bandwidth;

means for directing packets from the first and second packet buffers to an output;

first class flow bandwidth requirement determination means arranged in operation, selectively for said first class flows, to determine bandwidth requirements associated with first class flows; and

first class flow buffer admission means arranged in operation, selectively for said first class flows, to allow admission of the first class flow packets to the first packet buffer if said associated bandwidth requirement can be met.

2. An element as claimed in claim 1 wherein said first class flow buffer admission means is operable to apply a peak rate test to determine a peak rate bandwidth requirement, allowing admission to the first buffer if the currently unused portion of said predetermined portion of the output bandwidth is able to meet said peak rate bandwidth requirement.

3. An element as claimed in claim 2 wherein said means for allowing admission is operable to apply said peak rate test and to apply a buffer-fill test, allowing admission if said first packet buffer has sufficient space to accept another flow.

4. An element as claimed in claim 3 wherein:

said admission allowing means is arranged to allow admission of the first class flow packets to the first packet buffer only if;

the number of flows the first packet buffer is sized to accommodate minus the number of flows currently accommodated is at least unity; and

the free portion of the output bandwidth allocated to the first packet buffer minus the peak rate bandwidth requirement is greater than or equal to zero.

5. An element as claimed in claim 4 wherein said admission allowing means is operable to increase the size of said free portion on the cessation of a flow, said increase taking place after the lapse of a time period substantially equal to the packet-size divided by the peak rate associated with the flow.

6. An element as claimed in claim 1, further comprising means to admit first class flow packets to the second packet buffer if they were refused admission to the first packet buffer.

7. An element as claimed in claim 2 wherein said first class flow bandwidth requirement determination means is arranged to read a peak rate flow bandwidth requirement information portion from said received packet.

8. An element as claimed in claim 1 wherein said predetermined portion of the output bandwidth allocated to the first packet buffer may be dynamically changed.

9. An element as claimed in claim 2 wherein said peak rate bandwidth requirement determining means is arranged to determine particular peak rate flow bandwidth requirement values for respective single packet flows.

10. An apparatus according to claim 1 further comprising class determining means for determining whether said received packet is associated with a first or second class of service.

11. An element as claimed in claim 10 characterised in that the class determining means is arranged to determine whether the packets are associated with one of a bounded delay or best effort class of service.

12. An element as claimed in claim 10 wherein said class determining means is arranged to read a class identifying portion from said received packet.

13. A method of controlling flow based packets in a packet network element comprising:

receiving flow based packets;

wherein a received packet is associable with a first or second class of service;

directing each received packet on the basis of its associated class to a first or a second corresponding packet buffer,

said first packet buffer being allocated a predetermined portion of a predetermined output bandwidth;

said second packet buffer being allocated the remaining portion of the output bandwidth; and

directing packets from the first and second packet buffers to an output;

selectively for said first class flows;

determining bandwidth requirements associated with said first class flows; and

admitting said first class flow packets to the first packet buffer if said associated bandwidth requirement can be met.

14. A host element for use in association with a packet network comprising:

means for generating packet based flows and for associating each flow with a respective first or second class of service;

a first packet buffer, having a first packet buffer size, arranged to receive packets associated with the first class of service;

means for controlling the first packet buffer size;

a second packet buffer arranged to receive packets associated with the second class of service; and

means for directing packets from the first and second packet buffers to an output arranged to ensure that the first class packet flow rate does not exceed a selected peak rate bandwidth.

15. A host element as claimed in claim 14 wherein means are provided for writing the first or second class of service into a class identifying portion of said packets.

16. A host element as claimed in claim 15 wherein means are provided for writing a peak rate flow bandwidth requirement information into a peak rate flow rate bandwidth requirement portion of said packets.

17. A host as claimed in claim 16 characterised in that said means for generating and associating is arranged to generate packets associated with a selected one of a bounded delay or best effort class of service.

18. A method of generating packet based flows comprising:

generating packet based flows and associating each flow with a respective selected associated first or second class of service;

sending packets of first class flows to a first packet buffer, having a first packet buffer size, arranged to receive packets associated with the first class of service;

controlling the first packet buffer size;

sending packets of second class flows to a second packet buffer arranged to receive packets associated with the second class of service; and

directing packets from the first and second packet buffers to an output arranged to ensure that the first class packet flow rate does not exceed a selected peak rate bandwidth.

19. A packet network comprising one or more packet network elements, each packet network element comprising:

at least one input for receiving flow based packets;

at least one output of predetermined bandwidth;

wherein a received packet is associable with a first or second class of service;

means for directing each received packet on the basis of its class to a first or a second corresponding packet buffer,

said first packet buffer being allocated a predetermined portion of the output bandwidth;

said second packet buffer being allocated the remaining portion of the output bandwidth;

means for directing packets from the first and second packet buffers to an output;

first class flow bandwidth requirement determination means arranged in operation, selectively for said first class flows, to determine bandwidth requirements associated with first class flows; and

first class flow buffer admission means arranged in operation, selectively for said first class flows, to allow admission of the first class flow packets to the first packet buffer if said associated bandwidth requirement can be met.

20. A network as claimed in claim 19 further comprising one or more host elements for use in association with a packet network, each said host element comprising:

means for generating packet based flows and for associating each flow with a respective first or second class of service;

a first packet buffer arranged to receive packets associated with the first class of service;

means for controlling the first packet buffer size;

a second packet buffer arranged to receive packets associated with the second class of service; and

means for directing packets from the first and second packet buffers to an output arranged to ensure that the first class packet flow rate does not exceed a selected peak rate bandwidth.

21. A packet network element comprising:

at least one input for receiving flow based packets;

at least one output of predetermined bandwidth;

first means for determining whether a received packet is associated with a first or second class of service;

means for directing each received packet on the basis of its associated class to a first or a second corresponding packet buffer,

said first packet buffer being of predetermined size to accommodate a predetermined number of flows and being allocated a predetermined portion of the output bandwidth, a currently unused portion thereof varying with the number of flows accommnodated,

said second packet buffer being allocated a remaining portion of the output bandwidth;

second means for determining a peak rate flow bandwidth requirement associated with a flow;

first class flow buffer admission means for allowing admission of the first class flow packets to the first packet buffer if the first packet buffer is able to accept another flow and if the currently unused portion is able to meet the associated peak rate flow bandwidth requirements; and

means for directing packets from the first and second packet buffers to an output.