Abstract:
A system having multiple arbiters is constructed to reduce the chances of arbiters synchronizing with one another. Each arbiter includes a random process that introduces randomness into an arbitration scheme performed by the arbiter. Because of the randomness, the arbiters will not tend to synchronize with one another, even when receiving an identical stream of input values.

Description:
BACKGROUND OF THE INVENTION 
     A. Field of the Invention 
     The present invention relates generally to flow control, and more particularly, to data flow control and arbitration. 
     B. Description of Related Art 
     Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at line rate when the new functionality was added. 
     To meet the new demands, purpose-built routers were designed. Purpose-built routers are designed and built with components optimized for routing. They not only handled higher line rates and higher network traffic volume, they also added functionality without compromising line rate performance. 
     A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A switching fabric may be implemented in the router to carry the packets between the ports. In a high-performance purpose-built router, the switching fabric may transmit a large amount of information. If too much information is simultaneously sent to the switching fabric, or if too much information is destined for a specific destination on the switching fabric, the switching fabric or portions of the switching fabric may become congested. 
     In an effort to efficiently use the switching fabric and to ensure that any particular destination is not unfairly favored over other destinations, arbiters are used to control the timing of data flowing from a source to various destinations on the switching fabric. Separate arbiters control data at each source. With this architecture, however, a problem can occur when different sources try to send data to the same set of destinations. The different arbiters have a tendency to come into synchronism (also called in-stride) with one another, and may thus send a high concentration of data to a single destination, potentially overwhelming the portions of the switch fabric leading to that destination, and then all move on to the next destination and overwhelm it, and so on. 
     Synchronization of arbiters is a problem which can occur in any system having multiple arbiters operating in parallel. Therefore, the problem exists in many environments other than routing and networking. 
     It therefore would be desirable to implement arbiters at various data transmission sources that do not tend to come in-stride with one another, even when different sources attempt to send to the same set of destinations. 
     SUMMARY OF THE INVENTION 
     Systems and methods consistent with the invention provide, among other things, arbiters that control the sending of information in a manner such that arbiters do not become in-stride. 
     One aspect of the present invention is directed to an arbiter. The arbiter comprises a randomization table, a mapping component, an arbiter component, a de-randomization table, and an unmapping component. The randomization table stores randomization values. The mapping component modifies data items based on the randomization values. The arbiter component selects certain ones of the modified versions of the data items based on an arbitration scheme. The de-randomization table stores de-randomization values based on the randomization values stored in the randomization table, and the unmapping component converts the selected modified data items from the arbiter component back to original versions of the data items based on the de-randomization values. 
     An arbiter consistent with a second aspect of the present invention includes a register, a random generator, and an arbiter. The register stores representations of data items and includes a plurality of bits. Each bit represents information of a data item and is set when the data item is waiting to be transmitted. A random generator generates a random pointer that refers to one of the bits of the register. The arbiter selects data items by checking each of the plurality of bits of the register. 
     A third aspect of the present invention is directed to a method of arbitrating among multiple data items. The method includes randomizing the data items, selecting certain ones of the data items in accordance with an arbitration scheme based on the randomized the data items, and de-randomizing the selected data items. 
    
    
     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 a block diagram illustrating an exemplary routing system in which the present invention may be implemented; 
     FIG. 2 is a block diagram illustrating portions of the routing system shown in FIG. 1 in additional detail; 
     FIG. 3 is a diagram illustrating an implementation of a communication component shown in FIG. 2; 
     FIG. 4 is a diagram illustrating one of the arbiters shown in FIG. 3 in additional detail; 
     FIG. 5 is a flow chart illustrating operation of the arbiter shown in FIG. 4; 
     FIG. 6 is diagram of a simplified exemplary embodiment of the arbiter shown in FIG. 4; and 
     FIG. 7 is a diagram illustrating an arbiter consistent with a second aspect of the present invention. 
    
    
     DETAILED DESCRIPTION 
     The following detailed description of the invention refers to the accompanying drawings. The same reference numbers in different drawings 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 equivalents. 
     As described herein, in one implementation, destination information entering an arbiter is re-mapped to a different temporary destination. The re-mapping is based on a random process in each arbiter. The arbiter operates on the re-mapped destinations. The output destination from the arbiter is transformed back to its original destination based on a de-randomization process. Even if identical destination information is transmitted to multiple arbiters, the random re-mapping of the destination information keeps the arbiters from synchronizing. 
     System Description 
     FIG. 1 is a block diagram illustrating an exemplary routing system  42  in which the present invention may be implemented. System  42  comprises packet forwarding engines (PFEs)  44 ,  46  . . .  48 , a switch fabric  50 , and a routing engine (RE)  52 . System  42  receives a data stream from a physical link, processes the data stream to determine destination information, and transmits the data stream out on a link in accordance with the destination information. 
     RE  52  performs high level management functions for system  42 . For example, RE  52  communicates with other networks and systems connected to system  42  to exchange information regarding network topology. RE  52  creates routing tables based on the network topology information and forwards the routing tables to PFEs  44 ,  46 , and  48 . The PFEs use the routing tables to perform route lookup for incoming packets. RE  52  also performs other general control and monitoring functions for system  42 . 
     PFEs  44 ,  46 , and  48  are each connected to RE  52  and switch fabric  50 . PFEs  44 ,  46 , and  48  receive data on ports connecting physical links connected to a wide area network (WAN). Each physical link could be one of many types of transport media, such as optical fiber or Ethernet cable. The data on the physical link is formatted according to one of several protocols, such as the synchronous optical network (SONET) standard, an asynchronous transfer mode (ATM) technology, or Ethernet. 
     PFE  44  will be used as an example to discuss the operations performed by PFEs  44 ,  46 , and  48  consistent with the principles of the invention. PFE  44  processes incoming data by stripping off the data link layer. PFE  44  converts header information from the remaining data into a data structure referred to as a notification. 
     For example, in one embodiment, the data remaining after the data link layer is stripped off is packet data. PFE  44  converts the layer 2 (L2) and layer 3 (L3) packet header information included with the packet data into a notification. PFE  44  stores the notification, some control information regarding the packet, and the packet data in a series of cells. In one embodiment, the notification and the control information are stored in the first two cells. 
     PFE  44  performs a route lookup using the notification and the routing table from RE  52  to determine destination information. PFE  44  may also further process the notification to perform protocol-specific functions, policing, and accounting, and might even modify the notification to form a new notification. 
     If the destination indicates that the packet should be sent out on a physical link connected to PFE  44 , then PFE  44  retrieves the cells for the packet, converts the notification or new notification into header information, forms a packet using the packet data from the cells and the header information, and transmits the packet from the port associated with the physical link. 
     If the destination indicates that the packet should be sent to another PFE via switch fabric  50 , then PFE  44  retrieves the cells for the packet, modifies the first two cells with the new notification and new control information, if any, and sends the cells to the other PFE via switch fabric  50 . The receiving PFE uses the notification to form a packet using the packet data from the cells, and sends the packet out on the port associated with the appropriate physical link of the receiving PFE. 
     In summary, RE  52 , PFEs  44 ,  46 , and  48 , and switch fabric  50  perform routing based on packet-level processing. PFEs store each packet using cells while performing a route lookup using a notification, which is based on packet header information. A packet might be received on one PFE and go back out to the network on the same PFE, or be sent through switch fabric  50  to be sent out to the network on a different PFE. 
     FIG. 2 is a block diagram illustrating portions of routing system  42  in additional detail. PFEs  44 ,  46 , and  48  connect to one another through switch fabric  50 . Each of the PFEs may include one or more physical interface cards (PICs)  201 - 202  and flexible port concentrators (FPCs)  205 . 
     PICs  201  transmit data between a WAN physical link and FPC  205 . Different PICs are designed to handle different types of WAN physical links. For example, PIC  201  may be an interface for an optical link while PIC  202  may be an interface for an Ethernet link. Although FIG. 2 shows two PICs connected to the FPCs, in other embodiments consistent with the invention there can be a single PIC or more than two PICs connected to an FPC. 
     Switch fabric  50  includes switches  220  that transmit cells through the fabric  50 . The switches may be connected via optical links and may be organized into multiple fabric planes  230 . In one embodiment, four fabric planes  230  may be used. 
     FPCs, such as FPC  205 , handle packet transfers to and from PICs  201  and  202 , and switch fabric  50 . For each packet it handles, FPC  205  performs the previously-discussed route lookup function. FPCs  205  communicate with switch fabric  50  through a fabric communication component  207  (labeled as Nout). Communication component  207  handles the protocols associated with transmitting cells from and receiving cells from switch fabric  50 . 
     FIG. 3 is a block diagram illustrating an implementation consistent with the present invention of one of communication components  207 . Communication component  207  comprises a notification queue manager  305 , a notification buffer pool  306 , a grant pending queue  307 , a fabric request controller  308 , a packet reader  309 , and a data buffer  310 . 
     Data transmission from communication component  207  begins when notification queue manager  305  receives a notification, signifying that notification and data cells are to be sent to another FPC. Upon receiving the notification, notification queue manager  305  stores the notification in notification buffer pool  306 . In response, notification buffer pool  306  returns an address defining where the notification is stored in notification buffer pool  306 . Notification queue manager  305  stores the received address in one or more internal queues. Notification queue manager  305  arbitrates across its internal queues to select a notification for processing and sends the address of the notification to grant pending queues  307 . Grant pending queue  307  use the address to retrieve the selected notification from buffer pool  306 . 
     Grant pending queue  307  requests permission to send data cells associated with the notification by sending a request signal to fabric request controller  308 . More particularly, when grant pending queue  307  receives a selected address from notification queue manager  305 , it sends a request that includes the destination and the number of cells in the packet to fabric request controller  308 . Grant pending queue  307  holds the outgoing notification until permission to send the packet (called a grant) is received by fabric request controller  308 . When permission is granted, grant pending queue sends the notification to packet reader  309 , which reads out data cells associated with the notification and forwards the cells to data buffer  310  for transmission over the switch fabric  50 . 
     Fabric request controller  308  transmits requests and packet reader  309  transmits data cells to other destinations, such as other FPCs connected to switch  50 , based on arbiters  320 . Arbiters  320  may be round-round arbiters (RRAs) that arbitrate sending requests and data cells in a manner that gives equal priority to all destinations. 
     In a conventional round robin arbiter, requests are distributed with equal priority across all possible destinations. For example, if three sources corresponding to three destinations were under the control of a round robin arbiter, the round robin arbiter may sequentially check whether the first source, the second source, and then the third source have any data to send. After checking the third source, the round robin arbiter starts with the first source. Accordingly, the round robin arbiter gives equal priority to each of three sources. Other types of arbiters may also be used. 
     The implementation and operation of arbiters consistent with the present invention will now be described in detail with reference to FIGS. 4-7. 
     Operation and Implementation of Arbiters  320   
     FIG. 4 is a block diagram illustrating one of arbiters  320 . Arbiter  320  includes a randomization table  401  and a corresponding de-randomization table  402 . Arbiter  320  also includes a mapping component  420 , a destination vector  404 , a round robin arbiter  405 , and unmapping component  421 . 
     Mapping component  420  uses information in randomization table  401  to generate new “mapped” cell destinations for the cell destinations received by arbiter  320 . Similarly, unmapping component  421 , based on information in de-randomization table  402 , recovers the original cell destinations. A destination vector  404  stores indications of the destinations to which the received cells are to be transmitted. Round robin arbiter  405  implements a conventional round robin arbitration scheme on the destinations stored in destination vector  404  and transmits selected destinations to unmapping component  421 . 
     Arbiter  320  additionally includes a random generator  410 , which is used to populate tables  401  and  402 . Random generator  410  may be implemented as a dedicated hardware circuit, in software, or a combination of hardware and software. 
     In one implementation, switch fabric  50  connects 144 destination devices, such as 144 FPCs. Accordingly, the destination vector may be a 144bit register, with each bit corresponding to one of the possible destinations. In this implementation, randomization table  401  and de-randomization table  402  are implemented as a table of 144 rows, with each row storing a value that indexes one of the destinations. Thus, if the destinations are labeled as destinations zero to 143, each row in table  401  may be implemented as an eight bit register that stores a value between zero and 143. 
     FIG. 5 is a flow chart illustrating operation of the arbiters  320  consistent with an aspect of the present invention. Random generator  410  begins, during an initial power-up or reset operation of routing system  42 , by populating randomization table  401  and de-randomization table  402 . (Acts  501  and  502 ). Random generator  410  populates tables  401  and  402  based on a series of random or pseudo-random numbers such that the values in randomization table  401  are essentially a shuffled version of the possible destinations. More specifically, each of the 144 rows of the randomization table  401  contains a random value between zero and 143, where each of the values between zero and 143 is used once and none of the values are repeated. 
     For illustration purposes, a simplified version of randomization table  401  and a number of neighboring components are shown in FIG.  6 . Randomization table  601  is illustrated as having four rows (labeled as rows zero through three), where each row contains a value between zero and three. As shown, random generator  410  has populated table  601  such that row zero includes the destination value two, row one includes the destination value three, row two includes the destination value one, and row three includes the destination value zero. De-randomization table  602  is filled with values that reverse the mapping dictated by randomization table  601 . 
     Based on the value in the randomization table  601 , mapping component  420  maps incoming destinations to new mapped destinations. For example, in FIG. 6, the mapping component  420  would map cells intended for destination zero to destination two. 
     Returning to FIG. 5, for each received destination address, mapping component  420  changes the received destination to a new mapped destination as described above (Acts  503  and  504 ). Mapping component  420  next sets a bit in destination vector  404  corresponding to the mapped destinations (Act  505 ). If, for example, data vector  404  is a 144-bit vector, and an incoming cell destined for destination two was mapped to destination ten, mapping component  420  sets bit ten of destination vector  404  to indicate that cells corresponding to this destination are waiting to be selected by round robin arbiter  405 . In the example of FIG. 6, destination vector  604  is a four-bit vector having bits one and three set (corresponding to received destinations two and one, respectively). 
     Round robin arbiter  405  selects destinations from destination vector  404  (Act  506 ). After selecting the destination, round robing arbiter  405  clears the bit corresponding to the destination. In one implementation, round robin arbiter  405  is a conventional round robin arbiter that gives equal priority to each destination. In this implementation, round robin arbiter  405  would sequentially check bits zero to 143 of destination vector  404  and then begin checking back at destination zero of destination vector  404 . 
     For each selected destination, unmapping component  421  converts (unmaps) the destination to its original value using de-randomization table  402 . (Acts  507  and  508 ). The cell corresponding to the unmapped destination is then transmitted over switch fabric  50 . (Act  509 ). 
     In the implementation described above, the functionality of a conventional round robin arbiter is modified using relatively simple circuitry positioned before and after the round robin arbiter. The circuitry randomizes and then de-randomizes values input to the round robin arbiter. Finally, the randomization process for multiple arbiters in the system are independent of one another, so that even if the multiple arbiters receive the same input value, they will not exhibit a tendency to become in-stride with one another. 
     FIG. 7 is a block diagram of an implementation of an arbiter, labeled as arbiter  720 , consistent with a second embodiment of the present invention. As with the arbiter shown in FIG. 4, arbiter  720  includes a destination vector, labeled as destination vector  704 . Inputs to the destination vector  704  are not mapped based on a randomization table, but are instead directly set in the destination vector  704  based on the received destination (i.e., a cell intended for the 10 th  destination sets the 10 th  bit in the destination vector  704 ). 
     A randomization arbiter  705  is connected to destination vector  704  and arbitrates among the destinations set in destination vector  704 . Randomization arbiter  705  is based on a modified round robin arbiter  706  that periodically receives a pointer to a starting destination within destination vector  704  from a random generator, such as linear feedback shift register (LFSR)  707 . LFSRs can produce pseudo-random numbers at very high frequencies. Hardware constructions for LFSRs are well known in the art and will not be described further herein. Other circuits for generating random numbers, in addition to LFSRs, may alternatively be used. 
     In operation, round robin arbiter  706  receives a pointer value from LFSR  707  that indicates at which destination address in destination vector  704  the round robin arbiter should begin. If, for example, the pointer value is ten, round robin arbiter  705  begins by checking the 10 th  bit in destination vector  704 . The round robin arbiter will then sequentially check the bits in the destination vector  704  up through the 143 rd  bit, and then wrap around to bit zero and sequentially check the bits in destination vector  704  up through bit nine. After bit nine, round robin arbiter  706  gets a new pointer value from LFSR  707 , and beginning at the new value, checks each of the bits in destination vector  704 . The new pointer value generated by LFSR  707  may be generated periodically or in response to a new pointer request signal from round robin arbiter  706 . 
     Arbiter  720  provides similar functionality as the arbiter shown in FIG. 4, due to the fact that both arbiters introduce an element of randomness into their selections. More particularly, multiple randomization arbiters  720  in a system receive different LSFR initial seed values, and will thus not have a tendency to become in-stride with one another. 
     Although described in the context of a purpose-built router, concepts consistent with the present invention can be implemented in any system that uses multiple arbiters where it is desirable to keep two or more of the arbiters from becoming in-stride with one another. Although the arbiters described herein arbitrate across destinations, an arbiter consistent with the principles of the invention may be used in any system requiring arbitration. For example, data items other than destinations may be randomized. 
     The foregoing description of preferred embodiments of the present 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. 
     The scope of the invention is defined by the claims and their equivalents.