The present invention relates generally to communication networks, and, more particularly, to detecting and locating a misbehaving device in a network domain.
In today""s information age, communication devices, such as computers and computer peripherals, are often internetworked over a data communication network. The data communication network typically includes a number of interconnected routers that enable data to be transferred from a source communication device to a destination communication device. The number of interconnected routers form a router domain within the router network.
Within a particular router domain, it is common for at least some of the routers to be interconnected with multiple neighboring routers, in what is often called a xe2x80x9cmeshxe2x80x9d configuration. The mesh configuration may provide multiple paths from the source communication device to the destination communication device, where each path traverses some number of routers. However, when transferring data from the source communication device to the destination communication device, it is preferable to route the data over only one path from the source communication device to the second communication device.
Therefore, in order to route information from the source communication device to the destination communication device over the data communication network, the routers must first agree on a preferred path from the source communication device to the destination communication device. The routers select the preferred path based upon routing information that is exchanged using a networking protocol, such as the Routing Information Protocol (RIP), the Open Shortest Path First (OSPF) protocol, or the Hello protocol. Each networking protocol utilizes a particular decision algorithm to select the preferred path based on a number of network parameters, including, but not limited to, the number of routers traversed by a path, the bandwidth of the communication links between routers, and the congestion level at each router, and therefore the preferred path may be different depending upon the networking protocol employed.
Thus, each router relies on the routing information it receives from the other routers in order to determine appropriate routes within the router network. Consequently, if a router receives invalid routing information, then the router may establish invalid routes that can result in performance degradation, data loss, or total failure within the router network. In order to prevent such consequences, it is preferable for each router to verify the routing information and authenticate the source of the routing information before using the routing information to establish routes. Furthermore, if a router or other network device (referred to hereinafter as a xe2x80x9cmisbehaving devicexe2x80x9d) is producing and distributing invalid routing information, then it is desirable for that misbehaving device to be located so that the misbehaving device can be isolated or fixed. Therefore, a technique for locating a misbehaving device is needed.
In accordance with one aspect of the invention, a network domain of a communication network is divided into a number of sectors. Each sector includes an authenticating device, such as a secure and trusted authority (STA), as well as a number of communication devices, such as routers. A two-level authentication scheme is used to allow any of the communication devices in the network domain to determine the sector in which a misbehaving communication device is operating. The authenticating device within a sector can determine if a misbehaving communication device is within the same sector as the authenticating device.
Specifically, each sector is assigned a sector key. The sector key for each sector is distributed to all communication devices and authenticating devices. Furthermore, each communication device is assigned a device key. The device key is shared only between the device and the authenticating device within the same sector.
When an originating device in an originating sector transmits data, the originating device transmits a packet that includes at least the data, a sector tag, and a device tag. In a preferred embodiment of the present invention, the sector tag is computed using a one-way hash function based upon the data and the sector key. In a preferred embodiment of the present invention, the device tag is computed using a one-way hash function based upon the data, the sector tag, and the device key.
A receiving device in a receiving sector authenticates the originating sector for the packet by computing a-sector verification tag and comparing the sector verification tag to the sector tag in the packet. In a preferred embodiment of the present invention, the sector verification tag is computed using a one-way hash function based upon the data and the sector key. The receiving device determines the sector key by determining the originating sector for the packet, preferably using a sector key identifier included in the packet, and retrieving the sector key from a sector key table maintained by the receiving device. If the sector verification tag does not match the sector tag in the packet, then the receiving device drops the packet. If the sector verification tag matches the sector tag in the packet, then the receiving device proceeds to verify the data in the packet to determine whether the data is valid or invalid. If the data is invalid, then the packet is forwarded to one or more authenticating devices.
An authenticating device determines whether the packet originated at one of the communication devices within the same sector as the authenticating device. Specifically, in order to determine if a particular communication device is the originating device, the authenticating device computes a device verification tag using the device key corresponding to that communication device, and compares the device verification tag to the device tag in the packet. In a preferred embodiment of the present invention, the device verification tag is computed using a one-way hash function based upon the data, the sector tag, and the device key. If the device verification tag matches the device tag in the packet, then the authenticating device terminates processing of the packet, as the authenticating device successfully located the originating device. If the device verification tag does not match the device tag in the packet, then the authenticating device repeats the authentication process using the device key for another communication device in the sector. If the authenticating device fails to find a communication device within the sector that is authenticated as the originating device, then the authenticating device may forward the packet to another authenticating device in a different sector and/or notify the network administrator that there is an unidentified misbehaving communication device.