# Patent

## Title
Systems and methods for routing data in a communications network

## Abstract

A network device includes a group of interfaces. Each interface is associated with at least one other interface of the group of interfaces and a group of network addresses. Each interface is configured to monitor at least one of the group of network addresses with which the each interface is associated or the at least one other interface with which the each interface is associated, and determine whether to logically shut down based on the monitoring.

## Background
RELATED APPLICATION
This application is a continuation of U.S. patent application Ser. No. 11/037,180, filed Jan. 19, 2005, which is incorporated herein by reference.


FIELD OF THE INVENTION
Implementations consistent with the principles of the invention relate generally to communications networks and, more particularly, to systems and methods for routing data in a communications network.
BACKGROUND OF THE INVENTION
A typical communications network includes a lot of different types of network devices. For example, a typical communications network may include host devices, which act as the source or destination of a particular flow of traffic, routers and/or switches, which act to forward traffic flows toward their appropriate destinations, and security devices, which provide, for example, firewall functionality. These different types of network devices may be interconnected via links.
In some instances, a link between a pair of network devices may fail or a network device may fail. In those instances, it is important that the communications network have the capability to route a flow of traffic along a different path (e.g., one that does not include the failed link or failed network device). Currently, when an interface connected to the failed link or network device detects that the link or network device has failed, the interface may physically shut down, preventing all traffic from going through the interface.
SUMMARY OF THE INVENTION
In a first implementation consistent with the principles of the invention, a method includes detecting a problem forwarding a traffic flow via a first interface of a network device, and transferring the traffic flow to a second interface of the network device using layer 3 signaling.
In another implementation consistent with the principles of the invention, a network device includes a group of interfaces. Each interface is associated with at least one other interface of the group of interfaces and a group of network addresses. Each interface is configured to monitor at least one of the group of network addresses with which the each interface is associated or the at least one other interface with which the each interface is associated, and determine whether to logically shut down based on the monitoring.
In still another implementation consistent with the principles of the invention, a method includes monitoring at least one of a group of network addresses with which an interface is associated or at least one other interface with which the interface is associated, and determining whether to logically shut down the interface based on the monitoring.



BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention and, together with the description, explain the invention. In the drawings,
FIG. 1 is an exemplary diagram of a communications network in which systems and methods consistent with the principles of the invention may be implemented;
FIG. 2 is an exemplary configuration of the network device of FIG. 1 in an implementation consistent with the principles of the invention;
FIG. 3 is an exemplary configuration of a data structure that may be associated with an interface of the network device of FIG. 1 in an implementation consistent with the principles of the invention;
FIG. 4 is a flowchart of an exemplary process for routing data units in a communications network in an implementation consistent with the principles of the invention; and
FIGS. 5 and 6 are exemplary data structures that may be associated with interfaces of the network device of FIG. 1 in an implementation consistent with the principles of the invention.



DETAILED DESCRIPTION
The following detailed description of implementations consistent with the principles of the invention refers to the accompanying drawings. The same reference numbers in different drawings may identify the same or similar elements. Also, the following detailed description does not limit the invention. Instead, the scope of the invention is defined by the appended claims and their equivalents.
Systems and methods consistent with the principles of the invention improve traffic forwarding within a communications network. In an exemplary implementation, when a problem is detected with respect to communicating a traffic flow, the traffic flow can be moved from one interface in a network device to another interface in the network device using layer 3 signaling.
Exemplary System
FIG. 1 is an exemplary diagram of a communications network 100 in which systems and methods consistent with the principles of the invention may be implemented. As illustrated, communications network 100 may include host devices H1 110a and H2 110b (collectively, host devices 110), routing devices R1 120a, R2 120b, and R3 120c (collectively, routing devices 120), a network device 130, and a network 140. It will be appreciated that network 100 may include other devices (not shown) that aid in receiving, processing, and/or transmitting data.
Host devices 110 may include typical host devices, such as mainframes, minicomputers, personal computers, laptops, personal digital assistants (PDAs), wireless telephones, or other types of computational or communication devices, threads or processes running on one of these devices, and/or objects executable by one of these devices. Host devices 110 may communicate with each other by transmitting data units, such as packets, through communications network 100.
Routing devices 120 may include network devices that receive data units, process the data units to determine their destination(s), and forward the data units toward their determined destination(s).
Similar to routing devices 120, network device 130 may include a network device that receives data units, processes the data units to determine their destination(s), and forwards the data units toward their determined destination(s). As illustrated in FIG. 1, network device 130 may include multiple interfaces, depicted as interfaces e 1/1, e 1/2, e 2/1, and e 2/2. Interfaces e 1/1 and e 1/2 may receive data units from routing device R1 120a and transmit data units to routing device R1 120a. Interface e 2/1 may receive data units from routing device R2 120b and transmit data units to routing device R2 120b. Similarly, interface e 2/2 may receive data units from routing device R3 120c and transmit data units to routing device R3 120c. In one implementation consistent with the principles of the invention, interfaces e 1/1 and e 2/1 may be associated with each other, such that data units received on interface e 1/1 are forwarded to interface e 2/1 for forwarding to routing device R2 120c and data units received on interface e 2/1 are forwarded to interface e 1/1 for forwarding to routing device R1 120a. Similarly, interfaces e 1/2 and e 2/2 may be associated with each other, such that data units received on interface e 1/2 are forwarded to interface e 2/2 for forwarding to routing device R3 120c and data units received on interface e 2/2 are forwarded to interface e 1/2 for forwarding to routing device R1 120a. Although four interfaces are depicted in FIG. 1, it will be appreciated that network device 130 may include more or fewer interfaces. Moreover, it will be appreciated that one or more of the interfaces may be associated with more than one other interface. The number of interfaces illustrated in FIG. 1 is provided for explanatory purposes only.
Network 140 may include, for example, a local area network (LAN), a wide area network (WAN), a telephone network, such as the Public Switched Telephone Network (PSTN), an intranet, the Internet, or a combination of networks. In fact, network 140 may include any type of network that is capable of forwarding data units.
In the exemplary communications network 100 illustrated in FIG. 1, traffic can be routed between host H1 110a and host H2 110b via two possible paths (or tunnels). The first path, depicted as path 150, may be from host H1 110a through routing device R1 120a, interfaces e 1/1 and e 2/1 of network device 130, routing device R2 120b, and network 140 to host H2 110b. The second path, depicted as path 160, may be from host H1 110a through routing device R1 120a, interfaces e 1/2 and e 2/2 of network device 130, routing device R3 120c, and network 140 to host H2 110b. Therefore, two paths 150 and 160 may exist for transmitting data units between host H1 110a and host H2 110b. In one implementation, path 150 may be a higher priority path.
FIG. 2 is an exemplary configuration of network device 130 of FIG. 1 in an implementation consistent with the principles of the invention. As illustrated, network device 130 may include a bus 210, processing logic 220, an Application Specific Integrated Circuit (ASIC) 230, a memory 240, and a group of communication interfaces 135. Bus 210 permits communication among the components of network device 130.
Processing logic 220 may include any type of conventional processor or microprocessor that interprets and executes instructions. ASIC 230 may include one or more ASICs capable of performing network-related functions. In one implementation, ASIC 230 may perform a security-related function.
Memory 240 may include a random access memory (RAM) or another dynamic storage device that stores information and instructions for execution by processing logic 220; a read only memory (ROM) or another type of static storage device that stores static information and instructions for use by processing logic 220; and/or some other type of magnetic or optical recording medium and its corresponding drive. Communication interfaces 135 may include any transceiver-like mechanism that enables network device 130 to communicate with other devices and/or systems, such as routing devices 120.
As will be described in detail below, network device 130, consistent with the principles of the invention, monitors interfaces 135 and select network addresses (e.g., Internet Protocol (IP) addresses) and logically shuts down interfaces based on the monitoring. Network device 130 may perform these and other operations in response to processing logic 220 executing software instructions contained in a computer-readable medium, such as memory 240. A computer-readable medium may be defined as one or more memory devices and/or carrier waves. The software instructions may be read into memory 240 from another computer-readable medium or from another device via a communication interface 135. The software instructions contained in memory 240 may cause processing logic 220 to perform processes that will be described later. Alternatively, hardwired circuitry may be used in place of or in combination with software instructions to implement processes consistent with the principles of the invention. Thus, systems and methods consistent with the principles of the invention are not limited to any specific combination of hardware circuitry and software.
FIG. 3 is an exemplary configuration of a data structure 300 that may be associated with one of interfaces 135 of network device 130 in an implementation consistent with the principles of the invention. In one implementation, each of interfaces 135 of network device is associated with a data structure 300. For explanatory purposes, assume that data structure 300 described below is associated with interface e 1/1 of FIG. 1.
As illustrated, data structure 300 may include a track network address (NA) field 310, an interface (IF) list field 320, a threshold field 330, and a summation (SUM) field 340. Track network address field 310 may store a list of network addresses of which interface e 1/1 will monitor the status. The list can include zero or more entries. For example, interface e 1/1 (FIG. 1) may monitor the status of host H1 110a. Therefore, the network address (e.g., an IP address) of host H1 110a may be stored in field 310 for interface e 1/1. As another example, interface e 2/1 (FIG. 1) may monitor the status of host H2 110b. Therefore, the network address (e.g., an IP address) of host H2 110b may be stored in field 310 for interface e 2/1. Each network address in track network address field 310 may be associated with a weight value. The weight values may be configurable.
Interface list field 320 may store a list of zero or more interfaces to be monitored. In one implementation, interface list field 320 may store a list of those interfaces associated with interface e 1/1. As set forth above, in the exemplary configuration illustrated in FIG. 1, interface e 1/1 may be associated with interface e 2/1. Therefore, information identifying interface e 2/1 may be stored in interface field 320. If interface e 1/1 were associated with more than one interface, information identifying each interface would be stored in field 320. Each interface identified in interface list field 320 may be associated with a weight value. The weight values may be configurable.
Threshold field 330 may store a configurable threshold value. The threshold value may be an integer value greater than or equal to 1. Summation field 340 may store a value representing a current status level of interface e 1/1. The manner in which the summation value is determined is described in detail below with respect to the process of FIG. 4.
Exemplary Processing
FIG. 4 is a flowchart of an exemplary process for routing data units in communications network 100 in an implementation consistent with the principles of the invention. The following process may be implemented by processing logic 220 for the interfaces of network device 130. Processing may begin by verifying the status of the network addresses stored in field 310 of database 300 associated with an interface (act 405). In one implementation, processing logic 220 may ping each network address stored in field 310 of database 300. Other techniques may alternatively be used. For example, an address resolution protocol (ARP) command may be used to verify the status of the network addresses stored in field 310. In one implementation, the choice of network address verification technique may be user configurable.
Processing logic 220 may determine whether any of the network addresses are unavailable (e.g., the device associated with the network address cannot be reached) (act 410). Processing logic 220 may determine that a particular network address is not available when a reply to a ping request to that network address has not received. If each of the network addresses is determined to be available, processing may return to act 405 with processing logic 220 re-verifying the status of the network addresses for the interface. In one implementation, processing logic 220 may verify the status of the network addresses at a periodic time interval, such as every second. The time interval may be configurable.
If processing logic 220 determines that one or more of the network addresses are unavailable (act 410), processing logic 220 may add the weights of the unavailable network addresses to the summation value in summation field 340 (act 415). The summation value may be zero (or some other predetermined value) when all of the network addresses and the associated interfaces are determined to be available.
During, before, or after the time that processing logic 220 is monitoring the status of the network addresses in track network address field 310 of database 300, processing logic 220 may monitor the status of the associated interfaces identified in interface list field 320 of database 300 (act 420). In one implementation, an interface may receive event messages from each interface identified in field 320 of database 300. Processing logic 220 may determine whether any of the associated interfaces are down (act 425). Processing logic 220 may determine that a particular associated interface is down when an event message is received from that associated interface. If each of the associated interfaces is determined to be available (i.e., not down), processing may return to act 420 with processing logic 220 continuing to monitor the status of the associated interfaces. In one implementation, processing logic 220 may verify the status of the associated interfaces at a periodic time interval, such as every second. The time interval may be configurable.
If processing logic 220 determines that one or more of the associated interfaces are unavailable (act 425), processing logic 220 may add the weights of the associated interfaces that are determined to be down to the summation value in summation field 340 for the interface (act 430). As set forth above, the summation value may be zero (or some other predetermined value) when all of the network addresses and the associated interfaces are determined to be available.
Processing logic 220 may compare the summation value in summation field 340 for the interface to the threshold value in field 330 (act 435). Processing logic 220 may make this comparison at predetermined periods. If the summation value does not equal or exceed the threshold value (act 440), processing may return to act 405 and/or act 420. If, on the other hand, the summation value equals or exceeds the threshold value (act 440), the interface may be logically shut down by processing logic 220 (act 445). Logically shutting down an interface means that the interface is shut down at the layer 3 level, as opposed to physically shutting down the interface, which is performed at the layer 1 or layer 2 level. To logically shut down an interface, a routing protocol associated with the interface may notify associated network devices in communications network 100, using layer 3 signaling, not to use that interface. For example, assuming that the interface is interface e 1/1 in FIG. 1, interface e 1/1 may notify routing device R1 120a and/or host device H1 110a to use another path for routing data units. The routing protocol may be an Open Shortest Path First (OSPF) protocol or other type of protocol.
In response to this notification, routing device R1 120a may change the priority of its outgoing interface so, for example, traffic from host H1 110a to host H2 110b is routed to a different interface of network device 130. In essence, the notification tells routing device R1 120a to find another path (or tunnel) for routing traffic between, for example, this particular host and destination pair (i.e., H1 110a and H2 110b).
Once an interface (e.g., interface e 1/1) is logically shut down due to network address tracking, processing logic 220 may continue to verify the status of the network addresses associated with interface e 1/1. For example, processing logic 220 may continue to send ping (or ARP) commands to the network addresses associated with interface e 1/1 and then re-compute the summation value to determine whether interface e 1/1 should be logically brought back up. Moreover, as set forth above, an interface becoming logically shut down may cause another interface (e.g., interface e 2/1) to be logically shut down. Therefore, logically bringing interface e 1/1 back up can cause interface e 2/1 (and any other interfaces that monitor the status of interface e 1/1) to be logically brought back up.
The following example illustrates the above processing. With reference to FIG. 1, assume for this example that a traffic flow has been established between host H1 110a and host H2 110b via path 150. Moreover, assume that interface e 1/1 is associated with exemplary data structure 500 illustrated in FIG. 5 and that interface e 2/1 is associated with exemplary data structure 600 illustrated in FIG. 6.
With reference to FIG. 5, assume that track network address field 310 stores the network address for host H1 110a, which has a weight assigned to it of 255, that interface list field 320 stores information identifying interface e 2/1, which has a weight assigned to it of 255, that the threshold value in threshold field 330 is 255, and the summation value in summation field 340 is 0.
With reference to FIG. 6, assume that track network address field 310 stores the network address for host H2 110b, which has a weight assigned to it of 255, that interface list field 320 stores information identifying interface e 1/1, which has a weight assigned to it of 255, that the threshold value in threshold field 330 is 255, and the summation value in summation field 340 is 0.
Processing may begin with processing logic 220 determining whether interface e 2/1 can reach host H2 110b and monitoring the status of interface e 1/1. Assume for this example that interface e 2/1 does not receive a reply to a ping request sent to host H2 110b. In response, processing logic 220 may add the weight (255) associated with the network address of host H2 110b to the summation value (0) in summation field 340 for interface e 2/1. The new summation value (255) may then be compared to the threshold value (255) in threshold field 330. Since the new summation value (255) matches the threshold value (255), processing logic 220 logically shuts down interface e 2/1.
During this time, processing logic 220 is also monitoring the status of the network address and interface e 2/1 in its data structure 500 for interface e 1/1. Processing logic 220 will detect that interface e 2/1 has shut down. In response, processing logic 220 may add the weight (255) associated with interface e 2/1 to the summation value (0) in summation field 340 for interface e 1/1. The new summation value (255) may then be compared to the threshold value (255) in threshold field 330 by processing logic 220. Since the new summation value (255) matches the threshold value (255), interface e 1/1 logically shuts down. Processing logic 220 may then use a routing protocol associated with interface e 1/1 to notify routing device R1 120a to find another path for routing traffic between host H1 110a and host H2 110b. Routing device R1 120a may find another path, such as path 160, for routing the traffic between host H1 110a and host H2 110b. In this way, processing logic 220 can notify a routing device R1 120a to switch to another path without physically shutting down interface e 1/1. Moreover, by logically shutting down interface e 1/1, as opposed to physically shutting down interface e 1/1, traffic can still flow between routing device R1 120a and interface e 1/1. For example, interface e 1/1 may include multiple logical interfaces. The above processing may cause one of the logical interfaces of interface e 1/1 (e.g., the one associated with the traffic flow between hosts H1 110a and H2 110b) to be logically shut down, while the remaining logical interfaces remain active.
Thereafter, when routing device R1 120a receives a data unit from host H1 110a for host H2 110b, routing device R1 120a may forward the data unit to interface e 1/2 of network device 130. Interface e 1/2 may forward the data unit to interface e 2/2, which may then forward the data unit to host H2 110b via routing device R3 120c and network 140. In this way, a flow from a source/destination pair (or between subnets) can be moved from one interface in a network device 130 to another interface in network device 130 using layer 3 signaling.
Conclusion
Systems and methods consistent with the principles of the invention improve traffic forwarding within a communications network. In an exemplary implementation, when a problem is detected with respect to communicating a traffic flow, the traffic flow can be moved from one interface in a network device to another interface in the network device using layer 3 signaling.
The foregoing description of exemplary implementations consistent with the principles of the invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. For example, while a series of acts has been described with regard to FIG. 4, the order of the acts may be varied in other implementations consistent with the invention. Moreover, non-dependent acts may be implemented in parallel.
Although embodiments consistent with the principles of the invention teach processing logic 220 monitoring the interfaces, processing data flowing into the interfaces, and sending data out the interfaces, in other embodiments consistent with the principles of the invention, each of the interfaces may have their own processing capability to perform the processing of processing logic 220 in a distributed manner.
No element, act, or instruction used in the description of the present application should be construed as critical or essential to the invention unless explicitly described as such. Also, as used herein, the article “a” is intended to include one or more items. Where only one item is intended, the term “one” or similar language is used. Further, the phrase “based on” is intended to mean “based, at least in part, on” unless explicitly stated otherwise.
The scope of the invention is defined by the claims and their equivalents.

## Claims

1. A method comprising:
detecting, using one or more processors, a problem forwarding a traffic flow via a first input interface of a network device, the traffic flow being received from a second network device;
accumulating weights associated with one or more network addresses, that are determined to be unreachable, to obtain an accumulated value;
comparing the accumulated value to a threshold; and
transferring, using one or more processors, the traffic flow from the second network device to a second input interface of the network device, using layer 3 signaling, when the accumulated value exceeds the threshold.

2. The method of claim 1, where detecting the problem includes:
monitoring the one or more network addresses at a time interval,
where the weights are accumulated based on monitoring the one or more network addresses, and
where the problem is detected based on the accumulated value exceeding the threshold.

3. The method of claim 1, where detecting the problem includes:
detecting that another interface, of the network device, is inoperable,
where the other interface is associated with the first input interface, and
where the problem is detected based on detecting that the other interface is inoperable.

4. The method of claim 1, where transferring the traffic flow includes:
notifying an upstream device to not route the traffic flow to the first input interface.

5. The method of claim 1, further comprising:
monitoring the one or more network addresses to determine whether one or more devices, associated with the network addresses, are reachable,
where detecting the problem is performed in response to monitoring the one or more network addresses, the one or more network addresses being associated with the first input interface.

6. The method of claim 5, where monitoring the one or more network addresses includes:
pinging at least one of the one or more network addresses,
where the problem is detected based on a result of pinging the least one of the one or more network addresses.

7. The method of claim 1, where detecting the problem is performed in response to monitoring at least one other interface of the network device, the at least one other interface being associated with the first input interface.

8. A device comprising:
a memory to store instructions; and
a processor to execute the instructions to:
detect a problem associated with forwarding a traffic flow via a first input interface of the device, the traffic flow being received from another device, where the first input interface is associated with:
another interface of the device, the other interface being associated with a weight value, and
a summation value that
includes the weight value when the other interface is inoperable,

where, when detecting the problem, the processor is to compare the summation value to a threshold value, and
where the problem is detected when the summation value exceeds the threshold value, and
cause the traffic flow, from the other device, to be routed to a second input interface associated with the device, in response to detecting the problem.

9. The device of claim 8, where, when detecting the problem, the processor is to:
receive an event message from the other interface; and
determine that the other interface is down, in response to receiving the event message.

10. The device of claim 8, where the processor is further-to:
monitor one or more other interfaces of the device at a configurable time interval,
where the problem is detected further based on monitoring the one or more other interfaces.

11. The device of claim 8, where, when causing the traffic flow, from the other device, to be routed to the second input interface, the processor is to:
logically shut down the first input interface with respect to the traffic flow.

12. The device of claim 11, where, when logically shutting down the first input interface with respect to the traffic flow, the processor is to:
shut down, only at a layer 3 level, one or more other interfaces of the device with respect to the traffic flow, the one or more other interfaces being associated with the first input interface.

13. The device of claim 8, where, when detecting the problem, the processor is to at least one of:
monitor one or more network addresses associated with the first input interface, or
monitor one or more other input interfaces associated with the first input interface,
where the problem is detected further based on monitoring the one or more network addresses or monitoring the one or more other input interfaces.

14. The device of claim 8, where, when causing the traffic flow, from the other device, to be routed to the second input interface, the processor is to:
notify, using layer 3 signaling, an upstream device to not route the traffic flow to the first input interface.

15. A system comprising:
a device to:
receive, at a first input interface of the device, a traffic flow from an upstream device,
detect a problem associated with forwarding the traffic flow via the first input interface,
where, when detecting the problem, the device is to:
add a weight value, associated with each of one or more interfaces, to obtain a summation value, the one or more interfaces being associated with the first input interface, and
compare the summation value to a threshold value,
where the problem is detected when the summation value exceeds the threshold value, and

cause the traffic flow, from the upstream device, to be routed to a second input interface associated with the device, based on detecting the problem.

16. The system of claim 15, where the device is further to track, at a time interval, at least one of one or more network addresses or the one or more interfaces,
where the one or more network addresses are associated with the first input interface, and
where the problem is detected further based on tracking the at least one of the one or more network addresses or the one or more interfaces.

17. The system of claim 15, where, when causing the traffic flow to be routed to the second input interface, the device is to:
shut down, only at a layer 3 level, another interface with respect to the traffic flow,
where the other interface is associated with the first input interface.

18. The system of claim 15, where, when detecting the problem, the device is further to:
determine that the first input interface is to be logically deactivated based on the comparison of the summation value to the threshold value.

19. The system of claim 18, where the device is further to:
add the one or more weight values to obtain another summation value, and
determine that the first input interface is to be logically reactivated based on a result of a comparison of the other summation value to the threshold value.

20. The system of claim 15, where the device is further to:
deactivate, at a layer 3 level and based on detecting the problem, another interface, of the device, with respect to the traffic flow, and
cause, when the other interface is deactivated, the upstream network device to be notified, via layer 3 signaling, that the other interface is logically deactivated.

21. The system of claim 15, where the device further includes a data structure associated with the first input interface, and
where the data structure includes:
information identifying each of the one or more interfaces,
the threshold value, and
the summation value.