Electrical computers and digital processing systems: multicomput – Computer-to-computer data modifying
Reexamination Certificate
2000-05-25
2004-06-29
Alam, Hosain (Department: 2155)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data modifying
C709S213000, C709S245000, C370S389000
Reexamination Certificate
active
06757742
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to testing and validation of hashing schemes used in a network switch.
2. Background Art
Local area networks use a network cable or other media to link stations on the network. Each local area network architecture uses a media access control (MAC) enabling network interface devices at each network node to access the network medium.
The Ethernet protocol IEEE 802.3 has evolved to specify a half-duplex media access mechanism and a full-duplex media access mechanism for transmission of data packets. The full-duplex media access mechanism provides a two-way, point-to-point communication link between two network elements, for example between a network node and a switched hub.
Switched local area networks are encountering increasing demands for higher speed connectivity, more flexible switching performance, and the ability to accommodate more complex network architectures. For example, commonly-assigned U.S. Pat. No. 5,953,335 discloses a network switch configured for switching layer
2
type Ethernet (IEEE 802.3) data packets between different network nodes; a received data packet may include a VLAN (virtual LAN) tagged frame according to IEEE 802.1q protocol that specifies another subnetwork (via a router) or a prescribed group of stations. Since the switching occurs at the layer
2
level, a router is typically necessary to transfer the data packet between subnetworks.
Efforts to enhance the switching performance of a network switch to include layer
3
(e.g., Internet protocol) processing may suffer serious drawbacks, as current layer
2
switches preferably are configured for operating in a non-blocking mode, where data packets can be output from the switch at the same rate that the data packets are received. Newer designs are needed to ensure that higher speed switches can provide both layer
2
switching and layer
3
switching capabilities for faster speed networks such as 100 Mbps or gigabit networks.
However, such design requirements risk loss of the non-blocking features of the network switch, as it becomes increasingly difficult for the switching fabric of a network switch to be able to perform layer
3
processing at the wire rates (i.e., the network data rate). For example, switching fabrics in layer
2
switches require only a single hash key to be generated from a MAC source address and/or a MAC destination address of an incoming data packet to determine a destination output port; the single hash key can be used to search an address lookup table to identify the output port. Layer
3
processing, however, requires implementation of user-defined policies that include searching a large number of fields for specific values. These user-defined policies may specify what type of data traffic may be given priority accesses at prescribed intervals; for example, one user defined policy may limit Internet browsing by employees during work hours, and another user-defined policy may assign a high priority to e-mail messages from corporate executives. Hence, the number of such user policies may be very large, posing a substantial burden on performance of layer
3
processing at the wire rates.
In addition, network designers need to be able to test alternative hash based table lookup schemes. However, these hash based table lookup schemes cannot be algorithmically evaluated. Hence, simulation has been used to capture statistics, where a simulator generates data packets and sends the data packets to the network switch or a Verilag based representation (i.e., model) of the network switch. Unfortunately, such simulation techniques have limited utility in evaluating hash based table lookup schemes. In particular, the validation of the effectiveness of a hash based table lookup requires the generation of a substantial amount of data; if this data was to correspond to packets on a computer network, the time required for the simulator to generate the simulated packets would be enormous. In addition, it is often difficult to evaluate the effectiveness of the hashing function within the network switch, since performance issues may be caused by other system components.
SUMMARY OF THE INVENTION
There is a need for an arrangement that enables the evaluation of the effectiveness of a hash based table lookup scheme in an efficient manner.
There is also a need for an arrangement that enables multiple hash based lookup schemes to be evaluated in an efficient manner to determine the optimum hash based table lookup scheme for a network.
These and other needs are attained by the present invention, where a computer-based system is configured for generating a first data structure having entries representing respective network nodes having layer
2
and layer
3
network addresses. The system generates a second data structure, having a plurality of data packet headers, by selecting source and destination pairs from the first data structure and combining the respective layer
2
and layer
3
network addresses from the respective selected source and destination pairs with randomly-generated numbers representing layer
3
payload data. The second data structure is supplied to a switch model configured for parsing the layer
3
network addresses according to selected hash functions. Hence, the computer-based system is able to evaluate the selected hash functions based on a time-independent analysis, eliminating the necessity of building an actual network in hardware or simulating network traffic over a period of time.
One aspect of the present invention provides a method in a computer system. The method includes generating and storing on a tangible medium a first data structure having entries, each entry representing a network node and having a corresponding layer
2
and layer
3
network address. The method also includes generating a second data structure having a plurality of data packet headers, by selecting source and destination pairs from the first data structure, and combining the layer
2
and layer
3
network addresses of the selected source and destination pairs with respective randomly-generated numbers representing layer
3
payload data to form the data packet headers, and evaluating a hash function by supplying the second data structure to a switch model configured for parsing at least a portion of the data packet headers according to the hash function, and monitoring results of the parsing by the hash function. Generation of the first data structure having entries representing network nodes with layer
2
and layer
3
network addresses enables use of a data representation for analyzing network behavior, as opposed to the necessity of generating actual data packets using an implemented local area network or a simulator. Moreover, generation of the second data structure having the data packet headers enables optimized computer-based evaluation of the hash function by the switch model, since the switch model has immediate access to all data packet headers, minimizing processing time during the evaluation procedure.
Another aspect of the present invention provides a computer-based system comprising a controller, a switch model, and an evaluation module. The controller is configured for generating and storing on a tangible medium a first data structure having entries, each entry representing a network node and having a corresponding layer
2
and layer
3
network address. The controller is also configured for generating a second data structure having a plurality of data packet headers, by selecting source and destination pairs from the first data structure, and combining the layer
2
and layer
3
network addresses of the selected source and destination pairs with respective randomly-generated numbers representing layer
3
payload data to form the data packet headers. The switch model is configured for parsing at least a portion of the data packet headers according to at least one hash function, and the evaluation module is configured for evaluating the at least one hash function by supplying the second dat
Advanced Micro Devices , Inc.
Alam Hosain
Duong Oanh
Manelli Denison & Selter PLLC
Turkevich Leon R.
LandOfFree
Computer-based system for validating hash-based table lookup... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer-based system for validating hash-based table lookup..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer-based system for validating hash-based table lookup... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3303556