Compact segmentation of variable-size packet streams

• US 6,888,848 B2
• Filed: 12/14/2000
• Issued: 05/03/2005
• Est. Priority Date: 12/14/2000
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Munter, Ernst A., Beshai, Maged E.
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/735,471
• Publication Number:
  US 20040213291A1
• Time in Patent Office: 1,601 Days
• Field of Search: 370/389, 370/393, 370/400, 370/255, 370/351, 370/464, 370/576, 370/473, 370/412, 370/395.1, 370/235, 370/474, 370/359, 373/225
• US Class Current: 370/474
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/36 by determining packet size, e.g. maximum transfer unit [MTU]
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 47/431 using padding or de-padding
• CPC Class Codes: H04L 49/3072 Packet splitting
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9021 Plurality of buffers per packet
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

A method is described for segmenting a data stream comprising variable-size packets, a data stream being defined by its source node, sink node, assigned network route, and other attributes. The segments are of equal size and the method concatenates the packets in successive segments in a manner that attempts to minimize segmentation waste without undue delay. The method facilitates the construction of efficient networks that scale to very high capacities while respecting service-quality specifications. Apparatus for implementing the method are also described.

Claims

1. A method of segmenting variable-size packets, each packet being associated with one of a plurality of defined data streams, the method comprising steps of:

concatenating packets of each data stream, from among said plurality of data streams, into concatenated packets; and

dividing each of said concatenated packets into equal-size segments,

wherein said steps of concatenating and dividing are constrained by an adaptive delay threshold;

and wherein the adaptive-delay threshold is determined by an allocated transfer rate to said each data stream;

and wherein the adaptive delay threshold is governed by a transfer rate controller.

2. The method as claimed in claim 1 wherein the adaptive delay threshold is data-stream dependent.

3. In a network comprising source nodes and sink nodes, the method as claimed in claim 1 wherein said step of concatenating is applied at the ingress port of a source node.

4. In a network comprising source nodes and sink nodes, the method as claimed in claim 1 wherein said step of concatenating is applied at the output port of a source node.

5. In a switching node receiving packets from a plurality of incoming channels, a method of two-phase packet segmentation comprising:

segmenting individual packets in a first phase into first-phase segments using a plurality of first-phase segmentation circuits;

segmenting an aggregate of packets in a second phase into second-phase segments using a plurality of second-phase segmentation circuits;

switching an output of said first-phase segmentation circuits to said second-phase segmentation circuits under control of a routing algorithm;

wherein said routing algorithm selects routes from an incoming channel to a sink node using a method of maximum aggregation probability.

6. The method as claimed in claim 5 wherein said first-phase segments are of equal size and said second-phase segments are of equal size and the size of a second-phase segment is an integer multiple of the size of a first-phase segment.

7. The method as claimed in claim 5 wherein a first-phase segmentation circuit is allocated to an incoming channel.

8. A data structure to enable merging equal-size null-padded data segments into new equal-size data segments having reduced null-padding, the data segments belonging to K>

1 data streams, the data structure comprising;

(i) An array “

A”

of fractional segments having K entries, each entry dedicated to a data stream;

(ii) An array “

B”

of complete segments having K1>

K entries; and

(iii) a control matrix “

C”

having K records, each record dedicated to a data stream and having four fields to indicate, for a corresponding stream, the stream'"'"'s delay threshold, the stream'"'"'s current delay, the fill of a respective fractional-segment in array “

A”

, and the address of a complete segment in array “

B”

.

9. The data structure as claimed in claim 8 wherein the size of each of said new equal-size data segments is an integer-multiple of the size of each of said equal-size null-padded data segments.

10. The data structure as claimed in claim 8 wherein array “

A”

is directly indexed by a stream identifier.

11. The data structure as claimed in claim 8 wherein array “

A”

is replaced by a pointer array and a segment-Storage array.

12. In conjunction with the data structure as claimed in claim 8 a method for data segmentation including steps of

(a) Receiving a plain segment of a stream k, 0≦

k<

K;

(b) Merging said plain segment with data content of array “

A”

at storage position k;

(c) Appending a complete segment resulting from said merging to a queue associated with data stream k in array “

B”

; and

(d) Overwriting a fractional segment resulting from said merging in memory “

A”

at position k.

13. The method as claimed in claim 12 wherein a plurality of plain segments are processed concurrently.

14. The method as claimed in claim 12 wherein pointers to transferred segments are placed in a transfer queue.

15. In conjunction with the data structure as claimed in claim 8 a method of controlling data segments transfer, the method including steps of:

(e) Receiving from a transfer rate controller a prompt to transfer a data segment of a stream k, 0≦

k<

K;

(f) Transferring a complete segment belonging to data stream k in array “

B”

if said complete segment exists;

else

(g) Transferring a fractional segment belonging to data stream k in array “

A”

if said fractional Segment exists and has already been prompted by said rate controller a predefined number of times;

else

(h) Return a no-action indication to rate controller.

16. A compact-segmentation apparatus operable to segment variable-size packets into compact fixed-size segments, the apparatus comprising

(a) a packet segmentation circuit;

(b) an enqueueing controller;

(c) a principal data memory;

(d) an auxiliary data memory;

(e) a control memory

(f) a dequeueing controller; and

(g) a transfer-rate controller;

wherein

said packet segmentation circuit receives variable-size packets and segments each of said variable-size packets into plain segments,

said packet segmentation circuit identifies a data stream associated with each one of said variable-size packets,

said enqueueing controller communicates with said control memory, said principal data memory, and said auxiliary data memory, and concatenates said plain segments of a data stream with previously-received segments of same data stream,

said transfer-rate controller selects a selected data stream, and

said dequeueiflg controller selects data segments, belonging to said selected data stream, from waiting data segments in said principal data memory and said auxiliary data memory for transfer downstream.

17. The apparatus as claimed in claim 16 wherein the rate controller is driven by a service-quality controller.

18. The apparatus as claimed in claim 17 wherein the service-quality controller is source-node driven.

19. The apparatus as claimed in claim 17 wherein the service-quality controller is driven by a source node controller.

20. The apparatus as claimed in claim 17 wherein a segment is ready for transfer by the dequeueing controller if it is a complete segment waiting in the principal data memory or a fractional segment waiting in the auxiliary data memory and has already been prompted by the rate controller a predefined number of times.

21. The apparatus as claimed in claim 16 wherein the principal data memory is structured as a multi-head interleaved linked list.

22. A circuit for fast concatenation of a first picket of a known length and a second packet of a known length into a complete segment of n predefined length, the circuit comprising a shift connector, a memory array, and a register array, the length of said first packet being smeller than said predefined length and the length of said second packet being less than said predefined length, wherein

said first packet is copied onto said register array, said shift connector performs a concatenation process that concatenates said second packet with said first packet onto said register array placing any remainder resulting from said concatenation process in said memory array.

23. The circuit as claimed in claim 22 wherein the shift connector is constructed from arrays of shift connectors of a smaller size.

24. The circuit as claimed in claim 23 wherein each array comprises identical shift connectors and the sizes of shift connectors in different arrays are different.