Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2000-07-25
2004-11-30
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000
Reexamination Certificate
active
06826148
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to the field of computer systems and, more particularly to communications protocols within computer systems and/or networks, and communication routing or switching within computer systems and/or networks.
2. Description of the Related Art
Devices in a communications network may communicate with one another by sending packets to each other. These packets may correspond to an operation that one device seeks to perform with the assistance of another device. Packets may be transferred between devices using a network which may include a fabric. A network generally may comprise a number of devices that are configured to convey packets between any number of devices.
At times, however, adverse transmission conditions may occur in the network when one device is sending a packet to another device on the network. For example, the network may become overly congested with packets traveling between devices. Another adverse condition that may occur in networks is corruption of a packet (e.g. an ECC error, parity error, checksum error, etc.). A fault condition (e.g. failure in the fabric) that prevents a packet from proceeding along its proposed route is another adverse condition. One adverse condition resolution scheme in packet routing protocols involves dropping packets in response to an adverse transmission condition within one or more devices (e.g. a switch, switching device, endpoint, node, etc.) in the network. In the case of congestion, a device within the network may drop one or more packets randomly or selectively to instantaneously reduce the packet load. By dropping one or more packets, the device can free up sufficient resources to service the remaining packets. Corrupted packets may also be dropped. For a fault condition, all packets reaching a fault point may have to be dropped and resent using a different route.
When a packet is dropped, the device that originated the packet needs to detect that it has been dropped so that it can be resent. Detection of dropped packets may be accomplished by a time-out mechanism at at receiving device when it fails to receive an expected packet, by a time-out mechanism at a sending device where the sending device is waiting for a signal from a receiving device that a packet has been received, or by sending a negative acknowledgement (NACK) from the device that dropped the packet to the sending device.
Each of these detection methods has its problems, however. Where a time-out mechanism is used, a device needs to ensure that it does not resend a packet until it is certain that the original packet has been dropped. The device must generally wait a period of time to ensure that the packet has been dropped and this waiting period results in a performance penalty. Where a NACK to the sending device is used to signal a dropped packet, a dropped packet is unknown to the receiving device, no matter how far through the network the dropped packet traveled before being dropped. The NACK propagates back only to the sender and the network resources consumed by the dropped packet are wasted. An apparatus and method of handling adverse transmission conditions that minimizes the drawbacks of the above methods is needed.
SUMMARY
The problems outlined above are in large part solved by the use of the apparatus and method described herein. Generally speaking, an apparatus and method is contemplated for implementing a routing scheme using intention packets. At times, a switching device within a network may detect a fault, corruption, or congestion. When a switching device detects a fault, corruption, or congestion, it may drop one or more packets to resolve the fault, corruption or congestion. When a packet is dropped, the switching device that dropped it may create an intention packet that corresponds to the dropped packet. The switching device may then route the intention packet to the destination device specified by the dropped packet. The intention packet may be routed along a different route than the original route specified by the dropped packet. The intention packet may be much smaller than the dropped packet and may include parts of a portion of the dropped packet. The intention packet may also record the route it takes to get to the destination device.
A device may react to receiving an intention packet based on the information in the intention packet as well as its own characteristics. The information in the intention packet may indicate whether the dropped or modified packet was a request or a response to a request. If the dropped or modified packet was a request, then the device that receives the intention packet, i.e. the receiving device, may send a signal to the requesting device that its request has been dropped. The receiving device may also perform an operation that corresponds to the request in anticipation of receiving the resent packet. If the dropped or modified packet was a response to a request, then the requesting device may receive the intention packet. The requesting device may reschedule the request in response to receiving the intention packet and may convey a subsequent packet that includes the request to the receiving device. The requesting device may be configured optimize the resending of the request by rescheduling the request for a more appropriate time or by merging the request with a subsequent request.
A device in a network may detect a fault. A fault may be a condition that prevents a packet from continuing along its intended or proposed route. For exanple, a fault may condition may result from failure of a downstream switching device. If a device detects a fault, the operation corresponding to the packet may be aborted, and the device may generate an intention packet and convey the intention packet to the destination device along an alternate route. The device may also drop all or a portion of the packet. The destination device may forward the intention packet to the initiating device. The initiating device may use the route record of the intention packet to reconfigure its routing algorithm before resending the original packet.
A device may also detect a fault at a destination device. In this case, the operation corresponding to the packet may be aborted, and the device may generate an intention packet and convey that packet to the initiating device to indicate a destination failure. The device may also drop all or a portion of the original packet. The initiating device may resend the original packet or may send a packet to an alternative destination in response to an intention packet that indicates a destination failure.
Instead of or in addition to a fault condition, a device may detect other adverse transmission conditions such as corruption and congestion. For example, at times, one or more devices in a network may become congested. When a device becomes congested, it may drop one or more packets to alleviate some of the congestion. The devices may each include one or more ports and they may support a particular amount of resources (such as bandwidth, buffers, etc.) in and out of each of their ports. When a packet or a portion of a packet arrives at a device, the device may determine what port the packet will need and the amount of resources required by the packet on that port. If the required resources are available for the packet on the port, then the switching device may route the packet to a next device. If the required resources are not available for the packet on the port, then the device may drop at least a portion of the packet. When a packet is dropped, the device that dropped it may create an intention packet that corresponds to the dropped packet. The switching device may then route the intention packet to the destination device specified by the dropped packet. In one embodiment, a device may consider the age of a packet as well as the amount of resources already consumed by the packet in determining which packet to drop.
A device in a network may detect corruption of a packet (e.g. ECC error, parity error, checksum error)
Kowert Robert C.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Sun Microsystems Inc.
Vanderpuye Kenneth
LandOfFree
System and method for implementing a routing scheme in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for implementing a routing scheme in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for implementing a routing scheme in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3320977