Method and a device for resequencing

• US 5,461,614 A
• Filed: 06/15/1994
• Issued: 10/24/1995
• Est. Priority Date: 06/15/1993
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Lindholm, Lars A. a.
• Primary Examiner(s): Hsu, Alpus
• Application Number:
  US08/260,926
• Time in Patent Office: 496 Days
• Field of Search: 370/13, 370/54, 370/58.1, 370/58.2, 370/58.3, 370/60, 370/60.1, 370/61, 370/94.1
• US Class Current: 370/394
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers

Abstract

In a data packet network, packets are transferred from input ports to output ports. Packet transfers can require time periods of different lengths because data packets, as they are transported in the network, pass through units where they are subjected to processing. In each input port, a list is established of current combinations of source addresses and destination addresses for the data packets that have arrived at the input port. The list includes the current sequential number for data packets having this combination. This list is restricted or limited so that it includes only a small number of records. When a data packet is received by an input port, and the source address and destination address of the dam packet are not already in the list, the record in the list that has been inactive for the longest time period is overwritten, thereby erasing the corresponding sequential number. When a message having the same source address and destination address arrives again, the sequential number is restarted. At the same time, a flag is set in the packet, indicating the restart. Further, those records that have been inactive during some predetermined time period are removed from the list. Also, in the output port there is a similar list that is reduced to avoid long search times. If a record in the list in an output port has been inactive for a sufficiently long time, it can be removed from the list, since then the corresponding record is already removed in the list in the input port.

Claims

1. A method of transferring data packets from input ports to output ports in a network, in which data packet transfers can require time periods of varying lengths and there is a first category comprising all input ports and a second category comprising all output ports comprising the steps of:

when a data packet arrives at an input port, inserting a sequential number into the arrived data packet, the sequential number indicating a sequential position of the arrived data packet;

feeding data packets in a correct sequential order from an output port based on the sequential number of each arrived data packet that has been transferred to the output port;

in at least one of the categories of ports, establishing a list comprising records, wherein each record comprises an address associated with a respective arrived data packet and a current sequential number associated with a next data packet that has the same address and is next to arrive at the input port or is to be transferred to the output port, respectively;

the records comprise different addresses and only addresses associated with data packets that have latest arrived at the input port or have been latest transferred to the output port, respectively; and

performing at least one of the following steps;

where a time period for transferring a data packet through the network from an input port to an output port is always smaller than a predetermined time period, restricting a list in an output port to a limited number of records, the limited number of records being larger than a smallest number that allows, considering the predetermined time period, a resequencing of data packets transferred to the output port;

removing a record from the list in the output port when no data packet associated with the address of the record has arrived at an input port during the predetermined time period.

2. The method of claim 1, wherein a list in an input port contains records comprising a destination address, the destination address being included in the data packets themselves or an address of an output port in the network to which the data packets are to be transferred, and a list in an output port contains records comprising a source address, the source address being included in the data packets themselves or an address of an input port in the network from which the data packets have been transferred.

3. The method of claim 2, wherein if the step of removing a record is performed, the number of records in a list in an output port is equal to or larger than a ratio of a sum of a maximum time period for transferring a data packet in the network from an input port to an output port and a time period after which a record in an input port is removed and a minimum time period during which an output port can receive data packets transferred through the network.

4. The method of claim 2, wherein the predetermined time period is equal to or larger than a sum of a maximum time period for transferring a data packet in the network from an input port to an output port and a time period after which a record in an input port is removed.

5. The method of claim 2, wherein in each record in a list in an input port of the network, information is inserted that represents a time when a data packet latest arrived at the input port associated with the address indicated in the respective record.

6. The method of claim 2, wherein when a data packet has been transferred in the network to an output port and the dam packet has a sequential number following a current sequential number in the list'"'"'s record comprising the address with which the data packet is associated, the data packet is stored to be fed later from the output port.

7. The method of claim 6, wherein at substantially the same time as a data packet having a sequential number following the current sequential number is transferred, information is stored relating to a time when the data packet that was received in the output port is stored.

8. The method of claim 6, wherein when a data packet has been stored for at least the predetermined time period, the data packet is fed from the output port.

9. The method of claim 8, wherein when a stored data packet is fed from an output port, the current sequential number in the list'"'"'s record comprising the address with which this data packet is associated is set equal to a sequential number that is next after the sequential number of the stored data packet.

10. A method of transferring data packets from input ports to output ports in a network, in which data packet transfers can require time periods of varying lengths and there is a first category comprising all input ports and a second category comprising all output ports comprising the steps of:

when a data packet arrives at an input port, inserting a sequential number into the arrived data packet, the sequential number indicating a sequential position of the arrived data packet;

feeding data packets in a correct sequential order from an output port based on the sequential number of each arrived data packet that has been transferred to the output port;

in at least one of the categories of ports, establishing a list comprising records, wherein each record comprises an address associated with a respective arrived data packet and a current sequential number associated with a next data packet that has the same address and is next to arrive at the input port or is to be transferred to the output port, respectively;

the records comprise different addresses and only addresses associated with data packets that have latest arrived at the input port or have been latest transferred to the output port, respectively; and

performing at least one of the following steps;

where a time period between data packets transferred from an input port into the network is always larger than a predetermined time interval, restricting a list in an input port to a limited number of records, the limited number of records being larger than a smallest number that prevents a data packet that arrives at the input port and is not associated with a record in the list in the input port from being transferred to an output port in the network before a previous data packet that is transferred to a same output port and is associated with a same address has been transferred through the network to the output port;

removing a record from the list in an input port when no dam packet associated with the address of the record has arrived at the input port during a predetermined time period.

11. The method of claim 10, wherein a list in an input port contains records comprising a destination address, the destination address being included in the data packets themselves or an address of an output port in the network to which the data packets are to be transferred, and a list in an output port contains records comprising a source address, the source address being included in the data packets themselves or an address of an input port in the network from which the data packets have been transferred.

12. The method of claim 11, wherein if the step of removing a record is performed, the number of records in a list in an input port is equal to or larger than a ratio of a time period after which a record in an input port is removed and a minimum time period at which an input port can issue data packets to be transferred through the network or a ratio of a maximum time period for transferring a data packet in the network from an input port to an output port and a minimum time period.

13. The method of claim 11 , wherein the predetermined time period is equal to or larger than a maximum time period for transferring a data packet in the network from an input port to an output port.

14. The method of claim 11, wherein in each record in a list in an input port of the network, information is inserted that represents a time when a data packet latest arrived at the input port associated with the address indicated in the respective record.

15. The method of claim 11, wherein when a data packet has been transferred in the network to an output port and the data packet has a sequential number following a current sequential number in the list'"'"'s record comprising the address with which the data packet is associated, the dam packet is stored to be fed later from the output port.

16. The method of claim 15, wherein at substantially the same time as a data packet having a sequential number following the current sequential number is transferred, information is stored relating to a time when the data packet that was received in the output port is stored.

17. The method of claim 15, wherein when a data packet has been stored for at least the predetermined time period, the data packet is fed from the output port.

18. The method of claim 17, wherein when a stored data packet is fed from an output port, the current sequential number in the list'"'"'s record comprising the address with which this data packet is associated is set equal to the sequential number that is next after the sequential number of the stored data packet.

19. A network for transferring data packets from input ports to output ports of the network, in which data packet transfers require time periods of different lengths and there is a first category comprising all input ports and a second category comprising all output ports comprising:

means for inserting, into a data packet arrived at an input port, a sequential number indicating a sequential position of the arrived dam packet;

in an output port, means for forwarding arrived data packets that have been transferred to the output port, the transferred data packets being forwarded in a correct sequential order based on the sequential numbers of the transferred data packets;

in at least one of the categories of ports, means for establishing a list comprising records, wherein each record comprises an address associated with a respective arrived data packet and a current sequential number associated with a next data packet associated with the same address that is next to arrive at the input port or is to be transferred to the output port, respectively; and

the records comprise different addresses and only addresses associated with data packets that have latest arrived at the input port or have been latest transferred to the output port, respectively;

a memory, in communication with the establishing means, for storing each list; and

further comprising at least one of;

means for restricting a list in an output port to a limited number of records, the number of records being larger than a smallest number that allows a resequencing of data packets transferred to the output port;

arranging means in the establishing means for monitoring each record in the list in an output port to remove from the list a record when no data packet associated with the address of the record has arrived at the input port during the predetermined time period.

20. The network of claim 19, wherein the establishing means makes the records in an input port comprise a destination address, the destination address being an address in the data packets themselves or an address of an output port in the network to which the data packets are to be transferred, and the establishing means makes the records in an output port comprise a source address, the source address being an address in the data packets themselves or an address of an input port in the network from which the data packets have been transferred.

21. The network of claim 20, wherein if the arranging means is included in the network, the number of records in a list in an output port is equal to or larger than a ratio of a sum of a maximum time period for transferring a data packet in the network from an input port to an output port and a time period after which a record in an input port is removed and a minimum time period during which an output port can receive data packets transferred through the network.

22. The network of claim 20, wherein the arranging means uses as a value of the predetermined time period a value equal to or larger than a sum of a maximum time period for transferring a dam packet in the network from an input port to an output port and a time period after which a record in an input port is removed.

23. The network of claim 20, wherein for each record in the list in the input port stored in the memory means, the establishing means inserts information relating to a time when a data packet latest arrived to the input port associated with the address in the respective record.

24. A network for transferring data packets from input ports to output ports of the network, in which data packet transfers require time periods of different lengths and there is a first category comprising all input ports and a second category comprising all output ports comprising:

means for inserting, into a data packet arrived at an input port, a sequential number indicating a sequential position of the arrived data packet;

in an output port, means for forwarding arrived data packets that have been transferred to the output port, the transferred data packets being forwarded in a correct sequential order based on the sequential numbers of the transferred data packets;

in at least one of the categories of ports, means for establishing a list comprising records, wherein each record comprises an address associated with a respective arrived data packet and a current sequential number associated with a next data packet associated with the same address that is next to arrive at the input port or is to be transferred to the output port, respectively; and

the records comprise different addresses and only addresses associated with data packets that have latest arrived at the input port or that have been latest transferred to the output port, respectively;

a memory in communication with the establishing means, for storing each list; and

further comprising at least one of;

means for restricting a list in an input port to a limited number of records, the number of records being larger than a smallest number that prevents a data packet that arrives at the input port and is not associated with a record in the list in the input port from being transferred to an output port in the network before a previous data packet, which is transferred to a same output port and with which a same address is associated, has been transferred through the network to the output port, wherein a time period between data packets transferred from an input port into the network is always larger than a predetermined time interval;

arranging means in the establishing means for monitoring each record in the list in an input port to remove records from a list when no data packet associated with the address of the record has arrived at the input port during a predetermined time period.

25. The network of claim 24, wherein the establishing means makes the records in an input port comprise a destination address, the destination address being an address comprised in the data packets themselves or an address of an output port in the network to which the data packets are to be transferred, and the establishing means makes the records in an output port comprise a source address, the source address being an address in the data packets themselves or an address of an input port in the network from which the data packets have been transferred.

26. The network of claim 25, wherein if the arranging means is included in the network, the number of records in a list in an input port is equal to or larger than a ratio of a time period after which a record in an input port is removed and a minimum time period at which an input port can issue data packets to be transferred through the network or a ratio of a maximum time period for transferring a data packet in the network from an input port to an output port and a minimum time period.

27. The network of claim 25, wherein the arranging means uses as a value of the predetermined time period a value equal to or larger than a maximum time period for transferring a data packet in the network from an input port to an output port.

28. The network of claim 25, wherein for each record in the list in the input port stored in the memory means, the establishing means inserts information relating to a time when a data packet latest arrived to the input port associated with the address in the respective record.