Data stream shaper

• US 6,097,701 A
• Filed: 12/10/1997
• Issued: 08/01/2000
• Est. Priority Date: 12/13/1996
• Status: Expired due to Term

• Current Assignee: Sound View Innovations, LLC (Sound View Innovation Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Stock, Thomas, Grunenfelder, Reto
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): TRINH, DUNG N
• Application Number:
  US08/987,897
• Time in Patent Office: 965 Days
• Field of Search: 370/395, 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/236, 370/237, 370/238, 370/239, 370/240
• US Class Current: 370/235
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 2012/568 Load balancing, smoothing or shaping
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A shaper (1) in a stream of data packets provides for compliance with the agreements about the packet traffic of each virtual connection. It contains means (11) for the intermediate storage and read-out of data packets and for extracting the packet clock, furthermore a control (12) which reads the packets of the different connections into the data stream at the right time. The selection of the data packet takes place on the basis of a rank which is established for each data packet located at the front of the virtual waiting line of the individual connection. With each packet clock the rank is incremented in accordance with the agreed bandwidth for this connection; thus, for each clock a new calculation for the highest two connections for which a data packet advances again to the head of the virtual waiting line, is sufficient. Two processing units (21, 24) are provided. Reference magnitudes (Bk) of individual connections are calculated in a single first processing unit (21); in a second processing unit (24) which is available once for each connection, they are also weighted, updated and provided with the priority (PRIO).

Claims

1. A shaper for a stream of data packets, particularly an ATM traffic stream, with means (1, 12) for the intermediate storage and read-out of data packets from individual connections and the extraction of the packet clock, characterized by an evaluation unit (20) which determines the instant of the last read-out of a data packet during the packet clock period for each connection based on the current time, the agreed traffic parameters (tk, Tk) and the priority (PRIO) of a rank (Rank), wherein the rank comprises a mode class which determines the priority of the packet departure and a weight which is decisive for the sequence within the same mode class, and wherein the rank is decisive for the selection of the data packets to be read out next.

2. A shaper for a stream of data packets, particularly an ATM traffic stream, with means (1, 12) for the intermediate storage and read-out of data packets from individual connections and the extraction of the packet clock, characterized by an evaluation unit (20) which determines the instant of the last read-out of a data packet during the packet clock period for each connection based on the current time, the agreed traffic parameters (tk, Tk) and the priority (PRIO) of a rank (Rank) wherein the rank is decisive for the selection of the data packets to be read out next, wherein the shaper is further characterized by a means (25) connected downstream of the evaluation unit (20) for storing the determined ranks, and an evaluation and selection unit (12) which accesses the contents of the ranks, and in turn controls the read-out of the data packets from the means (11) for the intermediate storage of the data packets'"'"' individual connection.

3. A shaper as claimed in claim 2, characterized by a separate memory (22, 23) placed before the evaluation unit (20) for each type of agreed connection parameters (tk, Tk) whose contents are read as needed by the evaluation unit (20).

4. A shaper as claimed in claim 3, characterized by an evaluation unit (20) in the form of a first processing unit (21) for determining reference magnitudes (Bk) from the traffic parameters (tk, Tk) and from events (E1, E2) in traffic movements, and per connection of a second processing unit (24) connected downstream for the individual updating of the rank as a function of time and a part of the traffic parameter (Tk).

5. A shaper as claimed in claim 4, characterized in that the second processing unit (24, 40) contains a counter (47), which is set by the reference magnitude obtained from the first processing unit (21), which counts packet clocks in reference to a traffic parameter (Tk), and whose status together with the priority (PRIO) provides the rank (Rank).

6. A shaper as claimed in claim 2, characterized by an evaluation unit (20) in the form of a first processing unit (21) for determining reference magnitudes (Bk) from the traffic parameters (tk, Tk) and from events (E1, E2) in traffic movements, and per connection of a second processing unit (24) connected downstream for the individual updating of the rank as a function of time and a part of the traffic parameter (Tk).

7. A method of shaping a stream of data packets, particularly from an ATM traffic stream, while taking a priority into consideration and complying with agreed traffic parameters for each connection, where arriving data packets of individual connections are inserted into a waiting line and the packet clock is determined, characterized by the following process steps during a packet clock period:

Determining for each connection a reference magnitude (Bk) from the traffic parameters (tk, Tk) and the time (t) elapsed since the last packet departure;

Determining for each connection a rank (Rank) based on the priority (PRIO) and the reference magnitude (Bk);

Determining the connection with the highest rank, and

Read-out of the data packet of the determined connection from the waiting line.

8. A method as claimed in claim 7, characterized in that determining the connection with the highest rank encompasses the following steps:

Storing the newly established rank;

Searching the stored ranks for the highest ranked memory input respectively if several highest ranked inputs are stored, the next memory input, and determining the connection which belongs to the selected memory input.

9. A method as claimed in claim 8, characterized in that the reference magnitude (Bi, Bj) is calculated anew for the connection of the last departed data packet and/or the arriving data packet which goes directly to the head of the waiting line, and that the reference magnitudes (Bk) of all other connections are updated.

10. A method as claimed in claim 9, characterized by the following steps for determining the reference magnitudes (Bi, Bj):

Determining the connection i of a departing data packet;

Calculating a reference magnitude (Bi) for the departure time of a next data packet of connection i;

Determining a connection j of an arriving data packet, which advances immediately to the head position in the waiting line;

Calculating a reference magnitude (Bj) for the departure time of a next data packet of connection j, and

Updating the reference magnitudes (Bk) of all other connections by means of an increment weighted with a traffic parameter.

11. A method as claimed in claim 7, characterized in that the reference magnitude (Bi, Bj) is calculated anew for the connection of the last departed data packet and/or the arriving data packet which goes directly to the head of the waiting line, and that the reference magnitudes (Bk) of all other connections are updated.

12. A shaper for a stream of data packets, particularly an ATM traffic stream, with means (1, 12) for the intermediate storage and read-out of data packets from individual connections and the extraction of the packet clock, characterized by an evaluation unit (20) which determines the instant of the last read-out of a data packet during the packet clock period for each connection based on the current time, the agreed traffic parameters (tk, Tk) and the priority (PRIO) of a rank (Rank) wherein the rank is decisive for the selection of the data packets to be read out next, wherein the shaper is further characterized by a separate memory (22, 23) placed before the evaluation unit (20) for each type of agreed connection parameters (tk, Tk) whose contents are read as needed by the evaluation unit (20).