Alternate routing arrangement

• US 4,679,189 A
• Filed: 11/27/1985
• Issued: 07/07/1987
• Est. Priority Date: 11/27/1985
• Status: Expired due to Term

• Current Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Original Assignee: American Telephone & Telegraph Company (AT&T, Inc.), AT&T Information Systems Inc. (AT&T, Inc.)
• Inventors: Olson, Jeffrey J., Seaton, David P., Peck, Stephen R.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Scutch, III, Frank M.
• Application Number:
  US06/802,573
• Time in Patent Office: 587 Days
• Field of Search: 370/60, 370/64, 370/16
• US Class Current: 370/396
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

Improved alternate routing in a packet switching system is provided by inserting alternate routing control information into each packet and by storing alternate routing information at each network node. The stored information at each node includes a list of the available paths extending from the node towards all other nodes together with a list of available algorithms that can be used to select one of the available routes. The alternate routing control information in each packet contains postage information specifying the maximum number of nodes through which the packet is to travel. The alternate routing control information also includes a destination node index code identifying the destination node. The destination node index is used as address information by each node receiving a packet to read out the stored information at the node identifying the available paths and the algorithm to be used in selecting one of these paths for use in transmitting the packet towards the destination node. The identified algorithm is then executed to select the path to be used.

Claims

1. A method for providing for the alternate routing of messages transmitted from an originating node to a destination node in a packet switching system having a plurality of nodes wherein each node stores routing information, said method comprising the steps of:

(A) inserting a message to be transmitted into a first field of a multifield frame,

(B) inserting alternate routing control control into a second field of said frame,

(C) transmitting said frame from said originating node over a path towards said destination node via an intermediate node,

(D) using said alternate routing control information in said transmitted frame to access said stored routing information at said intermediate node specifying a plurality of paths available for transmitting said frame from said intermediate node towards said destination node,

(E) selecting one of said specified paths under control of said stored routing information, and

(F) transmitting said message frame from said intermediate node towards a destination node via said selected specified path.

2. The method of claim 1 wherein said frame further comprises a logical channel index and wherein said method further comprises the steps of:

(A) receiving said frame at said destination node, and

(B) using said logical channel index in said frame received at said destination node to specify the one of a plurality of applications at said destination node to which the message of said frame is directed.

3. A method for providing for the alternate routing of messages transmitted from an originating node to a destination node in a packet switching system having a plurality of nodes wherein each node stores routing information, said method comprising the steps of:

(A) inserting a message to be transmitted into a first field of a multifield frame,

(B) inserting alternate routing control information into a second field of said frame,

(C) transmitting said frame from said originating node over a path towards said destination node via one or more intermediate nodes,

(D) using said alternate routing control information in said transmitted frame at each intermediate node receiving said frame to access said stored routing information of each said intermediate node specifying a plurality of paths available for transmitting said frame from each said intermediate node towards said destination node,

(E) selecting at each said intermediate node one of said specified paths under control of said stored routing information at each said intermediate node, and

(F) transmitting said message frame from each said intermediate node towards said destination node via said specified path selected at each said intermediate node.

4. The method of claim 3 wherein said frame further comprises a logical channel index and wherein said method further comprises the steps of:

(A) receiving said frame at said destination node, and

(B) using said logical channel index in said frame received at said destination node to specify the one of a plurality of applications at said destination node to which the message of said frame is directed.

5. The method of claim 3 wherein said alternate routing control information inserted into said frame, further comprises postage information specifying the number of nodes through which said frame may travel and wherein said method further comprises the steps of:

(A) comparing said postage information with zero each time a frame is received by an intermediate node,

(B) aborting said frame if said compared amount is zero,

(C) decrementing said postage information if said compared amount is not equal to zero, and

(D) inserting said decremented amount into said frame prior to transmission of said frame from said intermediate node.

6. A method for providing for the alternate routing of messages transmitted from an originating node to a destination node in a packet switching system having a plurality of nodes wherein each node stores routing information, said method comprising the steps of:

(A) inserting a message to be transmitted into a first field of a multifield frame,

(B) inserting alternate routing control information into a second field of said frame,

(C) transmitting said frame from said originating node over a path towards said destination node via one or more intermediate nodes,

(D) using said alternate routing control information in said transmitted frame at each intermediate node receiving said frame to access said stored routing information at each said intermediate node specifying a plurality of paths and an algorithm to be used to select one of said plurality of paths for use in transmitting said frame from each said intermediate node towards said destination node,

(E) executing the specified algorithm at each said intermediate node to select one of said specified paths at each said intermediate node, and

(F) transmitting said message frame from each said intermediate node towards said destination node via said specified path selected at each said intermediate node.

7. The method of claim 6 wherein said frame further comprises a logical channel index and wherein said method further comprises the steps of:

(A) receiving said frame at said destination node, and

(B) using said logical channel index in said frame received by said destination node to specify the one of a plurality of applications at said destination node to which the message of said frame is directed.

8. The method of claim 6 wherein said alternate routing control information inserted into said frame further comprises postage information specifying the number of nodes through which said frame may travel and wherein said method further comprises the steps of:

(A) comparing said postage information with zero each time a frame is received by an intermediate node,

(B) aborting said frame if said compared amount is zero,

(C) decrementing said postage information if said compared amount is not equal to zero, and

(D) inserting said decremented amount into said frame prior to transmission of said frame from said intermediate node.

9. The method of claim 6 wherein said path comprises a data link and a logical channel.

10. The method of claim 9 wherein each of said nodes comprises a host processor and a packet switch interconnected by a path.

11. A method for providing for the alternate routing of messages transmitted from an originating node to a destination node in a packet switching system having a plurality of nodes wherein each node stores routing information, said method comprising the steps of:

(A) inserting a message to be transmitted into a first field of a multifield frame structured to define a layered protocol,

(B) inserting alternate routing control information into a second field of said frame to define an alternate routing protocol layer for said frame, said alternate routing control information comprising a destination map index subfield,

(C) transmitting said frame from said originating node towards said destination node via more than one intermediate nodes,

(D) identifying the path by which each frame arrives at each one of said nodes to which it is transmitted,

(E) determining from said identification and from said stored information at at least one of said intermediate nodes receiving said frame that said frame is not to be alternate routed and is to be routed out from said one intermediate node via a path specified solely by the path on which said frame arrives at said one intermediate node,

(F) determining from said identification and from the arrival of said frame on a path at another one of said intermediate nodes that said frame is to be alternate routed,

(G) using said last named determination and said destination map index of said received frame as address information to read out stored information at said other intermediate node identifying a plurality of paths and an algorithm to be used in specifying one of said identified paths,

(H) executing said identified algorithm to specify one of said identified paths, and

(I) transmitting said message frame from each of said intermediate nodes towards said destination node via the path specified for use at each of said intermediate nodes.

12. The method of claim 11 wherein each of said paths comprises a data link and a logical channel.

13. The method of claim 11 wherein said alternate control routing field information further comprises a logical channel index subfield and wherein said method further comprises the steps of:

(A) transmitting said frame from one of said intermediate nodes receiving said frame to said destination node, and

(B) using said logical channel index subfield in said frame received by said destination node to specify the one of a plurality of applications at said destination node to which the message of said frame is directed.

14. The method of claim 11 wherein said alternate routing control information further comprises a postage information subfield specifying the number of nodes through which said frame may travel and wherein said method further comprises the steps of:

(A) comparing said postage subfield with zero each time a frame is received by an intermediate node,

(B) aborting said frame if said compared amount is zero,

(C) decrementing said postage subfield if said compared amount is not equal to zero, and

(D) inserting said decremented amount into said postage field of said frame prior to transmission from said intermediate node.

15. The method of claim 14 wherein each of said nodes comprises a host processor and a packet switch interconnected by a path.

16. A method for providing for the alternate routing of messages transmitted from an originating node to a destination node in a packet switching system having a plurality of nodes wherein certain ones of said nodes store routing information, said method comprising the steps of:

(A) inserting said message into a first field of a multifield frame structured to define a layered protocol,

(B) inserting alternate routing control information into a second field of said frame to define an alternate routing protocol layer for said frame, said alternate routing information comprising a destination map index subfield,

(C) transmitting said frame from said originating node towards said destination node via two or more intermediate nodes,

(D) identifying the path by which said frame arrives at each one of said nodes to which it is transmitted,

(E) determining from said path identification at one of said intermediate nodes receiving said frame that said frame is not to be alternate routed and is to be routed out from said one intermediate node via a path specified solely by the path on which said frame arrives at said one intermediate node,

(F) transmitting said frame from said one intermediate node towards said destination node via said specified path,

(G) determining from said identification at another intermediate node receiving said frame that said frame is to be alternate routed,

(H) using said last named determination and said destination map index of said received frame as address information to read out stored information from said other intermediate node identifying a plurality of paths and an algorithm to be used in selecting one of said identified paths,

(I) executing said identified algorithm to select one of said identified paths, and

(J) transmitting said frame from said other intermediate node towards said destination node via said selected path.

17. The method of claim 16 wherein said alternate control routing information inserted into said frame further comprises a postage information subfield specifying the number of nodes through which said frame may travel and wherein said method further comprises the steps of:

(A) comparing said postage subfield with zero each time a frame is received by an intermediate node,

(B) aborting said frame if said compared amount is zero,

(C) decrementing said compared amount if said compared amount is not zero, and

(D) inserting said decremented amount into said postage field of said frame prior to transmission from said intermediate node if said compared amount is not zero.

18. The method of claim 17 wherein said alternate routing control information further comprises a logical channel index subfield and wherein said method further comprises the steps of:

(A) transmitting said frame from one of said intermediate nodes to said destination node, and

(B) using said logical channel index subfield in said frame received by said destination node to specify the one of a plurality of applications at said destination node to which the message of said frame is directed.

19. The method of claim 18 wherein each of said paths comprises a data link and a logical channel.

20. The method of claim 19 wherein each of said nodes comprises a host processor and a packet switch interconnected by a path.

21. A method for providing for the alternate routing of messages transmitted from an originating to a destination node in a packet switching system having a plurality of nodes wherein each node stores routing information and wherein each node comprises a host processor and a packet switch interconnected by a path, said method comprising the steps of:

(A) generating message information and alternate routing control information and destination node information in the host processor of said originating node,

(B) transmitting said information from said host processor over said path to the packet switch of said originating node,

(C) operating said packet switch at said originating node to insert said message information into a first field of a multifield frame structured to define a layered protocol,

(D) operating said packet switch at said originating node to insert said alternate routing control information into a second field of said frame to define an alternate routing protocol layer for said frame, said alternate routing control information comprising a destination map index subfield,

(E) transmitting said frame from said originating node towards said destination node via at least one intermediate node,

(F) identifying the path by which each frame arrives at each one of said intermediate nodes to which it is transmitted,

(G) determining from said identification at an intermediate node receiving said frame that said frame is to be alternate routed,

(H) using said last named determination and said destination map index of said received frame as address information to read out stored information from said intermediate node identifying a plurality of paths and an algorithm to be used in selecting one of said identified paths,

(I) executing said identified algorithm to select one of said identified paths, and

(J) transmitting said frame from said intermediate node towards said destination node via said selected path.

22. The method of claim 21 wherein said host processor at said originating node also generates destination node application information that is transmitted over said path to the packet switch of said originating node and wherein said alternate routing field control information further comprises a logical channel index subfield containing said destination node application information, said method further comprising the steps of:

(A) transmitting said frame from one of said intermediate nodes to said destination node, and

(B) using said logical channel index subfield in said frame received by said destination node to specify the one of a plurality of applications at said destination node to which the message of said frame is directed.

23. The method of claim 22 wherein said alternate routing control information generated by said host processor at said originating node includes postage information that is transmitted over said path to the packet switch of said originating node and wherein said alternate routing field information further comprises a postage subfield containing said postage information specifying the number of nodes through which said frame may travel, said method further comprising the steps of:

(A) comparing said postage information with zero each time a frame or message information is received by a node,

(B) aborting said frame or said information if said compared amount is zero,

(C) decrementing said postage information if said compared amount is not zero, and

(D) inserting said decremented amount into said postage field of said frame prior to transmission from said node if said compared amount is not zero and if said last named node is not said destination node.

24. The method of claim 23 wherein each of said paths comprises a link and a logical channel.

25. The method of claim 24 wherein said method further comprises the steps of:

(A) operating the packet switch of each node receiving a frame to use the destination index field of each received frame to determine whether the received frame specifies each said node as the destination node of said packet,

(B) transmitting said message field of said received said frame to the host processor of each said node if said node is the specified destination node, and

(C) transmitting said frame out over a specified path towards said destination node if each said node is not said destination node.

26. The method of claim 21 wherein there are a plurality of available algorithms at each node and wherein said step of identifying includes the step of identifying one of said plurality of available algorithms.

27. The method of claim 21 wherein said readout of said stored information at a node includes information specifying the number of available paths that are available to transmit said frame.

28. A method for providing for the alternate routing of messages transmitted from a host processor at an originating node to a destination node in a packet switching system having a plurality of nodes wherein each node stores routing information, said method comprising the steps of:

(A) inserting a message to be transmitted into a first field of a multifield frame,

(B) inserting alternate routing control information into a second field of said frame,

(C) transmitting said frame from said host processor at said originating node to a packet switch at said originating node,

(D) using said alternate routing control information in said transmitted frame to access said stored routing information at said originating node specifying a plurality of paths available for transmitting said frame from said originating node towards said destination node,

(E) selecting one of said specified paths under control of said stored routing information, and

(F) transmitting said message frame from said originating node towards a destination node via said selected specified path.

29. The method of claim 28 wherein said method further comprises the steps of:

(A) receiving said frame transmitted by said originating node at a node intermediate said originating node and said destination node,

(B) using said alternate routing control information in said transmitted frame to access said stored routing information at said intermediate node specifying a plurality of paths available for transmitting said frame from said intermediate node towards said destination node,

(C) selecting one of said specified paths under control of said stored routing information, and

(D) transmitting said message frame from said intermediate node towards a destination node via said selected specified path.