Method and apparatus for performing cut-through virtual circuit merging

• US 6,233,243 B1
• Filed: 11/24/1997
• Issued: 05/15/2001
• Est. Priority Date: 11/24/1997
• Status: Expired due to Fees

• Current Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Original Assignee: Ascend Communications, Inc. (Nokia Corporation)
• Inventors: Ganmukhi, Mahesh N., Palnati, Prasasth R.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): KWOH, JASPER C
• Application Number:
  US08/976,759
• Time in Patent Office: 1,268 Days
• Field of Search: 370/235, 370/401, 370/402, 370/412-418, 370/399, 370/474, 370/389, 370/428, 370/429
• US Class Current: 370/412
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/40 Wormhole routing

Abstract

A method and apparatus for performing virtual connection merging in an output port of a network switch are disclosed. In the event no completely assembled packets have been received and scheduled for transmission, a partially received packet is selected for cut-through transmission prior to receipt of all cells comprising the packet. Transmission of the selected packet is initiated and a timer is started. If the timer expires prior to the receipt of an end of packet indication for the packet for which transmission has commenced, and end of packet signal is generated and transmitted and the transmission of additional cells for the cut-through packet is aborted. In this manner, delays associated with packet reassembly may be avoided and buffer sizes of reassembly buffers may be reduced.

Claims

1. A method for performing cut-through virtual connection merging at an output port of a network switch having a plurality of input ports in a connection based network comprising:

determining whether any of a plurality of cell buffers being loaded from said respective plurality of input ports contains a fully received packet available for transmission over a virtual connection;

if at least one fully received packet is determined to be available for transmission,

selecting one of said fully received packets for transmission using a first predetermined selection criteria;

transmitting said selected packet over said virtual connection; and

returning to said determining step;

if no fully received packets are determined to be available for transmission over said virtual connection, determining whether any of said plurality of cell buffers contains a partially received packet available for cut-through transmission over said virtual connection;

if no partially received packets are determined to be available for transmission, returning to said determining step;

if at least one partially received packet is determined to be available for transmission over said virtual connection,

selecting one of the partially received packets for cut-through transmission using a second predetermined criteria for selection;

initiating cut-through transmission of said selected partially received packet over said virtual connection;

in the event an End of Packet signal is not received for the packet undergoing cut-through transmission prior to expiration of a predetermined period following the initiation of transmission of said cut-through packet, generating and transmitting over said virtual connection an End of Packet (EOP) indication; and

returning to said determining step.

2. The method of claim 1 further comprising the step of:

disregarding the remainder of said selected partially received packet following expiration of said predetermined period.

3. The method of claim 1 wherein said initiating step further includes the step of initiating a timer having a preset expiration period upon initiation of transmission of said partially received packet and said generating step further comprises the step of transmitting an End of Packet indication if said end of packet signal is not received for the packet undergoing cut-through transmission prior to expiration of said timer expiration period.

4. The method of claim 1 wherein said selecting step comprises the step of selecting the first partially received packet for cut-through transmission which is eligible for cut-through transmission and which is detected by a packet scheduler.

5. The method of claim 4 wherein said selecting step further comprises the step of testing packets for cut-through eligibility in a round robin sequence and selecting the first partially received packet which is detected in said round robin sequence that is eligible for cut-through transmission.

6. The method of claim 1 wherein said selecting step further comprises the step of associating a timer value with each packet that is eligible for cut through transmission and selecting the packet for cut-through transmission having the smallest timer value.

7. The method of claim 1 wherein said selecting step further comprises the steps of:

maintaining a cell count of cells received for each packet eligible for cut-through transmission; and

selecting a packet for cut through transmission having the largest cell count from the packets eligible for cut-through transmission.

8. The method of claim 1 wherein said method further comprises the steps of:

at call setup, assigning a plurality of connection identifiers or ingress connections associated with corresponding VPI/VCI addresses;

at call setup associating said plurality of connection identifiers with a group identifier specifying a single egress virtual connection a received packet having a VPI/VCI address associated with one of said plurality of connection identifiers;

wherein said packet selected for cut-through transmission merging is selected from packets associated with said group identifier.

9. Packet scheduling apparatus for merging packets ford transmission from a output port of a network switch over a virtual connection, said packets received as cells through a plurality of input ports of said network switch in a connection based network, the apparatus comprising:

a plurality of cell buffers for storing packets associated with a corresponding plurality of connection identifiers wherein each of said plurality of connection identifiers is associated with a group identifier identifying packets to be merged over said single virtual connection;

a loadable timer operative to produce a timeout signal a predetermined period following activation of said timer; and

a scheduler,

said scheduler being operative to check said plurality of cell buffers to determine whether there is at least one fully received packet in said plurality of cell buffers and, if no fully received packets are found, to determine by checking said plurality of cell buffers whether there is at least one partially received packet in said cell buffers,

said scheduler being further operative to schedule a fully assembled packet stored within one of said plurality of cell buffers for transmission over said virtual connection in the event a fully assembled packet is available for transmission;

said scheduler being further operative to apply a predetermined criteria for selection to selectively initiate transmission of a partially received packet stored within one of said plurality of cell buffers, in the event no fully assembled packets are available for transmission and to activate said timer upon initiation of transmission of said partially received packet;

said scheduler being further operative to generate and transmit an end of packet signal in the event said scheduler detects said timeout signal prior to the completion of reception of said partially received packet in the respective one of said cell buffers; and

said scheduler being further operative to return to the state of checking at completion of transmission of the currently transmitting packet.

10. The packet scheduling apparatus of claim 9 wherein said scheduler is further operative to disregard the remainder of said partially received packet following detection of said timeout signal in the event said scheduler detects said timeout signal prior to the completion of reception of said partially received packet.

11. The packet scheduling apparatus of claim 9 wherein a timer value is stored in the respective cell buffer associated with each connection identifier associated with said group identifier and said timer predetermined period is selected based upon the connection identifier for the respective packet.

12. The packet scheduling apparatus of claim 9 wherein said timer predetermined period is selected based upon the group identifier.

13. The packet scheduling apparatus of claim 9 wherein a pointer to a timer value stored in a timer value table is stored in the cell buffer associated with each connection identifier associated with said group identifier and said timer predetermined period is selected based upon the specified value within said timer value table.

14. The packet scheduling apparatus of claim 9 wherein said partially received packet comprises at least one cell stored within the respective cell buffer.

15. The packet scheduling apparatus of claim 14 wherein said at least one cell comprises at least one Asynchronous Transfer Mode cell.

16. The packet scheduling apparatus of claim 9 wherein said scheduler is operative to select the first partially received packet which is detected and eligible for transmission over said virtual connection.

17. The packet scheduling apparatus of claim 16 wherein said scheduler is operative to test said cell buffers associated with said group identifier to identify partially received packets eligible for transmission in a round robin sequence.

18. The packet scheduling apparatus of claim 9 wherein a timer value is associated with each connection identifier and employed to specify said timer predetermined period and said scheduler is operative to select for transmission the partially received packet associated with the smallest timer value in the event there are no fully received packets associated with said group identifier available for transmission.

19. The packet scheduling apparatus of claim 9 wherein a cell count identifying the number of cells stored within the cell buffer is maintained for each cell buffer associated with said group identifier and said scheduler is operative to select for transmission the partially received packet associated with the largest cell count in the event there are no fully received packets associated with said group identifier available for transmission.