US5355364A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of routing electronic messages
Assignee: International Business Machines Corp
•
Filing: 1992-10-30
•
Granted: 1994-10-11
•
Expires: 2012-10-30
Abstract
Abstract A method of sending an electronic message from a source station through a network of switches and links to a destination station. An electronic message is sequentially sent to each of a series of switches. Each switch reads a route signal in the message and sends the message to a switch or a station having an input port connected to an output port identified by the route signal. The route signals are generated by storing a weight for each switch link in the network. Candidate paths through the switch network starting at the source station and ending at initial candidate destinations are identified. Each initial candidate destination has an input port directly connected to an output port of a switch having an input port directly connected to the source station. If one or more candidate destinations are the destination station, a candidate path ending at the destination station is selected, and a series of route signals corresponding to the selected candidate path is generated. If no candidate destination is the destination station, extended candidate paths are formed. Each extended candidate path has a path weight comprising the weights of switch links along the candidate path. If one or more extended candidate destinations are the destination station, a candidate path ending at the destination station and having a path weight better than or equal to the path weight of each other candidate path ending at the destination station is selected. Otherwise, the candidate paths are again extended.
Inventors
- 👤 Bulent Abali
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:34
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/12
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
434 words
A method of sending an electronic message from a source station through a network of a plurality of switches and links to a destination station, said method comprising: generating a series of one or more route signals, each route signal identifying an output port of a switch in the network of switches; compiling the series of route signals into an electronic message; and sequentially sending the message to each of a series of one or more switches, each switch reading a route signal in the message and sending the message to a component having an input port connected to an output port identified by the route signal; characterized in that the step of generating the series of route signals comprises the steps of: (a) storing in a location accessible to each said source station a weight w o m for each switch link connecting an output port of each of said switches to an input port of another of said switches, where m identifies the switch having an output port and o identifies the output port of that switch; (b) identifying one or more candidate paths through the switch network starting at the source station and ending at initial candidate destinations, each initial candidate destination comprising a component having an input port directly connected to an output port of a switch having an input port directly connected to the source station; (c) if one or more initial candidate destinations are the destination station, selecting a candidate path ending at the destination station, and generating in the source station a series of route signals corresponding to the selected candidate path, and changing the weight w o m of each switch link forming the candidate path; otherwise (d) identifying one or more extended candidate paths through the switch network starting at the source station and ending at next candidate destinations, each next candidate destination comprising a component having an input port directly connected to an output port of an immediately preceding candidate destination, each extended candidate path having a path weight comprising the weights of switch links along the candidate path; and then (e) if one or more candidate destinations are the destination station, selecting a candidate path ending at the destination station and having a path weight which is less than or equal to the path weight of each other candidate path ending at the destination station, and generating in the source station a series of route signals corresponding to the selected candidate path and changing the weight w o m of each switch link forming the candidate path; otherwise (f) return to step (d).
Claim 2
Independent Claim
434 words
A method of sending an electronic message from a source station through a network of a plurality of switches and links to a destination station, said method comprising: generating a series of one or more route signals, each route signal identifying an output port of a switch in the network of switches; compiling the series of route signals into an electronic message; and sequentially sending the message to each of a series of one or more switches, each switch reading a route signal in the message and sending the message to a component having an input port connected to an output port identified by the route signal; characterized in that the step of generating the series of route signals comprises the steps of: (a) storing in a location accessible to each said source station a weight w o m for each switch link connecting an output port of each of said switches to an input port of another of said switches, where m identifies the switch having an output port and o identifies the output port of that switch; (b) identifying one or more candidate paths through the switch network starting at the source station and ending at initial candidate destinations, each initial candidate destination comprising a component having an input port directly connected to an output port of a switch having an input port directly connected to the source station; (c) if one or more initial candidate destinations are the destination station, selecting a candidate path ending at the destination station, and generating in the source station a series of route signals corresponding to the selected candidate path, and changing the weight w o m of each switch link forming the candidate path; otherwise (d) identifying one or more extended candidate paths through the switch network starting at the source station and ending at next candidate destinations, each next candidate destination comprising a component having an input port directly connected to an output port of an immediately preceding candidate destination, each extended candidate path having a path weight comprising the weights of switch links along the candidate path; and then (e) if one or more candidate destinations are the destination station, selecting a candidate path ending at the destination station and having a path weight which is less than or equal to the path weight of each other candidate path ending at the destination station, and generating in the source station a series of route signals corresponding to the selected candidate path and changing the weight w o m of each switch link forming the candidate path; otherwise (f) return to step (d).
Claim 3
Dependent Claim
85 words
A method as claimed in claim 1, characterized in that each candidate path comprises: a series of one or more switches starting with the switch having an input port directly connected to the source station and ending with a switch having an output port directly connected to the candidate destination of the candidate path; a station link connecting the source station to an input port of the starting switch; and a station link connecting the output port of the ending switch to the destination station.
Claim 4
Dependent Claim
41 words
A method as claimed in claim 2, characterized in that each extended candidate path further comprises one or more switch links connecting an output port of a switch in the path with an input port of another switch in the path.
Claim 5
Dependent Claim
113 words
A method as claimed in claim 1, characterized in that: each pair of extended candidate paths contain a common root path extending from the source station to a common branch switch from which the paths diverge; the path weight of a first candidate path is less than the path weight of a second candidate path if the weight of the switch link of the first candidate path connected to an output of the common branch switch for the first and second candidate paths is less than the weight of the switch link of the second candidate path connected to an output of the common branch switch for the first and second candidate paths.
Claim 6
Dependent Claim
45 words
A method as claimed in claim 4, characterized in that the step of generating a series of route signals corresponding to the selected candidate path comprises generating a series of route signals identifying switch output ports connected to the links forming the selected candidate path.
Claim 7
Dependent Claim
52 words
A method as claimed in claim 5, characterized in that the step of storing weights for the switch links comprises storing an initial value K for the weight w o m for each switch link connected to an output port o m of a switch m, where K is a selected constant.
Claim 8
Dependent Claim
41 words
A method as claimed in claim 5, characterized in that the step of changing the weights of switch links forming the selected candidate path comprises increasing the weight of each switch link forming the selected candidate path by a constant K'.
Claim 9
Dependent Claim
13 words
A method as claimed in claim 7, characterized in that K=0 and K'=+1.
Claim 10
Dependent Claim
37 words
A method as claimed in claim 7, further comprising the steps of: storing the series of route signals in a route table; and generating the message by reading the series of route signals from the route table.
Claim 11
Dependent Claim
46 words
A method as claimed in claim 9, characterized in that: the destination station has an input port; and the last route signal in the series of route signals in the message identifies a switch output pork directly connected to the input port of the destination station.
Claim 12
Dependent Claim
96 words
A method as claimed in claim 10, characterized in that the step of sequentially sending the message comprises the steps of: (1) sending the message to a first switch having an input port directly connected to the source station, said first switch having at least two output ports; (2) reading a route signal in the message, said route signal identifying an output port of the first switch; and (3) sending the message to a second switch having an input port directly connected to the output port of the first switch identified by the read route signal.
Claim 13
Dependent Claim
24 words
A method as claimed in claim 11, further comprising the step of disabling the route signal in the message after reading the route signal.
Claim 14
Dependent Claim
31 words
A method as claimed in claim 1, characterized in that each extended candidate path has a path weight comprising the sum of the weights of switch links along the candidate path.
Claim 15
Independent Claim
332 words
A method of assigning a communication route from a source station through a network of a plurality of switches and links to a destination station, said method comprising: (a) storing in the source station a weight w o m for each switch link connecting an output port of each of said switches to an input port of another switch, where m identifies the switch having an output port and o identifies the output port of that switch; (b) identifying one or more candidate paths through the switch network starting at the source station and ending at initial candidate destinations, each initial candidate destination comprising a component having an input port directly connected to an output port of a switch having an input port directly connected to the source station; (c) if one or more initial candidate destinations are the destination station, selecting a candidate path ending at the destination station, generating in the source station a series of route signals corresponding to the selected candidate path, and changing the weight w o m of each switch link forming the selected candidate path; otherwise (d) identifying one ore more extended candidate paths through the switch network starting at the source station and ending at next candidate destinations, each next candidate destination comprising a component having an input port directly connected to an output port of an immediately preceding candidate destination, each extended candidate path having a path weight comprising the weights of switch links along the candidate path; and then (e) if one or more candidate destinations are the destination station, selecting a candidate path ending at the destination station and having a path weight which is less than or equal to the path weight of each other candidate path ending at the destination station, generating in the source station a series of route signals corresponding to the selected candidate path, and changing the weight w o m of each switch link forming the selected candidate path; otherwise (f) return to step (d).
Claim 16
Independent Claim
332 words
A method of assigning a communication route from a source station through a network of a plurality of switches and links to a destination station, said method comprising: (a) storing in the source station a weight w o m for each switch link connecting an output port of each of said switches to an input port of another switch, where m identifies the switch having an output port and o identifies the output port of that switch; (b) identifying one or more candidate paths through the switch network starting at the source station and ending at initial candidate destinations, each initial candidate destination comprising a component having an input port directly connected to an output port of a switch having an input port directly connected to the source station; (c) if one or more initial candidate destinations are the destination station, selecting a candidate path ending at the destination station, generating in the source station a series of route signals corresponding to the selected candidate path, and changing the weight w o m of each switch link forming the selected candidate path; otherwise (d) identifying one ore more extended candidate paths through the switch network starting at the source station and ending at next candidate destinations, each next candidate destination comprising a component having an input port directly connected to an output port of an immediately preceding candidate destination, each extended candidate path having a path weight comprising the weights of switch links along the candidate path; and then (e) if one or more candidate destinations are the destination station, selecting a candidate path ending at the destination station and having a path weight which is less than or equal to the path weight of each other candidate path ending at the destination station, generating in the source station a series of route signals corresponding to the selected candidate path, and changing the weight w o m of each switch link forming the selected candidate path; otherwise (f) return to step (d).
Claim 17
Dependent Claim
94 words
A method as claimed in claim 14, characterized in that each candidate path comprises: a series of one or more switches starting with a switch having an input port directly connected to the source station and ending with a switch having an output port directly connected to the candidate destination of the candidate path; a station link connecting the source station to an input port of the switch having an input port directly connected to the source station; and a station link connecting the output port of the ending switch to the destination station.
Claim 18
Dependent Claim
41 words
A method as claimed in claim 15, characterized in that each extended candidate path further comprises one or more switch links connecting an output port of a switch in the path with an input port of another switch in the path.
Claim 19
Dependent Claim
113 words
A method as claimed in claim 16, characterized in that: each pair of extended candidate paths contain a common root path extending from the source station to a common branch switch from which the paths diverge; the path weight of a first candidate path is less than the path weight of a second candidate path if the weight of the switch ink of the first candidate path connected to an output of the common branch switch for the first and second candidate paths is less than the weight of the switch link of the second candidate path connected to an output of the common branch switch for the first and second candidate paths.
Claim 20
Dependent Claim
44 words
A method as claimed in claim 17, characterized in that the step of generating a series of route signals corresponding to the selected candidate path comprises generating a series of route signals identifying switch output ports connected to the links forming the selected candidate
Claim 21
Dependent Claim
52 words
A method as claimed in claim 18, characterized in that the step of storing weights for the switch links comprises storing an initial value K for the weight w o m for each switch link connected to an output port o m of a switch m, where K is a selected constant.
Claim 22
Dependent Claim
41 words
A method as claimed in claim 19, characterized in that the step of changing the weights of switch links forming the selected candidate path comprises increasing the weight of each switch link forming the selected candidate path by a constant K'.
Claim 23
Dependent Claim
13 words
A method as claimed in claim 20, characterized in that K=0 and K'=+1.
Claim 24
Dependent Claim
37 words
A method as claimed in claim 14, further comprising the steps of: storing the series of route signals in a route table; and generating the message by reading the series of route signals from the route table.
Claim 25
Dependent Claim
46 words
A method as claimed in claim 22, characterized in that: the destination station has an input port; and the last route signal in the series of route signals in the message identifies a switch output port directly connected to the input port of the destination station.
Claim 26
Dependent Claim
31 words
A method as claimed in claim 23, characterized in that each extended candidate path has a path weight comprising the sum of the weights of switch links along the candidate path.
Claim 27
Dependent Claim
13 words
A method as claimed in claim 1, wherein said component is a switch.
Claim 28
Dependent Claim
13 words
A method as claimed in claim 1, wherein said component is a station.
Claim 29
Dependent Claim
13 words
A method as claimed in claim 14, wherein said component is a switch.
Claim 30
Dependent Claim
13 words
A method as claimed in claim 14, wherein said component is a station.
References Cited (Backward Citations)
US4814979A
Cited
US4466060A
Cited
US4814973A
Cited
US5016163A
Cited
US4905233A
Cited
US4987536A
Cited
US4873517A
Cited
US5166927A
Cited
US5034945A
Cited
US5115495A
Cited
US4995035A
Cited
US4993016A
Cited
US5142531A
Cited
US5130977A
Cited
US5140583A
Cited
US5115433A
Cited
US4939726A
Cited
US5056085A
Cited
EP0426911A1
Cited
US5014262A
Cited
US5083265A
Cited
US5128932A
Cited
US5243592A
Cited
JPH04167845A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-10-10 | 1998-04-11 | 1998-10-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-10 | 2002-04-11 | 2002-10-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-10 | 2006-04-11 | 2006-10-11 | $7700.00 | Window Closed / Lapsed |