Routing architecture for a multi-ring local area network

• US 4,621,362 A
• Filed: 06/04/1984
• Issued: 11/04/1986
• Est. Priority Date: 06/04/1984
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sy, Kian-Bon K.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Rokoff, Kenneth I.
• Application Number:
  US06/616,742
• Time in Patent Office: 883 Days
• Field of Search: 370/88, 370/89, 370/14, 370/99, 370/94, 340/825.05
• US Class Current: 370/403
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/4637 Interconnected ring systems

Abstract

The architecture provides a frame format and procedure for routing messages through a single ring or multi-ring communication system. Stations associated with the exchange of messages are located on the single ring or on different rings of the multi-ring communication system. The rings are connected by bridges to form a local area network. The frame format includes a plurality of control bits positioned within a Routing Information (RI) field, a frame control field and a frame status field. Messages are generated and structured in accordance with the frame format. A group of the control bits, in each message, is set with initial values according to the message type. Thus, different messages are characterized by a different sequence of control bit settings. A routing algorithm analyzes the message and depending on the status of the control bits, the message is processed and ultimately switched to its proper destination.

Claims

1. In a telecommunication network system wherein a plurality of serial loop networks are being interconnected by a plurality of bridges and each serial loop having one or more utilization stations connected thereto a method for routing frames between stations comprising the steps of:

(a) transmitting from a source station through the loop connected to it, a frame including a first indicia having at least two states and Routing Information (RI) field;

said RI field including one or more routing addresses adaptable for identifying the bridges through which the frame is being routed, a pointer (PTR) field for identifying the order in which the bridges will process the frame and a Length (LTH) field for indicating the length of the RI field;

(b) receiving the frame at a bridge;

(c) determining the position of the bridge relative to the order in which the bridges process the frame;

(d) incrementing the value of the pointer field only if the frame is accessing the bridges in an ascending order;

(e) decrementing the value of the pointer field only if the frame is accessing the bridges in a descending order; and

(f) retransmitting at the next opportunity given to the bridges by the network the frame including the adjusted pointer field whereby the steps recited in (b)-(f) above are being repeated at the bridges whose identify appears in the RI field until the last bridge in said field receives the frame with the pointer being set to a predetermined value, thus indicating that said bridge is at a target ring.

2. The method recited in claim 1 further including the step of forwarding the frame to the target ring from whence it is being removed by a target station.

3. The method recited in claim 1 wherein the RI field further includes a second indicia having at least two states.

4. The method recited in claim 3 further including the steps of:

(g) receiving the frame at a target station;

(h) examining the second indicia for determining the state of said second indicia;

(j) complementing the second indicia so that said indicia is being set to the opposite state; and

(k) setting the PTR to a different value, said value indicating the identity of the first bridge through which the frame is being routed, thereby allowing a common frame to shuttle messages throughout the network without rearranging the relative order of the bridges in the RI field.

5. The method of claim 4 wherein step (j) further including the steps of:

(i) comparing the identification number of the bridge with the number identified by the pointer;

(ii) examining the second indicia only if the bridge number matches the number in the RI field;

(iii) comparing the value in the PTR field with a range of predetermined values; and

(iv) characterizing the bridge as being on the ring with the initiating station only if the value in the PTR field is equivalent to one of the predetermined values.

6. In a telecommunication network system wherein a plurality of serial loop networks are being interconnected by a plurality of bridges and each serial loop having one or more utilization stations connected thereto a method for routing frames between stations comprising the steps of:

(a) transmitting from a source station through the loop connected to it, a frame including a first indicia having at Jeast two states and a Routing Information (RI) field;

said RI field including one or more routing addresses adaptable for identifying the bridges through which the frame is being routed, a point (PTR) field for identifying the next bridge to process the frame and a Length (LTH) field for indicating the length of the RI field;

(b) receiving the frame at a bridge connected to the loop; and

examining the first indicia for determining the state of said first indicia;

(c) determining the position of the bridge relative to the route;

(d) incrementing the value of the pointer field only if the frame is accessing the bridges in an ascending order;

(e) decrementing the value of the pointer field only if the frame is accessing the bridges in the opposite order; and

(f) retransmitting at the next opportunity given to the bridges by the network the frame including the adjusted pointer field whereby the steps recited in (c)-(f) above are being repeated successively at the bridges whose identify appears in the RI field until the last bridge in said field receives the frame with the pointer being set to a predetermined value, thus indicating that said bridge is at a target ring.

7. The method recited in claim 6 wherein steps (c)-(f) are being performed only if the first indicia is set to a first state.

10. The method recited in claim 7 further including the step of setting the second indicia at one of the switching stations.

8. A method for routing information through a network having a plurality of independently interconnected rings comprising the steps of:

(a) transmitting from a source station a frame having a first indicia set to a first state, a second indicia having at least two states and a Routing Information (RI) field;

said RI field further characterized by an LTH field for containing data representative of the size of the RI field, a PTR field, at least one two-state indicia and an address space for carrying the addresses of switching stations;

(b) receiving the frame at a switching station and examining the first indicia for determining the state of said first indicia;

(c) analyzing the RI field only if the first indicia is set to the first state;

(d) incrementing the value of the PTR only if the two state indicia of the RI field is being set to a predetermined value and the PTR is being set to a first predetermined value;

(e) retransmitting the frame;

(f) receiving the frame at a switching station identified by the PTR value;

(g) incrementing the PTR value only if the PTR is being set to a second predetermined value;

(h) retransmitting the frame and repeating steps (f)-(h) successively at the switching stations whose address appears in the address space until the last switching station identified in said address space receives the frame with the PTR value being set to a third predetermined value, thus indicating that said frame has arrived at the target ring.

9. The method recited in claim 8 further including the steps of:

(i) receiving the frame at a target station; and

(j) resetting the received two state indicia in the RI field to its opposite state and resetting the PTR to a different value thereby forming an adjusted frame for carrying information without changing the order of the switching stations within the address space.

11. The method of claim 9 further including the steps of:

(k) transmitting the adjusted frame in step (j);

(l) receiving the adjusted frame at a switching station identified by the PTR value;

(m) decrementing the PTR value only if the two state indicia is being set to a predetermined state and the PTR is being set to a fourth predetermined value;

(n) retransmitting the adjusted frame;

(o) receiving the adjusted frame at a switching station identified by the PTR value;

(p) decrementing the PTR value only if the receive PTR value is being set to a fifth predetermined value; and

(q) retransmitting the frame and repeating steps (e)-(g) successively at the switching stations whose address appears in the address space until the last switching station identified in said address receives the frame.

12. In a telecommunication network system wherein a plurality of serial loop networks are being interconnected by a plurality of switching stations and each serial loop having one or more utilization stations connected thereto a method for routing frames between stations comprising the steps of:

(a) generating and transmitting from a source station a frame having at least a Routing Information field;

said Routing Information field including an LTH field, an indicia having at least two states, a PTR field and an address space having one or more switching station addresses;

(b) receiving the frame at the switching station identified by the PTR;

(c) adjusting the value of the PTR only if the indicia is in a first state and the PTR is being set to a first predetermined value;

(d) retransmitting the frame;

(e) receiving the frame at a switching station identified by the PTR;

(f) adjusting the value of the PTR only if the PTR is being set to a second predetermined value;

(g) retransmitting the frame and repeating steps (e)-(g) successively at the switching stations whose addresses appear in the address space until the last identified switching station receives the frame.

13. In a telecommunication network system wherein a plurality of serial loop networks are being interconnected by a plurality of switching stations and each serial loop having one or more stations thereon, a method for obtaining the addresses of the switching stations through which a message is to be routed comprising the steps of:

(a) generating and transmitting from a source station a frame including the address of a destination station and an RI field, said RI field having at least a two-state indicia set to a first state, an LTH field set to a predetermined value;

(b) receiving the frame at a switching station;

(c) writing the address of the switching station in the frame at a location identified by the LTH field only if the value of the LTH field is less than a Hop-count or the address of the switching station is not recorded in the frame;

(d) adjusting the LTH field value;

(e) retransmitting the frame; and

(f) repeating steps (b)-(f) until the frame is received at the destination station.

14. The method recited in claim 13 further including the steps of:

(g) resetting the two state indicia in the receive frame to the opposite state;

(h) setting predetermined values in the LTH field and a PTR field; and

(i) utilizing the accumulated addresses as the routing Path for subsequent exchange of messages between the stations.

15. The method of claim 13 wherein step (d) is being Performed by incrementing the value of the LTH field.

16. In a telecommunication network system wherein a plurality of serial loop networks are being interconnected by a plurality of switching stations and each serial loop having one or more stations thereon a method for using a single copy of a message to identify the routing path for a selected station comprising the steps of:

(a) generating and forwarding from a source station a frame including the selected station address, a source address and an RI field;

said RI field including two two-state control indicia, each being set to a common predetermined value;

(b) receiving the frame at a switching station;

(c) examining the RI field to determine the state of the two indicia;

(d) writing the identification number of the switching station in the location identified by an LTH field only if the two indicia are being set to a common predetermined value;

(e) adjusting the length (LTH) field value;

(f) forwarding the frame; and

(g) repeating steps b-g until the value of the LTH field exceeds a Hop-count setting of a switching station or the address of the station is already recorded in the RI field.

17. In a digital communication network wherein a plurality of data terminal equipment (DTE) are coupled to a serial transmission path means and a plurality of the serial transmission path means are interconnected by one or more switching stations, a message transport mechanism for carrying messages within the network comprising:

a frame code signal generating means disposed within the DTE and adapted to generate the message transport mechanism;

said message transport mechanism having at least a Routing Information (RI) field divided into a control (C) section adapted for carrying control information and a routing section adapted for carrying the identity of the switching stations through which the message is to be routed;

a first two-state indicia disposed outside of the RI field and operable for indicating the presence of the RI field when it is set in a predetermined state; and

a second set of two-state indicia disposed outside of the RI field and operable for indicating that the message has passed through the last switching station when it is set in a predetermined state.

18. The message transport mechanism of claim 17 wherein the control (C) section includes a third two-state indicia operable to indicate the type of message;

a fourth set of indicia operable to carry a value representing the length of the RI field;

a fifth two-state indicia operable to indicate the direction in which a message moves relative to initiating a DTE and a sixth set of bits operable to identify the next switching station which will process said message.

19. The message transport mechanism of claim 18 further including means disposed at the switching station and operable to analyze the contents of the message transport and to route the message according to the setting of the indicia.

20. In a communications network system wherein a plurality of serial loop networks are being coupled by a plurality of switching stations and each serial loop network having one or more utilization stations connected thereto a method for routing frames between stations connected to different loop networks comprising the steps of:

(a) transmitting from a source station through the loop connected to said source station a frame including a Routing Information (RI) field;

said RI field including one or more routing addresses operable for identifying the switching stations through which the frame is being routed, a pointer (PTR) field operable for identifying the switching station that will next forward the frame and a first indicium having at least two states;

(b) receiving the frame at a switching station;

(c) examining the first indicium;

(d) incrementing the pointer field only if the first indicium is being set to a first predetermined state;

(e) decrementing the pointer field only if the first indicia is being set to a second predetermined state; and

(f) retransmitting at the next opportunity given to the switching station by the network the frame including an adjusted pointer field whereby steps (b)-(d) are being repeated by each of the switching stations having addresses within the RI field until the last switching station in said RI field receives the frame thereby indicating that said frame is at a target loop network.