CN100555992C - Based on network routing scheme - Google Patents

Abstract

Network-based routing scheme. A network organization and routing scheme is provided. These techniques allow the network to control the path that frames take through the network. A device sending a frame can add a tag to the frame to define the specific path that the frame should take through the network. For example, these labels can represent link-by-link paths between multiple switches in the network. As another example, a network can be organized into one or more groups of switches, each group and switches within a group have a unique identifier, so that for any given switch or port.

Description

Network-Based Routing Scheme

technical field

The present invention relates generally to network communications, and more particularly to a network-based routing scheme.

Background technique

In a network, switches route frames between different network elements. To route frames, switches typically use an Ethernet routing protocol that enables the switch to perform routing based on a dynamic learning algorithm.

Contents of the invention

According to the present invention, techniques for network-based routing schemes are provided. According to particular embodiments, these techniques describe routing schemes and network organizations that enable a private network to control the path a frame takes through the private network.

According to a particular embodiment, a method for routing a frame comprises the step of using a set of ports of a switch to receive the frame. Each frame includes a source address, a destination address, and a payload. At least some of the frames also include one or more labels, where each label specifies a group identification, a switch identification, and a port identification. The switch is part of a switch group which is part of a switching network. The method also includes the step of maintaining in the switch routing information representing output ports corresponding to each other switch in the group of switches. For each frame, if the frame complies with a particular routing protocol, the method includes the step of operating in a first mode of operation, otherwise the method includes the step of operating in a second mode of operation. In the first mode of operation, the first tag in the frame is read. It is determined whether the switch identification of the first label corresponds to the switch. If the switch identification does not correspond to the switch, accessing the routing information to determine an output port corresponding to the switch identification and sending the output port on the determined port of the plurality of ports frame. If the switch identification corresponds to the switch, sending the frame on a port corresponding to the port identification of the first label. In a second mode of operation, the frames are processed according to a standard routing protocol.

Embodiments of the present invention provide various technical advantages. For example, these techniques may allow a device to specify a particular path a frame should take through a private network. These dedicated routing techniques can work in conjunction with widely used routing techniques such as Ethernet routing. For example, within a private network, a switch may use a private network routing protocol instead of Ethernet routing for selected network traffic. In certain embodiments, the switches within the private network are divided into groups, and a particular port of a particular switch of the plurality of switches can be uniquely referenced by a label representing the group, switch, and port identifier. This allows switches within a group to maintain private routing tables defined only for other switches in the group. In some embodiments, proper routing can be achieved using smaller routing tables that require less memory in the switch. Furthermore, in certain embodiments, a frame entering a private network may be tagged to ensure that responses to the frame leave the private network on the exact same port.

Other technical advantages of the present invention can be readily conceived by those skilled in the art from the following figures, descriptions and claims. Furthermore, while specific advantages have been enumerated above, various embodiments may include all, some, or none of the enumerated advantages.

Description of drawings

For a more complete understanding of the invention and its advantages, reference is made to the following description taken in conjunction with the accompanying drawings, in which:

Figure 1 illustrates a system for controlling the path of frames through a switching network using a network-based routing scheme;

2A to 2C illustrate a group of switches adopting a network-based routing scheme in a switching network and a table storing routing information held by one of these switches;

3A to 3C illustrate the path of an outbound (outbound) frame and the corresponding structure of the frame when passing through various switches in the switching network;

Figure 4 is a flowchart illustrating a method for processing network management messages received at a switch in a switched network; and

Figure 5 is a flowchart illustrating a method for processing frames received at a switch in a switching system.

Detailed ways

Figure 1 illustrates a system (generally indicated at 10) that uses a network-based routing scheme to control the path of frames through a switching network. As illustrated, system 10 includes switching network 12 , management device 14 , network device 16 , Internet 18 , and external network 20 . The various elements of system 10 may be interconnected using any suitable technology or protocol. Generally, elements within system 10 interoperate to control the path that frames take through switching network 12 .

Switching network 12 includes switches 22 and represents any suitable collection of hardware, software, and control logic that interconnects switches 22 with elements coupled to switching network 12 . Thus, switching network 12 provides an infrastructure that supports communication between attached devices. As illustrated, switching network 12 includes a plurality of switches 22 organized into a plurality of groups 24 . In some embodiments, switched network 12 is a dedicated network that allows devices to specifically determine the path of frames through the network.

Switch 22 represents a network connection device that routes frames within a network and/or between different networks. According to a particular embodiment, each switch 22 represents a network device with a plurality of ports capable of switching network traffic between the ports. For example, switches 22 may each represent a chip-type switching device capable of exchanging frames between multiple ports based on a standard Ethernet protocol. However, as used and described herein, switch 22 may comprise a switch, router, or any suitable network device capable of interconnecting multiple network elements. Furthermore, switches 22 may communicate within switching network 12 using any suitable technique or protocol for communicating. Additionally, as discussed in more detail below, switch 22 implements a network-based routing scheme to allow source routing of frames traversing switching network 12 .

As illustrated, multiple switches 22 are grouped into multiple groups 24 . Switching network 12 may include one or more groups 24 , and each group 24 may include one or more switches 22 . Within a group 24, a plurality of constituent switches 22 may be interconnected in any configuration using any suitable technique or protocol. At boundaries between groups 24 , switches 22 in one group 24 may be connected to switches 22 in another group 24 . This provides intra-group and external links. As further illustrated, the switch 22 is also connected to the management device 14 , the network device 16 , the Internet 18 , the external network 20 . It should be understood from this illustration that switch 22 may be connected to any suitable network or device. As illustrated, the switching network 12 includes three groups 24: Group X, Group Y, and Group Z. Group X includes 3 switches 22: switch X.A, switch X.B and switch X.C. Group Y also includes three switches 22: switch Y.A, switch Y.B and switch Y.C. Group Z comprises 4 switches 22: switch Z.A, switch Z.B, switch Z.C and switch Z.D. This specific composition is given for purposes of illustration, but it should be understood that switching network 12 may include any suitable grouping of switches 22 .

In some embodiments, each group 24 is assigned a unique identifier within the switching network 12 . In the illustrated embodiment, each group 24 has a unique identifier: X, Y or Z. In particular embodiments, each switch 22 in a particular group 24 is assigned a unique identifier within that particular group 24 . The identifier of a particular switch 22 in one group 24 may be shared by different switches 22 in a different group 24 . For example, switch X.A and switch Y.A share a common switch identifier A, but they are each identifiable because they have different group identifiers X and Y. Additionally, each switch 22 may have multiple ports. Thus, within the switched network 12, a particular port can be uniquely referenced through the use of a group/switch/port identifier. For example, X.A.5 uniquely refers to port 5 on switch A in group X. Furthermore, within a particular group 24, a particular port may be uniquely referenced simply by using a switch/port identifier. For example, within group X, A.5 may uniquely refer to port 5 on switch X.A.

Furthermore, the routing information within a particular group 24 may be limited only for that particular group 24 . In some embodiments, the network routing information is stored in a network routing table. The network routing table for each constituent switch 22 in a particular group 24 may only provide routing information for other switches 22 in that particular group 24 . In a particular embodiment, the network routing table maintains routing information based on switch/port identifiers. This enables smaller table sizes and simpler lookup mechanisms, since switches 22 in one group 24 do not have to maintain routing information for switches 22 in other groups 24 . Each switch 22 may also maintain basic routing information for other groups 24 in the switching network 12 . For example, each switch 22 in group X may maintain a routing table entry specifying a particular port for frames addressed to group Y. In certain embodiments, this enables proper routing without lengthy routing tables. Although the routing information is described as being stored as a table, it should be understood that the routing information may be stored in any suitable manner, including databases, files, hash tables, and the like. One embodiment of selected routing information stored by switch 22 is further described below with reference to FIGS. 2A through 2C. In addition, although not explicitly illustrated or described in detail, switch 22 may also maintain other routing information, such as an Ethernet routing table. Thus, switch 22 may use a network-based routing scheme for selected network traffic, while using another routing scheme for other network traffic.

In operation, the devices may use the tags in the frames to control the path of the frames through the switching network 12 . A frame may include header information indicating that the frame contains these tags. In some embodiments, there are two types of tags: inbound tags and outbound tags. Inbound tags may be used, for example, when a frame enters switching network 12 to ensure that a response to the frame is sent from switching network 12 on the same port on which the frame was originally received. When an inbound frame enters switching network 12 at a particular port, receiving switch 22 may add an inbound tag representing the group/switch/port that received the frame. In a particular embodiment, switch 22 only adds inbound tags to frames that switch 22 receives from outside switching network 12 .

For example, in the illustrated embodiment, the switch Z.C may receive a frame from the external network 20 destined for the management device 14 . Switch Z.C may add an inbound tag before forwarding the frame (possibly forwarding the frame to switch Y.C) on the port indicated by the routing information held by switch Z.C. The switch Y.C can forward the frame on the port indicated by its routing information, and so on, until the frame reaches its destination: the management device 14 . In other embodiments, each switch 22 that receives an inbound frame adds an inbound tag representing the group/switch/port that received the frame. In a particular embodiment, the receiving switch 22 adds an inbound label indicating only the port on which the receiving switch 22 received the frame, and each subsequent switch 22 receiving the frame may add an inbound label indicating the port on which the switch 22 received the frame Additional inbound labels for . In some embodiments, the path the frame takes through the switching network 12 can be known by examining the inbound tags in the frame and, in some cases, by knowing the structure of the switching network 12 .

Outbound tags may be used to determine the particular path a frame should take through switching network 12 . For example, management device 14 and network device 16 may send outbound tagged frames to define a desired frame path. In some cases, any device that is aware of the outbound labeling protocol used by switched network 12 and its constituent switches 22 can send outbound labeled frames. To use outbound tags, the sending device can add one or more tags to the frame's header. Each outbound label may enable switching network 12 to transmit a frame along a set portion of switching network 12 (eg, across a link between two switches 22 or across a group 24).

In some embodiments, outbound tags are vectorized. For vectored outbound labels, each outbound label can specify a set of output ports. The sequence of these outbound tags in a frame may specify the frame's path through switching network 12 link by link. Each receiving switch 22 recognizes only the port specified by the current outbound label, removes the current outbound label from the frame, and then forwards the frame on the specified port. For example, in the illustrated embodiment, switch X.A may receive frames with vectored outbound tags. The first label identifies port 4. To pass the frame on to the appropriate next switch 22, switch X.A removes the first tag and sends the frame on port 4. The frame will then be received by switch Y.A, and switch Y.A repeats a similar process to pass the frame to the appropriate next switch 22 . In one embodiment, each vector tag is a bit map corresponding to a port of switch 22. In another embodiment, a vectored tag may reference a memory location (eg, a VLAN table entry) representing one or more egress ports.

In other embodiments, the outbound tag is of the port identification (port ID) type. For port ID type outbound tags, each outbound tag can specify a group/switch/port. A sequence of these outbound tags in a frame specifies a hop from one group 24 to the next group 24, or to an external network such as the Internet 18 or external network 20, or to a device such as the management device 14 or network device 16 (hop). Using a port ID type outbound label, the "current" outbound label can remain unchanged when the frame passes through the particular group 24, and can be removed when the frame is forwarded outside the particular group 24. For example, in the illustrated embodiment switch Y.B may receive a frame destined for network device 16m (which is connected to switch Z.D) as its final destination. If the frame has an outbound label of type Port ID, switch Y.B determines the group/switch/port specified by the first label in the frame. For this example it could be port Y.C.2. For example, consider switch Y.B that receives a frame with an initial label representing port Y.C.2. The switch Y.B first evaluates whether the group identification specified by the tag matches the group of which the switch Y.B is a member. If so, switch Y.B looks at the switch identification specified by the first label to determine if the label identifies switch Y.B (no in this case). Since this switch identification designates another switch in group Y, switch B accesses its routing information to determine the appropriate port on which to send the frame to switch Y.C. Switch Y.B then forwards the frame on that port, with the first label still being part of the frame. When the frame is received, the switch Y.C checks the group identity and the switch identity indicated by the label. In this case, switch Y.C can remove the first label from the frame and forward it on the port specified by the label (port 2 in this example) since the groupID and switchID in the label specify switch Y.C. the frame.

Although switching network 12 is described as a plurality of switches 22 organized into a given group 24, it should be noted that this is a logical description. Components of switching network 12 may be located at one or more physical locations and/or may include additional or fewer components. Furthermore, the functionality of switch 22 and bank 24 may be provided by any suitable collection and arrangement of components. The functions performed by the various components of switching network 12 may be accomplished by any suitable device for controlling the path of frames through the network.

As illustrated, system 10 also includes a management device 14 connected to switching network 12 through switch X.A. Management device 14 may control the operation of switching network 12 and/or the interoperation between different switches 22 within switching network 12 . In particular embodiments, management device 14 performs initial configuration of switching network 12 . The initial configuration divides switches 22 into groups 24 , assigns a switch ID to each switch 22 , assigns a group ID to each group 24 , and issues to each switch 22 the switch ID and group ID corresponding to that particular switch 22 . In addition, management device 14 may send this initial configuration result to any other device that may use the network-based routing scheme. Management device 14 may perform initial configuration in any suitable manner, including automated or manual.

In some embodiments, management device 14 receives network management messages from network device 16 , Internet 18 , external network 20 and/or switch 22 . In order to control the routing of management messages to management devices 14, switches 22 within switching network 12 may provide special handling of received management messages. For example, when a particular switch 22 detects a received network management message, the switch 22 may access its routing information to determine the port on which to forward the network management message. In particular embodiments, each switch 22 has defined ports on which network management messages should be sent. The defined ports may vary from switch 22 to switch 22 . However, network management messages received by eg a switch Z.C may always follow the same path through the same switch 22 to reach the management device 14 . In particular embodiments, one or more switches 22 add inbound tags to network management messages so that management device 14 knows the port at which the network management message enters switching network 12 and/or where each network management message arrives at management device 14. The exact route traveled.

Furthermore, as noted above, system 10 may include any suitable number of management devices 14 . In these cases, switch 22 may send management messages to some or all management devices 14 . For example, different management devices 14 may be responsible for different management functions, and switches 22 may forward management messages based on type or other suitable factors.

Network device 16 represents any device that may be connected to switched network 12 . For example, network devices 16 may include personal computers, servers, file storage units, network printers, and other network-capable devices. Network device 16 communicates with other network devices 16 , management device 14 , Internet 18 and external network 20 through switching network 12 . Although not illustrated, network device 16 may also connect to other networks or other devices, components or elements. As illustrated, system 10 includes three network devices: 161, 16m, and 16n. Network device 161 is connected to switching network 12 through switch Y.B; network device 16m is connected to switching network 12 through switch Z.D; and network device 16n is connected to switching network 12 through switch Z.A. Although system 10 includes three network devices 16 , it should be understood that any number and type of network devices 16 may be connected to switched network 12 .

Internet 18 and external network 20 represent networks connected to switching network 12 through which messages may be sent to and/or received from other elements connected to switching network 12 . The Internet 18 may be any group of networks connected together, such as a worldwide collection of computers and computer networks that can use the TCP/IP network protocol for data transmission and exchange. The external network 20 represents another network of devices enabling communication between a plurality of devices. For example, external network 20 may include one or more networks such as a telecommunications network, a satellite network, a cable network, a local area network (LAN), a wide area network (WAN), a public switched telephone network, and/or any other suitable network. Although not explicitly illustrated, external network 20 may solely employ a network-based routing scheme for communications within external network 20 similar to that described for switched network 12 .

In the illustrated embodiment, the Internet 18 is connected to the switched network 12 through a switch Y.B, while the external network 20 is connected to the switched network 12 through a switch Z.C. The Internet 18 and the external network 20 can communicate with the network device 16 , the management device 14 , and can communicate with each other through the switching network 12 . Although not illustrated, it should be understood that each of Internet 18 and external network 20 may also be connected to other networks or other devices, components or elements. Although system 10 includes two networks (Internet 18 and external network 20 ), any number and type of networks 16 may be connected to switched network 12 .

While specific embodiments of systems using network-based routing schemes have been described, this is not an inclusive example. Although system 10 is described as comprising a specific configuration and arrangement of elements, it should be noted that this is a logical description and that the components and functions of system 10 can be combined, separated, and distributed as appropriate, both logically and physically. . Furthermore, the functionality of system 10 may be provided by any suitable collection and arrangement of components. The described and illustrated organization, number, and structure of switches 22 in switching network 12 are exemplary only. Switch 22 may be organized and configured in any suitable manner, and switch 22 may include any suitable configuration and number of groups 24 . System 10 may be configured in any suitable manner to control the routing of frames through switching network 12 .

Figures 2A to 2C illustrate one of groups 24: group Z, which uses a network-based routing scheme and a sample network routing table corresponding to a switch Z.A in group Z. Figure 2A illustrates an embodiment of one of the plurality of groups 24 (group Z) and its constituent switches 22 (switch Z.A, switch Z.B, switch Z.C and switch Z.D). These constituent switches 22 are connected by intragroup links 30 and external links 32 . Intra-group links 30 connect constituent switches 22 to other constituent switches 22 , while external links 32 connect constituent switches 22 to switches 22 and network devices 16m , 16n in other groups 24 . Although not illustrated, external links 32 may connect constituent switch 22 to various networks, components, elements, or devices, including other network devices 16 , management devices 14 , the Internet 18 , and external networks 20 , for example.

As illustrated, switch Z.A has 6 intra-team links 30 and external links 32 represented by ports 0-5. In the illustrated embodiment, port 0 is connected to switch X.B; port 1 is connected to switch Z.B; port 2 is connected to switch Z.D; and port 4 is connected to network device 16n. These connections between switch Z.A and other devices or networks may be achieved by any suitable logic or device using any suitable communication or protocol. Although not illustrated, ports 3 and 5 may be connected to any network device 16, switch 22, network (such as the Internet 18 or external network 20), or any other network, component, element or device. Although switch 22 is described as having only six ports, it should be understood that switch 22 may include any suitable number of ports.

Figure 2B illustrates one example of how switch 22 may store routing information. In the illustrated embodiment, switch Z.A stores routing information as network routing table 34 . The network routing table 34 includes a switch column 36 indicating the switch or device that should receive the frame, and an egress port column 38 indicating the corresponding egress port on which the frame should be sent. When switch Z.A receives a frame destined for an identified switch 22 or device (eg, network device 16m, 16n or management device 14), it looks up table 34 to determine on which port the frame should be sent.

In certain embodiments, the switched network 12 is divided into groups 24 of switches 22 such that any particular port in the switched network 12 can be uniquely referenced through the use of a group/switch/port identifier. Furthermore, within a group 24, a particular port can be uniquely referenced simply by using a switch/port identifier. Thus, within a particular group 24 (eg, group Z), network routing tables may be defined for the group only. As illustrated, the network routing table 34 of switch Z.A only provides routing information for the other switches 22 in group Z, the devices connected to switch Z.A, and the management device 14 . Since switch Z.A does not have to maintain routing information for switches 22 in groups 24 other than group Z, switch Z.A can have a smaller network routing table size and a simpler lookup mechanism. In certain embodiments, the routing information is stored in the form of a table, while in other embodiments, the routing information is stored and/or maintained in a variety of different ways. Routing information is illustrated and described as being stored in table 34, but it should be understood that this is for illustrative purposes only and that routing information may be stored in any suitable manner. Additionally, although not explicitly illustrated, switch 22 may also include routing information to facilitate routing frames using other protocols. For example, switch 22 may maintain Ethernet-based routing information for routing frames based on addressing information (which may include the frame's source address and destination address).

For example, switch Z.A can receive frames with outbound tags of type Port ID. Switch Z.A looks at the first label and determines if the label's group identification is equal to group Z. If so, switch Z.A determines if the label's switch identification is equal to switch Z.A. If the switch identification of the label is identical to the switch identification of the switch Z.A, the switch Z.A removes the first label from the frame and forwards the frame on the port identified by the label. Otherwise, switch Z.A knows that the switch identified by the label's switch identification should receive the frame. By consulting the network routing table 34, the switch Z.A can determine the appropriate egress port for the frame so that the frame reaches the switch identified by the label.

As another example, switch Z.A may receive network management messages destined for management device 14 . After accessing table 34, switch Z.A determines that frames destined for management device 14 should be forwarded on port 0. In the illustrated embodiment, switch X.B receives the network management message from switch Z.A and similarly forwards the network management message based on its routing information. In particular embodiments, the routing information stored in switch 22 identifies the particular outbound port on which to forward any and all network management messages. In certain embodiments, the routing information indicates the outbound ports used to forward network management messages to management device 14 through more complex methods.

Figure 2C illustrates an example of group routing information that may be stored and maintained by switch Z.A. As illustrated, switching network 12 includes group Z, group Y, and group X. As shown in FIG. In many embodiments, switch Z.A does not maintain routing information for switches 22 located in group Y or group X. Thus, in a particular embodiment, switch Z.A maintains a table 40 providing routing information for group Y as a whole and routing information for group X as a whole. The basic routing information for each group 24 listed by column 42 is associated with the outbound ports listed by column 44 . Thus, switch Z.A may maintain a table 40 to designate a particular egress port (port 0 in the illustrated embodiment) of frames addressed to group X. In certain embodiments, the basic routing information for other groups 24 is stored in various formats, and the use of table 40 is illustrative and not limiting. Although table 40 is illustrated as storing only two groups 24, table 40 may include routing information corresponding to any number of different groups 24, devices, networks, and the like. In some embodiments, switch 22 does not store group routing information.

Group Z and tables 34, 40 illustrated and described with reference to FIGS. 2A to 2C are exemplary only. It should be understood that the manner of operation and devices represented as performing different operations may be modified in any suitable manner. Although routing information is described in table form, certain embodiments include routing information stored in any suitable manner. Furthermore, although group Z is described as having a particular configuration and arrangement of components, group 24 may include any suitable device suitably arranged to provide a system for controlling the path of frames through the network.

3A to 3C illustrate the path of an outbound frame and the corresponding structure of the frame as it passes through various switches 22 . Figure 3A illustrates the path 50 of a frame. In the illustrated embodiment, the management device 14 sends the frame, which passes through 4 switches 22 (which are part of 3 different groups 24 ) and to the external network 20 . The management device 14 may structure the frame such that the various switches 22 in the switching network 12 know in which particular direction to route the frame. The management device 14 may structure the frame so that the most efficient route is taken, the route with the least traffic is used, a faulty switch 22 is avoided, or the frame is structured for any suitable reason. Management device 14 may send frames in response to frames sent by external network 20 . The routing selected by the management device 14 may be chosen such that the external network 20 receives the frame at the same port on which the original message was sent.

As illustrated, path 50 includes 5 different hops (1 to 5). First, the management device 14 sends the frame to the switch X.A via hop 1 . Switch X.A then sends the frame to switch X.C in hop 2; switch X.C sends the frame to switch Y.C in hop 3; switch Y.C then sends the frame to switch Z.C in hop 4. Finally, the switch Z.C sends the frame to the external network 20 in hop 5 . In some embodiments, frames are structured to include vector-type tags. In FIG. 3B, for each hop (1 to 5) of the path 50, the structure of a frame with a vector type label is shown. In a particular embodiment, the frame is structured to include a port ID type tag. In FIG. 3C, for each hop (1 to 5) of the path 50, the structure of a frame with a port ID type tag is shown.

FIG. 3B shows the corresponding structure of frames for various hops (1 to 5) through path 50. In FIG. In the illustrated embodiment, the frame is structured with a vector-type label representing the next switch 22 on the path 50 . As illustrated, a frame includes a destination address 52 , a source address 54 , one or more (or none) tags 56 , and a payload 58 . Destination address 52 may be an indication of the frame's destination in any suitable format or protocol. Similarly, source address 54 may be an indication of the source of the frame in any suitable format or protocol. Tag 56 operates to control the path of frames through switching network 12 . Payload 58 represents any type of information, and may include all information not contained in the frame's header. In some embodiments, the payload 58 is the information to be conveyed by the frame. In other embodiments, payload 58 represents any information that is not processed or analyzed by switch 22 .

The frame corresponding to hop 1 represents the structure of the frame sent from the management device 14 to the switch X.A. In Hop 1 , the frame contains a destination address 52 , a source address 54 , four tags 56 and a payload 58 . Switch X.A receives the frame and extracts the tag 56a. Since tag 56a contains the value 5, switch X.A sends the frame on port 5 after removing tag 56a from the frame. Thus, in Hop 2 the frame contains a destination address 52 , a source address 54 , three tags 56 and a payload 58 . After Hop 2, the switch X.C receives the frame and extracts the label 56b. As illustrated, tag 56b contains a value of 4. Switch X.C removes tag 56b from the frame and sends the frame out on port 4. In Hop 3 the frame contains a destination address 52 , a source address 54 , 2 tags 56 and a payload 58 . The switch Y.C receives the frame and extracts the label 56c. Tag 56c contains the value 0, so switch Y.C sends the frame on port 0 after removing tag 56c from the frame. For Hop 4, the frame contains a destination address 52, a source address 54, a tag 56 and a payload 58. The switch Z.C receives the frame and extracts the last label 56: label 56d. Tag 56d contains the value 3. The switch Z.C removes the tag 56d from the frame and sends the frame out on port 3, which is then received by the external network 20.

The frame structure in FIG. 3B depicts logical information contained in multiple vector-type tags for illustrative purposes only. However, as noted above, a vectored tag may include information encoded in any suitable format to allow switch 22 to properly identify one or more outbound ports. As noted above, each vector-type tag may comprise a bit-vector, a reference to a bit-vector stored in memory, or any other data structure suitable for representing one or more outbound ports.

FIG. 3C shows the corresponding structure of frames for various hops (1 to 5) through path 50. In FIG. In the illustrated embodiment, the frame is constructed with a port ID type tag representing the next group 24 in the path 50 . As illustrated, a frame includes a destination address 52 , a source address 54 , one or more (or none) tags 60 , and a payload 58 . In some embodiments, destination address 52, source address 54, and payload 58 are similar to those shown in Figure 3B. Tag 60 operates to control the path of frames through switching network 12 .

The frame corresponding to hop 1 represents the structure of the frame sent from the management device 14 to the switch X.A. In Hop 1 , the frame contains a destination address 52 , a source address 54 , three tags 60 and a payload 58 . Switch X.A receives the frame and extracts the tag 60a. Label 60a designates port X.C.4: port 4 of switch X.C. Switch X.A first compares the group identification "X" of tag 60a with its own group identification. Switch X.A finds that they match, and switch X.A compares the switch identity "C" of label 60a with its own switch identity. Since they do not match, switch X.A looks at its routing information to determine the appropriate egress port for frames destined for switch X.C. Switch X.A recognizes port 5 as the correct port and sends the frame on port 5 to switch X.C. In the illustrated embodiment, switch X.A does not remove tag 60a from the frame because the switch identification in tag 60a does not match the switch identification of switch X.A.

In Hop 2, the frame still contains a destination address 52, a source address 54, three tags 60 and a payload 58. Switch X.C receives the frame and extracts the tag 60a. The exchange X.C first compares the group identification "X" of the tag 60a with its own group identification. Switch X.C finds that they match, and switch X.C compares the switch identity "C" of label 60a with its own switch identity. Since they match, switch X.C evaluates the port ID (which is 4). Switch X.C first removes tag 60a and then sends the frame on port 4 to switch Y.C.

For Hop 3, the frame contains a destination address 52 , a source address 54 , 2 tags 60 and a payload 58 . The switch Y.C receives the frame and extracts the label 60b. Similarly, switch Y.C first compares the group identification "Y" of tag 60a with its own group identification. Switch Y.C finds that they match, and switch Y.C compares the switch identity "C" of label 60b with its own switch identity. Since they match, the switch Y.C evaluates the port identification (which is 0). Switch Y.C removes tag 60b and sends the frame on port 0.

Thus, in Hop 4 , the frame contains destination address 52 , source address 54 , 1 tag 60 c and payload 58 . The switch Z.C receives the frame and extracts the label 60c. First, the switch Z.C compares the group identification "Z" of the tag 60a with its own group identification. The exchange Z.C finds that they match and then compares the exchange identification of the label 60c with its own exchange identification. Since there is a match again, the switch Y.C evaluates the port identification (port 3). Switch Z.C removes tag 60c and sends the frame on port 3. In Hop 5 , the frame contains a destination address 52 , a source address 54 and a payload 58 . The frame is received by the external network 20 after hop 5 .

The devices and frame structures illustrated and described with reference to FIGS. 3A to 3C are merely exemplary. It should be understood that the manner of operation and devices represented as performing different operations may be modified in any suitable manner. Although frames are described as including particular protocols and structures, frames may be structured in any suitable manner and use any protocol in particular embodiments. In particular, although a frame is shown with a destination address 52, a source address 54, and a payload 58, particular embodiments contemplate any frame structure with tags that control the path of the frame through the switching network 12. . Furthermore, although the path traversed by the frame is described as having a particular set of switches 22, the path may include any suitable device suitably arranged to provide a system for controlling the path of the frame through the network.

FIG. 4 is a flowchart illustrating a method 80 for processing network management messages received at a switch 22 . In the illustrated embodiment, a port ID type tag is added to inbound network management messages so that management device 14 can determine the precise entry point of the network management message received by management device 14 .

At step 82, switch 22 receives the frame. In step 84, switch 22 determines whether the frame is a network management message. For example, network management messages may be identified by information contained in a header of a frame, by receiving the frame at a particular time, by receiving the frame from a particular location, or in any other suitable manner. If the frame is not a network management message, as shown in step 86, a method similar to that shown in FIG. 5 may proceed. However, if the frame is a network management message, method 80 proceeds to step 88 where switch 22 accesses routing information stored on switch 22 . In step 90, switch 22 uses the routing information to determine the appropriate output port for the network management message. In some embodiments, switch 22 has access to this routing information, which identifies the appropriate output port for any and all network messages. For example, the routing information may be similar to that illustrated and described with reference to FIG. 2B. In other embodiments, switch 22 uses this routing information to calculate the appropriate output port for network management messages.

After calculating the output port for the network management message, in step 92 switch 22 determines whether switch 22 received the frame from an external link. If so, then at step 94 switch 22 adds to the frame a tag specifying the input port on which the switch received the frame. If the frame was not received from an external link, method 80 simply proceeds to step 96 . Finally, in step 96 switch 22 sends the frame on the output port identified in step 90 . Method 80 then returns to step 82 where switch 22 receives another frame.

The method described with reference to FIG. 4 is exemplary only, and it is to be understood that the manner of operation and the apparatus represented as performing those operations may be modified in any suitable manner. For example, in some embodiments, port ID type tags are added to inbound network management messages. Although the method describes certain steps performed in a certain order, it should be understood that system 10 contemplates elements for performing some, all, or none of these steps in any operative order. any suitable collection and arrangement of .

FIG. 5 is a flowchart illustrating a method 100 for processing frames received at the switch 22 . In the illustrated embodiment, port ID type tags are used to control the path of frames through switching network 12 . At step 102, switch 22 receives the frame. Then, at step 104, switch 22 determines whether the frame is in the format of a particular routing protocol. In some embodiments, the VLAN ID tag at the beginning of the frame contains a specific value indicating that a particular routing protocol may be used. In other embodiments, switch 22 determines that the frame uses or complies with a particular routing protocol in a variety of different ways. If no special routing protocol is applied to the frame, then in step 106 switch 22 processes the frame according to standard routing and method 100 ends. In some embodiments, standard routing includes Ethernet and/or Internet Protocol (IP) based routing, although switch 22 may use any suitable routing protocol.

If a special routing protocol is used, method 100 proceeds to step 108 where switch 22 extracts (or reads) the first tag in the frame. In some embodiments, the first label is the label found closest to the beginning of the frame. In other embodiments, the first tag is the first tag of a plurality of tags for the frame processed by the switch 22 . In step 110, the switch 22 determines whether the group identification found in the label is a group to which this particular switch 22 belongs. If the group identification does not match the group of switch 22, then at step 112, switch 22 deletes the first tag from the frame. In step 114, switch 22 evaluates whether the frame still has a tag. If so, method 100 returns to step 108 where switch 22 reads the first tag in the frame. Otherwise, switch 22 discards the frame in step 116 and method 100 ends.

If the switch 22 determines that the tag's group identification is equal to the switch 22 group identification, the method 100 proceeds to step 118 . In step 118 , the switch 22 determines whether the label's switch identification is equal to the switch 22 switch identification. If so, then at step 120 switch 22 determines that the appropriate output port for the frame is equal to the port identification in the label. Switch 22 removes the first tag from the frame in step 122 and sends the frame on the determined output port in step 124; method 100 then ends. If the switch identification of the label is not equal to the switch identification of switch 22 , then method 100 proceeds from step 118 to step 126 . In step 126 , the switch 22 accesses the routing information stored by the switch 22 . In some embodiments, switch 22 stores routing information in the form of a table. In step 128, the switch 22 determines from the routing information on which port the frame should be forwarded so that the frame is received by the specific switch 22 designated by the switch identification in the frame. In step 130, switch 22 sends the frame on the output port, and method 100 ends.

The method described with reference to FIG. 5 is merely exemplary, and it should be understood that the manner of operation and the apparatus represented as performing those operations may be modified in any suitable manner. Although the method describes certain steps performed in a certain order, it should be understood that system 10 contemplates elements for performing some, all, or none of these steps in any operative order. any suitable collection and arrangement of .

Although the present invention has been described in several embodiments, various modifications and variations can be suggested by those skilled in the art, and the present invention includes such modifications and variations within the scope of the appended claims.

Claims (21)

1. A method for routing a frame, comprising the following steps: receiving a plurality of frames using a plurality of ports of the switch, each of the frames including a source address, a destination address, and a payload, at least some portion of the frame including one or more tags, each of the tags specifying a switch group identifier, a switch identifier, and a port identifier, wherein the switch is part of a switch group and the switch group is part of a switched network; maintaining routing information in the switch, the routing information representing an output port of the plurality of ports for each other switch in the group of switches; for each said frame, operating in a first mode of operation if the frame conforms to a particular routing protocol, and operating in a second mode of operation if the frame does not conform to the particular routing protocol; In the first operating mode: reading a first tag in the frame; determining whether the switch identification of the first label corresponds to the switch; If the switch identification of the first label does not correspond to the switch, accessing the routing information to determine the output port corresponding to the switch identification of the first label among the plurality of ports, and in the sending the frame on the determined output port of the plurality of ports; and if the switch identification of the first label corresponds to the switch, sending the frame on an output port of the plurality of ports corresponding to the port identification of the first label; and In the second mode of operation, the frames are processed according to standard routing protocols, including Ethernet and/or Internet Protocol based routing. 2. The method of claim 1, in the first mode of operation, further comprising the step of: determining whether the switch group identification of the first label corresponds to the switch group; and deleting the first label from the frame if the switch group identifier of the first label does not correspond to the switch group; Wherein, determining whether the switch identifier of the first label corresponds to the switch is performed after determining whether the switch group identifier of the first label corresponds to the switch group. 3. The method of claim 2, further comprising the step of: after deleting the first tag from the frame, determining whether the frame includes a second tag; If the frame includes a second tag, reading the second tag and determining whether the switch group identification of the second tag corresponds to the switch group; and If the frame does not include the second tag, the frame is discarded. 4. The method of claim 1, further comprising the steps of: receiving a network management message at an input port of the plurality of ports; determining an output port of the plurality of ports on which to send the received network management message; If the network management message is received on a link connecting the switch to a device external to the switched network, inserting a tag in the network management message indicating the multiple The one of the ports that receives the network management message; and The frame is sent on the determined output port of the plurality of ports. 5. The method of claim 4, wherein the routing information includes an entry specifying a port of the plurality of ports on which to send all network management messages received by the switch . 6. The method of claim 1, in the first mode of operation, further comprising the step of: if the switch identification of the first tag corresponds to the switch, before sending the frame, from the frame Remove the first label in the . 7. The method of claim 1, wherein: each switch group in the switching network has a switch group identifier, the switch group identifier corresponding to each switch group being different from the switch group identifier corresponding to any other switch group; and For each switch group, each switch in the switch group has a corresponding switch identifier, the switch identifier corresponding to each switch being different from the switch identifier corresponding to any other switch in the switch group. 8. A switch, comprising: a plurality of ports, each operable to receive a plurality of frames, each of which includes a source address, a destination address, and a payload, at least some portion of which includes one or more tags , each of the tags specifies a switch group ID, a switch ID, and a port ID; a memory operable to maintain network routing information representing output ports of the plurality of ports for one or more other switches in the group of switches, and standard routing information, the standard routing information routing information maps addressing information to output ports of the plurality of ports, wherein the switch is part of the group of switches that is part of a switching network; Wherein, for each frame, the switch can operate to determine whether the frame conforms to a special routing protocol, and if the frame does not conform to the special routing protocol, use a standard routing protocol to frames, wherein the standard routing protocols include Ethernet and/or Internet Protocol-based routing; wherein, if the frames conform to the special routing protocol, the switch is also operable to read the the first label in the frame, and determine whether the switch identification of the first label corresponds to the switch; if the switch identification of the first label does not correspond to the switch, the switch is also operable to accessing the network routing information to determine an output port of the plurality of ports corresponding to the switch identification of the first label, and sending the frame on the determined output port of the plurality of ports ; if the switch identification of the first label corresponds to the switch, the switch is further operable to send the output port on the output port corresponding to the port identification of the first label among the plurality of ports frame. 9. The switch of claim 8, wherein: The switch is further operable to determine whether the switch group identifier of the first label corresponds to the switch group, and if the switch group identifier of the first label does not correspond to the switch group, from the frame delete said first tag; and Determining whether the switch identifier of the first label corresponds to the switch is performed after determining whether the switch group identifier of the first label corresponds to the switch group. 10. The switch of claim 9, wherein the switch is further operable to: after deleting the first tag from the frame, determining whether the frame includes a second tag; If the frame includes a second tag, reading the second tag and determining whether the switch group identification of the second tag corresponds to the switch group; and If the frame does not include the second tag, the frame is discarded. 11. The switch of claim 8, wherein the switch is further operable to: receiving a network management message at an input port of the plurality of ports; determining an output port of the plurality of ports on which to send the received network management message; If the network management message is received on a link connecting the switch to a device external to the switched network, inserting a tag in the network management message indicating the multiple The input port that receives the network management message among the ports; and The frame is sent on the determined output port of the plurality of ports. 12. The switch of claim 11, wherein the network routing information includes an entry specifying one of the plurality of ports on which to send all network management messages received by the switch output port. 13. The switch of claim 8, wherein if the switch identification of the first tag corresponds to the switch, the switch is further operative to remove the first tab. 14. The switch of claim 8, wherein: each switch group in the switching network has a switch group identifier, the switch group identifier corresponding to each switch group being different from the switch group identifier corresponding to any other switch group; and For each switch group, each switch in the switch group has a corresponding switch identifier, the switch identifier corresponding to each switch being different from the switch identifier corresponding to any other switch in the switch group. 15. A system for routing a plurality of frames comprising: means for receiving a plurality of frames using a plurality of ports of a switch, each of the frames comprising a source address, a destination address and a payload, at least some portion of the frame comprising one or more tags, each The tags all specify a switch group identifier, a switch identifier, and a port identifier, wherein the switch is part of a switch group, and the switch group is part of a switching network; means for maintaining routing information in said switch, the routing information representing an output port of said plurality of ports for each other switch in said group of switches; means for: for each said frame, for operating in a first mode of operation if the frame conforms to a special routing protocol, and for operating in a second mode if the frame does not conform to the special routing protocol operating mode to operate; In the first operating mode: reading a first tag in the frame; determining whether the switch identification of the first label corresponds to the switch; If the switch identification of the first label does not correspond to the switch, accessing the routing information to determine an output port of the plurality of ports corresponding to the switch identification of the first label, and in the sending the frame on the determined output port of the plurality of ports; and if the switch identification of the first label corresponds to the switch, sending the frame on an output port of the plurality of ports corresponding to the port identification of the first label; and In the second mode of operation, the frames are processed according to standard routing protocols, including Ethernet and/or Internet Protocol based routing. 16. The system of claim 15, further comprising, in the first mode of operation: determining whether the switch group identification of the first label corresponds to the switch group; and deleting the first label from the frame if the switch group identifier of the first label does not correspond to the switch group; Wherein, determining whether the switch identifier of the first label corresponds to the switch is performed after determining whether the switch group identifier of the first label corresponds to the switch group. 17. The system of claim 16, further comprising: in the first mode of operation: determining whether the frame includes a second tag after deleting the first tag from the frame; If the frame includes a second tag, reading the second tag and determining whether the switch group identification of the second tag corresponds to the switch group; and If the frame does not include the second tag, the frame is discarded. 18. The system of claim 15, further comprising: means for receiving network management messages at an input port of a plurality of ports; means for determining an output port of the plurality of ports on which to send the received network management message; means for inserting a tag in the network management message if the network management message is received on a link connecting the switch to a device external to the switched network, the tag indicating the an input port of the plurality of ports of the switch that receives the network management message; and means for sending the frame on the determined output port of the plurality of ports. 19. The system of claim 18, wherein the routing information includes an entry specifying an output of the plurality of ports on which to send all network management messages received by the switch port. 20. The system of claim 15, further comprising, in a first mode of operation, removing all of the Describe the first tab. 21. The system of claim 15, wherein: each switch group in the switching network has a switch group identifier, the switch group identifier corresponding to each switch group being different from the switch group identifier corresponding to any other switch group; and For each switch group, each switch in the switch group has a corresponding switch identifier, the switch identifier corresponding to each switch being different from the switch identifier corresponding to any other switch in the switch group.

Images