Method and apparatus for minimizing contention losses in networks

• US 6,243,378 B1
• Filed: 10/27/1999
• Issued: 06/05/2001
• Est. Priority Date: 06/26/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Olnowich, Howard Thomas
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): Qureshi, Afsar M.
• Application Number:
  US09/428,636
• Time in Patent Office: 587 Days
• Field of Search: 370/386, 370/388, 370/411, 370/351, 370/367, 370/228, 370/462, 340/825.01, 340/825.02, 340/826, 340/827, 340/825.05, 340/825.79, 379/219, 379/220, 379/221, 379/271, 379/273
• US Class Current: 370/388
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Contention losses are minimized in path searching, circuit-switched networks by adding intelligence to the last stage of the network. A count of number of bytes remaining to be transferred in each active message is maintained in real time for each output port of the network. If contention arises at the last stage switch being requested in camp-on mode to make a connection to a busy output port, the switch checks the bytes remaining count and responds differently depending on how the bytes remaining count compares to a preset threshold register. If the count remaining is below the threshold, the last stage switch accepts the camp-on request, because the desired output port will be available shortly. If the count remaining is above the threshold or below the threshold but another user is camped-on, the switch rejects the camp-on request to the last stage, because the desired output port will not be available shortly. In this case further path searching would be meaningless. A different message to a different destination (output port) is tried, and later the contended message is retried.

Claims

1. A multi-stage switching network, the network comprising a plurality of self-routing switches cascaded into first, middle and last stages, each said switch including a plurality of switch inputs and a plurality of switch outputs, each of the switch outputs of each said switch coupled to a different switch input of others of said switches;

wherein each of said output ports of said last stages includes a threshold means for determining whether a selective camp-on request remains pending while waiting for said output port to become not busy or is rejected; and

said last stages including a plurality of output ports each having a threshold and logic responsive to said camp-on command for selectively camping-on a busy output port, accepting the camp-on command, waiting for said output port to become not busy, and then connecting said data message to said output port, or rejecting said camp-on command, when said output port is busy and previously camped-on, or busy and will not be available within said threshold.

2. A multi-stage switching network, the network comprising:

a plurality of self-routing switches cascaded into first, middle and last stages, each said switch including a plurality of switch inputs and a plurality of switch outputs, each of the switch outputs of each said switch coupled to a different switch input of others of said switches,

a plurality of output ports comprising switch outputs of the last stage switches;

a plurality of network input ports comprising switch inputs of the first stage switches;

normal connection circuitry (1) for establishing a connection path between any one of the network input ports and any one of the network output ports in response to a connection request, said connection path comprising a plurality of connection segments, each connection segment providing the connection of one of said switch inputs to one of said switch outputs at any said network stage; and

(2) for canceling said connection path when any one of said plurality of connection segments is not available;

selective camp-on connection logic responsive to a selective camp-on request (1) for establishing a connection path between any one of the network input ports and any one of the network output ports in response to a selective camp-on connection request; and

(2) for holding said connection path until a blocked or busy connection segment becomes available or said selective camp-on connection request is rejected;

threshold logic for defining the upper limit of the amount of time that said connection path is held until a selective connection request is rejected;

a selective camp-on connection at said last stages, said last stages including a plurality of output ports each having a threshold and logic responsive to said camp-on command for selectively camping-on a busy output port, accepting the camp-on command, waiting for said output port to become not busy, and then connecting said data message to said output port, or rejecting said camp-on command, when said output port is busy and previously camped-on, or busy and will not be available within said threshold.

3. A multi-stage switching network, the network comprising:

a plurality of self-routing switches cascaded into first, middle and last stages, each said switch including a plurality of switch inputs and a plurality of switch outputs, each of the switch outputs of each said switch coupled to a different switch input of others of said switches,

a plurality of output ports comprising switch outputs of the last stage switches;

a plurality of network input ports comprising switch inputs of the first stage switches;

selective camp-on connection means responsive to a selective camp-on request (1) for establishing a connection path between any one of the network input ports and any one of the network output ports in response to a selective camp-on connection request; and

(2) for holding said connection path until a blocked or busy connection segment becomes available or said selective camp-on connection request is rejected;

a threshold means for defining the upper limit of the amount of time that said connection path is held until a selective connection request is rejected; and

said last stages including plurality of output ports each having a threshold and logic responsive to said camp-on command for selectively camping-on a busy output port, accepting the camp-on command, waiting for said output port to become not busy, and then connecting said data message to said output port, or rejecting said camp-on command, when said output port is busy and previously camped-on, or busy and will not be available within said threshold.

4. A method of sending data messages across n stages of a switching network responsive to a connection request including n sequential connection commands, each sequential connection command selecting one of a plurality of connection segments for each of n stages of said switching network, comprising the steps of:

sending a plurality of sequential connection commands;

selecting one of said plurality of connection segments;

transmitting first a first connection command for a first network stage;

transmitting last a connection command for a last network stage; and

holding said sequential connection command pending while waiting for said output port to become not busy, or rejecting said sequential connection command based on an upper limit of the amount of waiting time.

5. The method of claim 4, further comprising the step of:

establishing a connection segment from any switch input port to any switch output port selectively as a normal connection request or as a camp-on connection request.

6. The method of claim 4, further comprising the step of:

selectively enabling a selective camp-on connection individually at each of said n network stages and for defaulting to a normal connection segment upon not selecting said camp-on connection.

7. A method of sending data messages across n stages of a switching network, comprising the steps of:

receiving separately or simultaneously a plurality of connection requests;

responsive to said connection requests, establishing a plurality of simultaneously active communication paths between a plurality of network input ports and a plurality of network output ports and

holding each of said connection requests pending while waiting for said network output port to become not busy, or rejecting each of said connection requests based on an upper limit of the amount of waiting time.

8. A method of operating a switch input port and a switch output port of each stage of a multi-stage switching network, comprising the steps of:

communicating a data message over a plurality of data lines; and

signaling back over a first control line to a sending node a rejection of any connection request;

signaling back over a second control line to said sending node the acceptance of a selective camp-on connection request;

signaling back over a third control line the establishment of a valid connection path; and

signaling back over a fourth control line the establishment of a camp-on connection segment.

9. A method of sending data messages in parallel across a plurality of data lines, comprising the steps of:

signaling back to a sending node a rejection of any connection request;

signaling back to said sending node an acceptance of a selective camp-on connection request; and

signaling back to said sending node the activation of a valid connection path.

10. A last stage apparatus of a multi-stage switching network, comprising:

a camp-on control line;

a rejection control line for signaling back to a sending node a rejection of a selective camp-on connection request;

selective camp-on connection means;

cancellation means (1) for canceling said selective camp-on connection means when a pulse is received on said rejection control line for signaling back to said sending node a rejection of a selective camp-on connection request; and

thereupon (2) for deactivating the signal on said camp-on control line.

11. A method for operating the last stage of a multi-stage switching network, comprising the steps of:

receiving a camp-on connection request from a sending node;

selectively signaling back to said sending node a camp-on control signal indicating the acceptance of said camp-on connection request;

canceling selective camp-on connection status upon signaling to a sending node a rejection of said selective camp-on connection request; and

thereafter

deactivating said camp-on control signal.

12. A last stage apparatus of a multi-stage switching network, each switch of a plurality of switches of said last stage comprising:

means for determining the number of bytes in a data message received at said switch;

means for storing the determined byte count in one of a plurality of byte count registers, each byte count register corresponding to an associated one of a plurality of switch output ports; and

means for determining a bytes remaining count for each data message being transmitted to an associated output port by decrementing the corresponding byte count register as each byte of a data message is transferred through said switch.

13. A method for operating a switch in a last stage of a multi-stage switching network, comprising the steps of:

associating a camp-on queue with each output port of said switch;

holding in said camp-on queue a plurality of camp-on connection commands received at the input ports of said switch selecting a same switch output port;

selecting one of said camp-on connection commands held in said camp-on queue to establish a next connection segment to said switch output port as soon as said switch output port becomes available; and

signifying to said sending node of a hold period to establish said connection segment by holding an acceptance control signal active until the requested connection segment is established.

14. The method of claim 13, further comprising the steps of:

establishing a programmable threshold value for each said switch output port;

issuing a camp-on rejection pulse over a rejection control line when a requested connection to the said switch output port is not available and a bytes remaining count for the same switch output port is greater than said programmable threshold for the same switch output port, or there is at least one other queued camp-on connection command being held active.

15. A method for sending a data message through each stage of a multi-stage switch, comprising the steps of:

requesting first and middle stages to establish connection segments using said normal connection; and

requesting a last stage to establish the last connection segment using selective camp-on.

16. The method of claim 15, further comprising the steps of:

storing a maximum delivery time constant at the initiation of each data message; and

responsive to said maximum delivery time constant and a message delivery elapsed time, establishing a time period for canceling camp-on requests.

17. The method of claim 16, further comprising the steps of:

maintaining said camp-on request until said data message is accepted over said network.

18. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for sending data messages across n stages of a switching network responsive to a connection request including n sequential connection commands, each sequential connection command selecting one of a plurality of connection segments for each of n stages of said switching network, said method steps comprising:

sending a plurality of sequential connection commands;

selecting one of said plurality of connection segments;

transmitting first a first connection command for a first network stage; and

transmitting last a connection command for a last network stage.

19. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for operating a switch input port and a switch output port of each stage of a multi-stage switching network, said method steps comprising:

communicating a data message over a plurality of data lines; and

signaling back over a first control line to a sending node a rejection of any connection request;

signaling back over a second control line to said sending node the acceptance of a selective camp-on connection request;

signaling back over a third control line the establishment of a valid connection path; and

signaling back over a fourth control line the establishment of a camp-on connection segment.

20. A program storage device readable by a machine, tangibly embodying a program of instructions executable by a machine to perform method steps for sending a data message through each stage of a multi-stage switch, said method steps comprising:

requesting first and middle stages to establish connection segments using said normal connection; and

requesting a last stage to establish the last connection segment using selective camp-on.

21. A method of sending data messages across n stages of a switching network responsive to a connection request including n sequential connection commands, each sequential connection command selecting one of a plurality of connection segments for each of n stages of said switching network, comprising the steps of:

sending a plurality of sequential connection commands;

selecting one of said plurality of connection segments;

transmitting first a first connection command for a first network stage;

transmitting last a connection command for a last network stage;

establishing a connection segment from any switch input port to any switch output port selectively as a normal connection request or as a camp-on connection request; and

selectively enabling a selective camp-on connection individually at each of said n network stages and for defaulting to a normal connection segment upon not selecting said camp-on connection.