Hierarchical path hunt for multirate connections

Claim 2

The method of claim 1 wherein: the step of finding at least one available switched connection having said high rate comprises the step of path-hunting for said available switched connections having said high rate to satisfy as much of said given bandwidth as possible; and the step of finding at least one available switched connection having said lower rate comprises the step of path-hunting for said available switched connections having said lower rate to satisfy all of any unsatisfied bandwidth of said given bandwidth.

Claim 3

The method of claim 1 wherein: the step of finding at least one available switched connection having said high rate comprises the steps of dividing said given bandwidth into at least one first said switched connection having said high rate, dividing any remainder of said given bandwidth into at least one second said switched connection having said lower rate, attempting to find an available said at least one first switched connection having said high rate, and selectively failing to find an available at least one said attempted first switched connection; and the step of finding at least one available switched connection having said lower rate comprises the steps of in response to failing to find an available at least one said attempted first switched connection, dividing the bandwidth of any said failed attempted first switched connection into a plurality of third said switched connections having said lower rate, and finding available said third switched connections and any said second switched connections having said lower rate.

Claim 4

The method of claim 1 for providing said switched connection of said given bandwidth between an input and an output port of said switching network as said collection of said plurality of connections of smaller bandwidth between said input and said output through said switching network, wherein: the step of finding at least one available switched connection having said high rate comprises 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 provide 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, and selectively failing to provide at least one said attempted first unitarily-switched connection; the step of finding a least one available switched connection having said lower rate comprises the steps of 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 the step of providing said found available switched connections comprises the step of 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.

Claim 5

The method of claim 2 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 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 network and defining availability as fully-available, partially-available, or non-available, wherein: the step of path-hunting for said available connections having said high rate comprises the step of 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, marking said first entries as non-available, and marking second entries in said status tables for said lower rate which correspond to said first entries as non-available; and the step of providing said found available switched connections comprises the step of programming a connection between said first matching time slots into control memories of said input and output switching elements and said intermediate switching stage.

Claim 6

The method of claim 5 wherein the step of path-hunting for said available connections having said lower rate comprises the steps of finding second entries defining at least partially-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements, for said second entries, finding third entries defining at least partially-available bandwidth, for matching third time slots in lower rate status tables which correspond to said second entries, selectively marking the third entries as partially-available or non-available, and selectively marking the second entries as either partially-available or non-available; and the step of providing said found available switched connections further comprises the step of programming a connection between said third matching time slots into control memories of said input and output switching elements and said intermediate switching stage.

Claim 7

The method of claim 6 wherein: the step of finding second entries comprises the step of seeking to find initial second entries defining partially-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements, in response to either not finding said initial second entries or finding said initial second entries but not finding said third entries in the lower rate status tables which correspond to said initial second entries, seeking to find intermediate second entries one of which defines partially-available bandwidth and the other of which defines fully-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements, and in response to either not finding said intermediate second entries or finding said intermediate second entries but not finding said third entries in the lower rate status tables which correspond to said intermediate second entries, seeking to find final second entries defining fully-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements; the step of finding third entries comprises the steps of for each pair of found second entries, seeking to find initial third entries defining partially-idle bandwidth for matching third time slots in lower rate status tables which correspond to said pair of found second entries, in response to not finding said initial third entries, seeking to find intermediate third entries one of which defines partially-idle bandwidth and the other of which defines fully-idle bandwidth for matching third time slots in lower rate status tables which correspond to said pair of found second entries, and in response to not finding said intermediate third entries, seeking to find final third entries defining fully-idle bandwidth for matching third time slots in lower rate status tables which correspond to said pair of found second entries; and the step of marking said third entries comprises the step of in response to finding any said third entries, selectively marking said found third entries as partially-available or non-available.

Claim 8

A switching arrangement comprising: a multi-stage switching network having stages interconnected by paths that are individually time-division multiplexed 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.

Claim 9

The switching arrangement of claim 8 wherein: the means for finding at least one available switched connection having said high rate comprises means for path-hunting for said available switched connections having said high rate to satisfy as much of said given bandwidth as possible; and the means for finding at least one available switched connection having said lower rate comprises means for path-hunting for said available switched connections having said lower rate to satisfy all of any unsatisfied bandwidth of said given bandwidth.

Claim 10

The switching arrangement of claim 8 wherein: the means for finding at least one available switched connection having said high rate comprises first means for dividing the given bandwidth into at least one first said switched connection having the high rate, and means coupled to the first means for dividing, for attempting to find an available said at least one first switched connection having the high rate; and the means for finding at least one available switched connection having said lower rate comprises second means for dividing any remainder of said given bandwidth into at least one second said switched connection having said lower rate, third means responsive to failure to find an available at least one attempted first switched connection, for dividing the bandwidth of any said failed attempted first switched connection into a plurality of third said switched connections having said lower rate, and means coupled to the second and third means for dividing, for finding available said third switched connections and any said second switched connections having said lower rate.

Claim 11

The switching arrangement of claim 8 wherein: the multi-stage switching network 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; the means for finding at least one available switched connection having said high rate comprises 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, and 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; the means for finding at least one available switched connection having said lower rate comprises second means for dividing any remainder of the given bandwidth into at least one 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 first 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.

Claim 12

The switching arrangement of claim 8 wherein: said switching network is a three-stage network that has switching elements and includes a hierarchy of status tables for each individual input and each individual output switching element of said 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 network and defining availability as fully-available, partially-available, or non-available; and the means for finding connections at said high rate comprises 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, means for marking said first entries as non-available, and means for marking second entries in said status tables for said lower rate which correspond to said first entries as non-available; and the multi-stage switching network further comprising means for programming a connection between said first matching time slots into control memories of said input and output switching elements and said intermediate switching stage.

Claim 13

The switching arrangement of claim 12 wherein the means for finding connections at said lower rate comprises means for finding second entries defining at least partially-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements, means for finding, for said second entries, third entries defining at least partially-available bandwidth, for matching third time slots in lower rate status tables which correspond to said second entries, means for selectively marking the third entries as partially-available or non-available, and means for selectively marking the second entries as either partially-available or non-available; and the means for programming include means for programming a connection between said third matching time slots into control memories of said input and output switching elements and said intermediate switching stage.

Claim 14

The switching arrangement of claim 13 wherein the means for finding second entries comprises means for seeking to find initial second entries defining partially-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements, means, responsive to either not finding said initial second entries or finding said initial second entries but not finding said third entries in the lower rate status tables which correspond to said initial second entries, for seeking to find intermediate second entries one of which defines partially-available bandwidth and the other of which defines fully-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements, and means, responsive to either not finding said intermediate second entries or finding said intermediate second entries but not finding said third entries in the lower rate status tables which correspond to said intermediate second entries, for seeking to find final second entries defining fully-available bandwidth in said high rate status tables for matching second time slots of said input and output switching elements; the means for finding third entries comprises means for seeking to find, for each pair of found second entries, initial third entries defining partially-idle bandwidth for matching third time slots in lower rate status tables which correspond to said pair of found second entries, means, responsive to not finding said initial third entries, for seeking to find intermediate third entries one of which defines partially-idle bandwidth and the other of which defines fully-idle bandwidth for matching third time slots in lower rate status tables which correspond to said pair of found second entries, and means, responsive to not finding said intermediate third entries, for seeking to find final third entries defining fully-idle bandwidth for matching third time slots in lower rate status tables which correspond to said pair of found second entries; and the means for marking said third entries is responsive to finding any said third entries, for selectively marking said found third entries as partially-available or non-available.