Hierarchical path hunt for multirate connections

A method of providing a switched connection of a given bandwidth as a collection of a plurality of connections of smaller bandwidth through a switching network providing connections having a hierarchy of data rates comprising at least a high rate and a lower rate, wherein said switching network is a three-stage network having switching elements and that includes a hierarchy of status tables for each individual input and each individual output switching element of said three-stage network, said hierarchy of status tables corresponding to said hierarchy of data rates, each status table having entries each defining availability of time slots having bandwidth of the corresponding rate and connecting the corresponding individual input or output switching element with an intermediate switching stage of said three-stage network and defining availability as fully-available, partially-available, or non-available, said method comprising the steps of:

• providing at least one connection having said high rate to satisfy some of said given bandwidth, including
• finding first entries defining fully-available bandwidth in high rate status tables for matching first time slots of an input switching element and an output switching element to be used for said connection of said given bandwidth to satisfy as much of said given bandwidth as possible, and marking said first entries as non-available;
• and
• providing at least one connection having said lower rate to satisfy other of said given bandwidth.

A method of providing a switching connection of a given bandwidth as a collection of a plurality of connections of smaller bandwidth through a switching network providing connections having a hierarchy of data rates comprising at least a high rate and a lower rate, where said switching network is a three-stage network having switching elements, said method comprising the steps of:

• storing a hierarchy of status tables for each input and output switching element of said three-stage network, and status tables having entries defining availability of time slots connecting the input and the output switching elements with an intermediate switching stage of said three-stage network, said hierarchy of status tables corresponding to said hierarchy of data rates and defining availability of full, partial, or idle, for connections having said high and said lower rate;
• finding matching idle entries in the high rate status tables for the input and the output switching elements to be used for said connection of said given bandwidth to meet the requirements of as much of said given bandwidth as possible;
• marking said found idle entries as full and updating corresponding status tables for said lower rate;
• and
• providing at least one connection having said lower rate to satisfy as much of any unsatisfied bandwidth of said given bandwidth as possible.

In a three-stage switching network having switching elements and providing connections of STS-N, VT, and DS-0 rates where N is an integer, a path-hunt method comprising the steps of:

• storing a hierarchy of status tables for each input and output switching element of said three-stage network, said status tables having entries defining availability of time slots connecting the corresponding input or output switching element with an intermediate switching stage of said three-stage network, said hierarchy of status tables corresponding to said STS-N, VT, and DS-0 rates and defining availability as full, partial, or idle for connections having said STS-N and VT rates, and defining availability as busy or idle for connections having said DS-0 rate.
• A) in response to a request for an STS-N connection, finding matching idle entries in the STS-N status tables for the input and the output switching elements to be used for said STS-N connection and assigning time slots represented by said matched idle STS-N entries to said STS-N connection;
• B) in response to a request for a VT connection, finding matching idle entries in the VT status tables for the input and the output switching elements to be used for said VT connection, and assigning time slots represented by said matching idle VT entries to said VT connection but only when the result of such assignment of said VT time slots does not result in a previously-idle STS-N entry no longer being available for STS-N connections unless such assignment is necessary to prevent blocking of said VT connection;
• and
• C) in response to a request for a DS-0 connection, finding matching idle entries in the DS-0 status tables for the input and the output switching elements to be used for said DS-0 connection, and assigning time slots represented by said matching idle DS-0 entries to said DS-0 connection but only when the result of such assignment of said DS-0 time slots does not result in a previously-idle VT entry no longer being available to VT connections unless such assignment is necessary to prevent blocking of said DS-0 connection.

In a three-stage switching network providing connections having a hierarchy of data rates comprising a highest rate, at least one intermediate rate, and a lowest rate, a path-hunt method comprising the steps of:

• in response to a request for a switched connection of a given bandwidth through the three-stage switching network, dividing said given bandwidth into a plurality of bandwidths corresponding to individual rates of said hierarchy of data rates;
• path-hunting for connections having said highest rate to try to satisfy at least some of any bandwidths of said plurality which correspond to said highest rate;
• dividing any unsatisfied bandwidths of said plurality which correspond to said highest rate into additional bandwidths corresponding to at least one of the lower rates;
• path-hunting for connections having said at least one intermediate rate to try to satisfy at least some of any bandwidths which correspond to said at least one intermediate rate;
• dividing any unsatisfied bandwidths which correspond to said at least one intermediate rate into additional bandwidths corresponding to said lowest rate;
• and
• path-hunting for connections having said lowest rate to try to satisfy any bandwidths which correspond to said lowest rate.

A switching arrangement comprising:

• a switching network that switches connections having a hierarchy of data rates comprising at least a high rate and a lower rate;
• first means responsive to a request for a switched connection of a given bandwidth, for dividing the given bandwidth into at least one first connection having the high rate;
• means coupled to the first means for dividing, for attempting to find the at least one first connection having the high rate to satisfy some of the given bandwidth;
• second means for dividing any remainder of the given bandwidth into at least one second connection having the lower rate;
• third means responsive to failure to find at least one attempted first connection, for dividing the bandwidth of any said failed attempted first connection into a plurality of third connections having the lower rate;
• and
• means coupled to the second and third means for dividing, for finding the third connections and any said connections having the lower rate to satisfy other of the given bandwidth;
• the switching network providing the requested connection as a collection of the found connections.

A switching arrangement comprising:

• a three-stage switching network that switches connections having a hierarchy of data rates comprising at least a high rate and a lower rate, the three-stage switching network having switching elements and including a hierarchy of status tables for each individual input and each individual output switching element of said three-stage network, said hierarchy of status tables corresponding to said hierarchy of data rates, each status table having entries each defining availability of time slots having bandwidth of the corresponding rate and connecting the corresponding individual input or output switching element with an intermediate switching stage of said three-stage network and defining availability as fully-available, partially-available, or non-available;
• and
• means responsive to a request for a switched connection of a given bandwidth, for finding at least one connection through the switching network having the high rate to satisfy some of the given bandwidth, including
• means for finding first entries defining fully-available bandwidth in high rate status tables for matching first time slots of an input switching element and an output switching element to be used for said connection of said given bandwidth to satisfy as much of said given bandwidth as possible, and
• means coupled to the means for finding first entries, for marking said first entries as non-available;
• and
• means responsive to the request, for finding at least one connection through the switching network having the lower rate to satisfy other of the given bandwidth;
• the switching network providing the requested connection as a collection of the found connections.

A switching arrangement comprising:

• a three-stage switching network that switches connections having a hierarchy of data rates comprising at least a high rate and a lower rate and having switching elements and
• a hierarchy of status tables for each input and each output switching element of said three-stage network, said status tables having entries defining availability of time slots connecting the corresponding input or output switching element with an intermediate switching stage of said three-stage network, said hierarchy of status tables corresponding to said hierarchy of data rates and defining availability of full, partial, or idle, for connections having said high and said lower rate;
• first means responsive to a request for a switched connection of a given bandwidth, for finding matching idle entries in the high rate status tables for the input and the output switching elements to be used for said connection of said given bandwidth to meet the requirement of as much of said given bandwidth as possible;
• means coupled to said first means for finding entries, for marking said found idle entries as full and updating corresponding status tables for said lower rate;
• and
• means responsive to the request, for finding at least one connection through the three-stage network having the lower rate to satisfy as much of any unsatisfied bandwidth of said given bandwidth as possible.

A switching system comprising:

• a three-stage network having switching stages comprising switching elements for switching connections having a hierarchy of data rates comprising a lowest rate corresponding to one time slot of a time division frame of time slots, said hierarchy comprising at least one higher rate corresponding to a predefined plurality of time slots within said frame;
• a hierarchy of status tables for each input and each output switching element of input and output stages, respectively, of said three-stage network, said status tables having entries defining availability of time slots connecting the corresponding input or output switching element with an intermediate switching state of said three-stage network, said hierarchy of status tables corresponding to said hierarchy of data rates, said status tables for said higher rate defining the corresponding plurality of time slots, as full, partial or idle, said status tables for said lowest rate defining each time slot of said frame as busy or idle;
• and
• means, responsive to a request for a connection through said three-stage network having said higher rate, for finding matching idle entries in the status tables for said higher rate for the input and the output switching elements to be used for said requested connection if such matching idle entries exist.

A switching system comprising:

• a three-stage network having switching elements and providing connections having STS-N, VT, and DS-0 rates where N is an integer;
• a hierarchy of status tables for each input and each output switching element of said three-stage network, said status tables having entries defining availability of time slots connecting the corresponding input or output switching element with an intermediate switching stage of said three-stage network, said hierarchy of status tables corresponding to said STS-N, VT, and DS-0 rates and defining availability as full, partial, or idle for connections having said STS-N and VT rates, and defining availability as busy or idle for connections having said DS-0 rate;
• means responsive to a request for an STS-N connection, for finding matching idle entries in the STS-N status tables for the input and the output switching elements to be used for said STS-N connection and assigning time slots represented by said matching idle STS-N entries to said STS-N connection;
• means responsive to a request for a VT connection, for finding matching idle entries in the VT status tables for the input and the output switching elements to be used for said VT connection, and assigning time slots represented by said matching idle VT entries to said VT connection but only when the result of such assignment of said VT time slots does not result in a previously-idle STS-N entry no longer being available for STS-N connections unless such assignment is necessary to prevent blocking of said VT connection;
• and
• means responsive to a request for a DS-0 connection, for finding matching idle entries in the DS-0 status tables for the input and the output switching elements to be used for said DS-0 connection, and assigning time slots represented by said matching idle DS-0 entries to said DS-0 connection but only when the result of such assignment of said DS-0 time slots does not result in a previously-idle VT entry no longer being available for VT connection unless such assignment is necessary to prevent blocking of said DS-0 connection.

A path-hunt arrangement for a three-stage switching network providing connections having a hierarchy of data rates comprising a highest rate, at least one intermediate rate, and a lowest rate, comprising:

• means responsive to a request for a switched connection of a given bandwidth through the three-stage network, for dividing said given bandwidth into a plurality of bandwidths corresponding to individual rates of said hierarchy of data rates;
• means for path-hunting for connections having said highest rate to try to satisfy at least some of any bandwidths of said plurality which correspond to said highest rate;
• means for dividing any unsatisfied bandwidths of said plurality which correspond to said highest rate into additional bandwidths corresponding to at least one of the lower rates;
• means for path-hunting for connections having said at least one intermediate rate to try to satisfy at least some of any bandwidths which correspond to said at least one intermediate rate;
• means for dividing any unsatisfied bandwidths which correspond to said at least one intermediate rate into additional bandwidths corresponding to said lowest rate;
• and
• means for path-hunting for connections having said lowest rate to try to satisfy any bandwidths which correspond to said lowest rate.

The path-hunt arrangement of claim 57 wherein

• the means for path-hunting for connections having said lowest rate comprises
• fourth means for seeking, for every connection having said lowest rate, to find a pair of fourth entries defining at least partially-available bandwidth in said highest-rate status tables for matching fourth time slots of said input and output switching elements to be used for said connection having said lowest rate,
• fifth means coupled to said fourth means for seeking, responsive to finding a pair of said sought fourth entries, for seeking to find a pair of fifth entries defining at least partially-available bandwidth in said intermediate rate status tables for matching fifth time slots of said input and output switching elements to be used for said connection having said lowest rate,
• sixth means coupled to said fifth means for seeking, responsive to finding a pair of said sought fifth entries, for seeking to find a pair of sixth entries defining fully-available bandwidth in lowest rate status tables for matching sixth time slots of said input and output switching elements to be used for said connection having said lowest rate,
• third means coupled to said sixth means for seeking, responsive to finding any of said sought pairs of sixth entries, for marking the found pairs of sixth entries as non-available, and
• fourth means coupled to said third means for marking, responsive to marking any found pairs of sixth entries non-available, for selectively marking the corresponding fourth and fifth entries as partially-available or non-available.

A method of providing a switched connection of a given bandwidth between an input and an output port of a switching network as a collection of a plurality of connections of smaller bandwidth between said input and said output through said switching network, said method comprising the steps of:

• dividing said given bandwidth into at least one first unitarily-switched connection having a high data rate between said input and said output of said switching network, said first unitarily-switched connection being one of a plurality of unitarily-switched connections provided by said switching network between inputs and outputs of said switching network and having a hierarchy of data rates comprising at least the high rate and a lower rate;
• dividing any remainder of said given bandwidth into at least one second unitarily-switched connection having said lower data rate between said input and said output of said switching network, said second unitarily-switched connection being one of the plurality of unitarily-switched connections provided by said switching network;
• attempting to providing said at least one first unitarily-switched connection having said high rate between said input and said output of said switching network to satisfy some of said given bandwidth;
• selectively failing to provide at least one said attempted first unitarily-switched connection;
• in response to failing to provide at least one said attempted first unitarily switched connection, dividing the bandwidth of any said failed attempted first unitarily-switched connection into a plurality of third unitarily-switched connections having said lower rate between said input and said output of said switching network, said third unitarily-switched connection being one of the plurality of unitarily-switched connections provided by said switching network;
• and
• providing said third unitarily-switched connections and any said second unitarily-switched connections having said lower rate between said input and said output of said switching network to satisfy other of said given bandwidth.

A method of providing a switched connection of a given bandwidth as a collection of a plurality of available switched connections of smaller bandwidth selected from among switched connections having a hierarchy of data rates comprising at least at high rate and a lower rate and provided by a multi-stage switching network having stages interconnected by paths that are individually time-division multiplexed between a plurality of switched connections, said method comprising the steps of:

• finding at least one available switched connection having said high rate through said multi-stage switching network across at least one of said paths to satisfy some of said given bandwidth;
• finding at least one available switched connection having said lower rate through said multi-stage switching network across at least one of said paths to satisfy other of said given bandwidth;
• and
• providing said found available switched connections through said multi-stage network across at least one of said paths to jointly serve as said switched connection of a given bandwidth.

A switching arrangement comprising:

• a switching network that provides unitarily-switched connections between inputs and outputs of said switching network, said unitarily-switched connections having a hierarchy of data rates comprising at least a high rate and a lower rate;
• first means responsive to a request for a switched connection of a given bandwidth between an input and an output of said switching network, for dividing the given bandwidth into at least one first unitarily-switched connection having the high rate between said input and said output of said switching network;
• means coupled to the first means for dividing, for attempting to find the at least one first unitarily-switched connection having the high rate between said input and said output of said switching network to satisfy some of said given bandwidth;
• second means for dividing any remainder of the given bandwidth into at least on second unitarily-switched connection having the lower rate between said input and said output of said switching network;
• third means responsive to failure to find at least one attempted said first unitarily-switched connection, for dividing the bandwidth of any said failed attempted fist unitarily-switched connection into a plurality of third unitarily-switched connections having the lower rate between said input and said output of said switching network;
• and
• means coupled to the second and third means for dividing, for finding the third unitarily-switched connections and any said second unitarily-switched connections having the lower rate between said input and said output of said switching network to satisfy other of said given bandwidth.

A switching arrangement comprising:

• a multi-stage switching network having stages interconnected by paths that are individually time-division multiplied by a plurality of switched connections and that switches connections having a hierarchy of data rates comprising at least a high rate and a lower rate;
• means responsive to a request for a switched connection of a given bandwidth, for finding at least one available switched connection having said high rate through said multi-stage switching network across at least one of said paths to satisfy some of said given bandwidth;
• and
• means responsive to the request, for finding at least one available switched connection having said lower rate through said multi-stage switching network across at least one of said paths to satisfy other of said given bandwidth;
• the multi-stage switching network providing said found available switched connections through said multi-stage switching network across at least one of said paths to jointly serve as said requested connection.