Preserving the order of packets through a device

Abstract

A network device includes one or more sprayers, multiple packet processors, and one or more desprayers. The sprayers receive packets on at least one incoming packet stream and distribute the packets according to a load balancing scheme that balances the number of bytes of packet data that is given to each of the packet processors. The packet processors receive the packets from the sprayers and process the packets to determine routing information for the packets. The desprayers receive the processed packets from the packet processors and transmit the packets on at least one outgoing packet stream based on the routing information.

1 - 82 . (canceled) 
     
     
         83 . A device, comprising:
 at least one bandwidth divider, where each of the least one bandwidth divider is to:
 receive an incoming packet stream, 
 divide packets, included in the received incoming packet stream, where the at least one bandwidth divider, when dividing the packets, is further to:
 determine dispatch times for each of the packets, and 
 schedule the packets for transmission, from the at least one bandwidth divider, at the corresponding dispatch times; and 
 
   a plurality of processors, where each of the plurality of processors is to:
 receive respective packets from the at least one bandwidth divider, 
 process the packets to determine routing information for the packets. 
   
     
     
         84 . The device of  claim 83 , where the each of the plurality of processors is further to:
 attach, based on the determined routing information, an identifier to each of the processed packets, where the identifier is associated with one of a plurality of output ports associated with the device.   
     
     
         85 . The device of  claim 83 , where the at least one bandwidth divider includes:
 a shared memory to store the packets received on the incoming packet stream, where the at least one bandwidth divider is further to divide the packets into a plurality of cells of a predetermined size and store the cells in the shared memory, and   a plurality of transmit interfaces to transmit the cells stored in the shared memory to the plurality of processors.   
     
     
         86 . The device of  claim 85 , where the shared memory includes:
 a plurality of cell memories to store packet data and a pointer, at least one of the cell memories being linked to another one of the cell memories via the pointer in the at least one of the cell memories,   where the plurality of cell memories are linked together to form logical queues in the shared memory, the logical queues corresponding to at least an input queue and an output queue of variable size.   
     
     
         87 . The device of  claim 83 , where the at least one bandwidth divider is further to:
 determine the dispatch times of one of the packets based on time stamps of at least one of:
 beginnings of the packets, or 
 ends of the packets. 
   
     
     
         88 . The device of  claim 83 , where the at least one bandwidth divider is further to:
 store respective packet information, associated with the packets, based on the dispatch times for the packets,   where the at least one bandwidth divider, when storing packet information for the packets, is further to:
 determine that ends of the packets have been received, 
 determine, when the ends of the packets have been received, that entries corresponding to the dispatch times for the packets are empty, and 
 store, when the entries corresponding to the dispatch times for the packets are empty, the packet information for the packets. 
   
     
     
         89 . The device of  claim 88 , where the at least one bandwidth divider is further to:
 determine that entries corresponding to the dispatch times for the packets are not empty,   search for empty entries corresponding to a later dispatch time when the entries corresponding to the dispatch times are not empty, and   store the packet information for the packets in the empty entries.   
     
     
         90 . The device of  claim 83 , where the at least one bandwidth divider, when dividing the packets, is further to:
 balance an amount of bytes, of the respective packets, transmitted to each of the plurality of processors.   
     
     
         91 . A method, comprising:
 receiving, by a network device, at least one incoming packet stream; and   determining, by the network device, a dispatch time for each of packets included in the received at least one incoming packet stream, and   distributing, by the network device and at the corresponding dispatch times, the packets to two or more packet processors included in the network device.   
     
     
         92 . The method of  claim 91 , where distributing the packets includes:
 distributing the packets to the two or more packet processors according to a load balancing scheme,   where the load balancing scheme includes balancing an amount of bytes, of the respective packets, transmitted to each of the two or more packet processors.   
     
     
         93 . The method of  claim 91 , further comprising:
 processing, by the two or more packet processors, the packets to determine routing information for the packets; and   transmitting, by the two or more packet processors and based on the routing information, the processed packets via at least one outgoing packet stream.   
     
     
         94 . The method of  claim 91 , where receiving the packets includes:
 dividing each of the packets into cells of a predetermined size;   storing the cells, of each of the packets, in a shared memory; and   linking together the stored cells to form a logical queue.   
     
     
         95 . The method of  claim 91 , where determining the dispatch times includes: using respective time stamps for at least one of:
 receiving respective beginnings of the packets; or   receiving respective ends of the packets.   
     
     
         96 . The method of  claim 91 , where scheduling the packets for transmission includes:
 storing packet information corresponding to one of the packets in a data buffer when an end of the one of the packets is received;   determining that an entry, corresponding to the dispatch time for the one of the packets, is empty in a data queue; and   storing the packet information for the one of the packets in the data queue in response to determining that the entry corresponding to the dispatch time is empty.   
     
     
         97 . The method of  claim 96 , where scheduling the packets for transmission further includes:
 searching the data queue for an empty entry corresponding to a later dispatch time when the entry corresponding to the dispatch time is not empty; and   storing the packet information for the one of the packets in the empty entry.   
     
     
         98 . The method of  claim 96 , where scheduling the packets for transmission further includes:
 reading packet information from an entry in the scheduling data queue with a dispatch time that corresponds to a current time; and   writing the packet information to an output queue for transmission to one of the two or more packet processors.   
     
     
         99 . A non-transitory computer readable medium to store instructions that are executable on a processor of a network device, the instructions including:
 one or more instructions to receive at least one packet stream; and   one or more instructions to distribute packets, included in the received at least one incoming packet stream, to a plurality of packet processors,   where the one or more instructions to distribute the packets include:
 one or more instructions to distribute the packets to the plurality of packet processors according to a load balancing scheme. 
   
     
     
         100 . The non-transitory computer readable medium of  claim 99 , where the one or more instructions to receive the receive at least one packet stream include:
 one or more instructions to divide each of the packets into cells of a predetermined size;   one or more instructions to store the cells of each of the packets in a shared memory; and   one or more instructions to link together the stored cells to form a logical queue.   
     
     
         101 . The non-transitory computer readable medium of  claim 99 , where the one or more instructions to distribute the packets further include:
 one or more instructions to determine a dispatch time for each of the packets, and   one or more instructions to schedule the packets for transmission, to the plurality of packet processors, at the corresponding dispatch times.   
     
     
         102 . The non-transitory computer readable medium of  claim 99 , where the instructions further include:
 one or more instructions to process, by the plurality of packet processors, the packets to determine routing information for the packets; and   one or more instructions to transmit, by the plurality of packet processors and based on the routing information, the processed packets via at least one outgoing packet stream.   
     
     
         103 . The non-transitory computer readable medium of  claim 102 , where the one or more instructions to process the packets further include:
 one or more instructions to preserve an order of the packets based on respective dispatch times associated with the packets.   
     
     
         104 . The non-transitory computer readable medium of  claim 99 , where the one or more instructions to distribute the packets include:
 one or more instructions to balance an amount of bytes, of the respective packets, distributed to each of the plurality of packet processors.   
     
     
         105 . The non-transitory computer readable medium of  claim 104 , where the one or more instructions to balance the amount of bytes distributed to each of the plurality of packet processors, include:
 one or more instructions to store values relating to a number of bytes of packet data transmitted to a corresponding one of the plurality of packet processors; and   one or more instructions to identify one of the plurality of packet processors to receive one of the packets based on the stored values,   where the one or more instructions to identify one of the plurality of packet processors include:
 one or more instructions to compare the stored values, and 
 one or more instructions to identified one of the stream flow memories the one of the plurality of packet processors with a lowest value, of the stored values. 
   
     
     
         106 . The non-transitory computer readable medium of  claim 105 , where the one or more instructions to store the values further include:
 one or more instructions to identify respective number of bytes of the packets; and   one or more instructions to update the stored values based on the identified number of bytes.