CN100521655C - Dynamic sharing device of physical queue based on the stream queue - Google Patents

Abstract

The invention belongs to the technical field of business flow management in a computer network, and is characterized in that it contains: the device contains: a physical storage device RAM, and a writing module integrated on the FPGA/ASIC, a scheduling module, a RAM management module, and a dynamic sharing list , a dynamic sharing module; wherein, the physical storage device RAM is used to cache data packets and the next pointer of each data block; the data packets are written into the address corresponding to the RAM; the scheduling module is active according to the scheduled scheduling mode Scheduling in the flow of state; RAM management module manages the data structure of data packets stored in RAM according to the set method; dynamic sharing list maintains the mapping relationship between active flow and physical queue; dynamic sharing provides a fast search mechanism , the insertion mechanism, and the deletion mechanism. The device reduces the required physical queue and realizes queuing according to flow.

Description

Per-flow physical queue dynamic sharing device

technical field

The present invention is a physical queue dynamic sharing device that implements per-flow queuing (per-flow queuing) for business flows at wire speed, and can be applied to high-speed broadband network forwarding equipment to realize service quality (QoS) guarantee, and belongs to computer network field.

Background technique

By adopting per-flow queuing (per-flow queuing) cache management in computer network forwarding devices such as routers and switches, the Quality of Service (QoS) between different business flows can be strictly guaranteed. Traditionally, queuing per flow requires physical isolation of different flows for management, that is to say, a separate physical queue must be maintained for each flow. Through network measurement and other means, it is found that in a high-speed broadband network (such as a network with a bandwidth of 2.5Gbps and 10Gbps), more than one million different active service flows can coexist at the same time, so it is necessary to maintain millions of physical service flows for each flow queuing management method Queue, and this will make the management unit take up too many resources and consume too much processing time, making it difficult to implement. Therefore, although the buffer management method of queuing up per flow can provide QoS guarantee, the traditional concept is considered not scalable and cannot be implemented in high-speed broadband networks.

Although more than one million different active service flows can coexist in high-speed broadband, through simulation experiments on real network data, it is found that the number of queues whose length is not empty at any time does not exceed the order of hundreds or thousands. Intuitive explanation: each data packet is stored in a forwarding device such as a router for a very short time (ms level, or even ns level), and when the arrival interval between the same flow packets is greater than this order of magnitude, the queue will be temporarily empty Condition. Based on this fact, the present invention proposes an expandable device that physically only maintains a small number of queues (for example, less than 1k queues), and ensures that at any time, different active service flows are The forwarding device can be assigned to a separate queue to avoid multiple flows in one queue, thereby realizing queuing per flow and ensuring the quality of service.

Contents of the invention

In the per-flow queuing storage management system, in order to determine how many resources need to be reserved, the number of flows transmitted on the link can be measured by the following methods: 1) Flow classification Classify the packets according to the 5-tuple in the data packet header, Different data packets belong to different streams; 2) judging whether it is a stream being transmitted. When the first data packet of a flow arrives, it is considered that the flow starts to transmit; in order to detect whether the transmission of the flow ends, τ timeout is set. If no data packet arrives in the flow within τ time, the transmission process of the flow is considered to be over. When measuring, set τ to 60 seconds or even longer. Measurements show that the number of flows passing through nodes can reach hundreds of thousands or even millions. Based on this result, if the per-flow queuing system maintains one queue for each flow, the number of queues will also reach hundreds of thousands or even millions, making the storage management of per-flow queuing difficult to implement in high-speed routers. However, in fact, in the process of stream transmission, the queues corresponding to some streams do not store data packets at certain moments. Although their transmission is not over at this time, at these moments, the data packet storage system does not need to save queues for them. . Experimental and modeling results show that the actual number of occupied queues is much smaller than the number of concurrently transmitting streams. Based on this, only a small number of queues need to be implemented in the data packet storage system, and the purpose of queuing for each flow is achieved through the way of dynamic physical queues.

The present invention proposes an expandable device applicable to high-speed broadband networks that can realize queuing per flow at a wire speed. Through a dynamic sharing mechanism, a large number of service flows can be queuing per flow in a small number of physical queues, ensuring that the queuing of a large number of service flows is performed in any Different service flows will not be cached in the same physical queue at any time. Two stream states are defined: 1) active state. When a flow stores packets in the physical queue, it is considered that the flow is in an active state; 2) a silent state. When all packets stored in a network forwarding device for a flow have been forwarded, the flow is considered to be in a silent state until no new packets belonging to the flow arrive. A physical queue is occupied only when a flow is active, and correspondingly, the mapping relationship between its flow number (that is, the current active flow) f _n and the physical queue PQ _q can be established f _n →PQ _q , and the set {f _n →PQ _q } is called an active flow map. When a flow changes from active to silent, the mapping from the corresponding flow number to the physical queue needs to be deleted from the active flow mapping, and the corresponding physical queue should be released; when the flow changes from silent to active, it needs to be assigned a For a new physical queue, add the mapping of its flow number to the physical queue in the active flow list.

The system structure diagram of the device of the present invention is shown in Fig. 1 as the change curve of the number of coexisting streams with time, wherein the solid line is the curve of OC-192, and the dotted line is the curve of OC-48.

Fig. 2 is a curve of the number of occupied physical queues over time, in which the lower triangle marked curve is the curve of OC-192, and the upper triangle marked curve is the curve of OC-48.

Figure 3 is the operational complexity when using the linked list structure to organize the sub-tables of the dynamic shared list, where the lower triangle marked curve is the curve of OC-192, and the upper triangle marked curve is the curve of OC-48; (a) shows that the search has been active In the case of a flow, Figure (b) is the case of inserting a new active flow into the physical queue map.

Fig. 4 Operational complexity when using a binary search tree to organize the sub-tables of a dynamic shared list, where the lower triangle marked curve is the curve of OC-192, and the upper triangle marked curve is the curve of OC-48; (a) shows that the search already exists In the case of an active flow, Figure (b) is the case of inserting a new active flow into the physical queue map.

Figure 5. The average time for the dynamic sharing management module to return to the physical queue corresponding to the business flow. The upper triangle mark curve is the situation when the dynamic share sub-table adopts the linked list organization method, and the square mark curve is the dynamic share sub-table adopts the binary search tree organization method. The situation at that time; (a) Figure shows the situation of OC-48, (b) Figure is the situation of OC-192.

In Fig. 6, when the sub-tables of the dynamic sharing list are organized by binary search tree, the dynamic sharing management module returns the cumulative distribution function of the average time of the physical queue corresponding to the service flow.

Figure 7, where,

RAM is a physical storage device that stores data packets;

The RAM management module manages the data structure of data packets stored in RAM, including memory division, allocation and recovery of free blocks, providing free block write addresses to the writing module, and providing queue head elements of the dispatched queue to the scheduling module the address of.

The dynamic shared list is used to store and maintain the active flow mapping relationship f _n → PQq.

Dynamic sharing module 1) According to the flow number f _n provided by the writing module, and according to the information existing in the dynamic sharing list, judge whether there is currently a physical queue corresponding to flow f _n , and return its corresponding physical queue number PQ _q if it exists; otherwise, return a The idle queue number is given to the writing module, and a new mapping relationship is added to it in the dynamic shared list. 2) After receiving the message that a certain physical queue becomes empty returned by the scheduling module, delete the mapping entry corresponding to the physical queue from the dynamic shared list.

The write module is responsible for the writing of arriving packets. First, request to the dynamic sharing module the corresponding physical queue of the flow where the currently arriving packet is located, and then obtain the tail write address of the physical queue from the RAM management module according to the result returned by the dynamic sharing module, and write the data packet into the address corresponding to the RAM middle.

The scheduling module is responsible for the scheduling of data packets. First obtain the physical queue that should be scheduled according to the scheduling algorithm, then obtain the read address of the head of the physical queue from the RAM management module, and read it out from the RAM. When the physical queue becomes empty after scheduling, the scheduling module notifies the dynamic sharing module to delete the mapping entry corresponding to the physical queue from the dynamic sharing list.

Processing flow of the present invention can be summarized as follows:

The present invention solves how to make millions of service flows in the link (especially in the backbone network) share the limited physical queue resources in the network forwarding equipment, and realize queuing according to each flow. The challenges mainly lie in:

1) From the perspective of the processing time scale of the high-speed network forwarding equipment, the service flow cached in the high-speed network forwarding equipment changes randomly, so it is necessary to respond to the change of the current active flow in time. The invention provides an effective mechanism to maintain and update the mapping relationship between active flows and physical queues.

2) In a high-speed network, the arrival interval between data packets is very small, so a fast search mechanism is needed to locate the physical queue where the arriving packets should be stored. The invention provides a fast algorithm to find the mapping relationship between the active flow and the physical queue.

3) Memory bandwidth and capacity are one of the potential bottlenecks of high-speed network forwarding equipment, and RAM management has a huge impact on memory bandwidth and capacity. The invention adopts efficient data structure and control mode to maintain the management of RAM.

The present invention is characterized in that the device contains: a physical storage device RAM, and a writing module integrated on the FPGA/ASIC, a scheduling module, a RAM management module, a dynamic sharing list, and a dynamic sharing module; wherein,

The physical storage device RAM is used to cache data packets and the next pointer of each data block, using any one of SRAM, DRAM or other physical storage devices;

The writing module is provided with the input terminal of the arriving packet of the active flow, the input terminal of the corresponding physical queue of the flow where the current arriving packet is located, and is connected with the corresponding output terminal of the dynamic sharing module, and is used to write the physical queue into the physical storage device RAM The tail write address input end of the free block of the free block is connected to the corresponding output end of the RAM management module; it is also provided that the request signal output end of the corresponding physical queue is connected to the corresponding input end of the dynamic shared module; the corresponding physical The tail of the queue writes the address request signal output terminal, which is connected with the corresponding input terminal of the RAM management module; the data packet output terminal is connected with the corresponding input terminal of the physical storage device RAM; The corresponding physical queue of the flow where the packet is located, and then according to the result returned by the dynamic sharing module, the write address of the tail of the physical queue is obtained from the RAM management module, and the data packet is written into the address corresponding to the RAM;

The scheduling module is used for the scheduling of data packets, and is provided with: the input terminal of the physical queue that should be scheduled at present is connected with the corresponding output terminal of the dynamic sharing module; the read address input terminal of the head of the physical queue and the corresponding output of the RAM management module The corresponding physical queue read-in end of the read-out address of the head of the physical queue is connected with the corresponding read-out end of the physical storage device RAM; it is also provided with: an active flow output end, respectively to the dynamic shared module, RAM management The request signal output terminal that module, physical storage device RAM sends, comprises sending to dynamic sharing module, request deletes the corresponding mapping appearance request signal of the physical queue that has become empty through scheduling from dynamic sharing list; This scheduling module according to setting Schedule in the active stream according to the specified scheduling method, obtain the physical queue that should be scheduled, and then obtain the read address of the head of the physical queue from the RAM management module, and read the corresponding address from the RAM of the physical storage device Data packet; the active state refers to the data packet stored in the corresponding physical queue of a flow;

The RAM management module, while being connected to the physical storage device RAM, the writing module, and the scheduling module, manages the data structure of the data group stored in the RAM according to the set method, including the division of the memory and the allocation of free blocks Recycling, providing the free block writing address to the writing module, and providing the dispatching module with the address of the head element of the dispatched queue;

The dynamic shared list maintains a one-to-one mapping relationship between the active flow A and the physical queue PQ, and the number of elements in A and PQ is the same;

The dynamic sharing module is interconnected with the dynamic sharing list; this module provides a fast search mechanism, which is responsible for finding the physical queue corresponding to the active flow from the dynamic sharing list; it also provides a fast insertion mechanism, and is responsible for when a new packet of an active flow arrives. Insert a new active flow to the physical queue and map it to the dynamic shared list; in addition, it also provides a fast deletion mechanism. When the physical queue allocated by a flow becomes empty, it is responsible for deleting an active flow to the physical queue in the dynamic shared list. mapping.

The scheduling module schedules in more than one active physical queue in a round-robin manner.

The RAM management module divides the RAM storage space into fixed-size storage blocks, whose size is equal to the size of a data transmission unit.

The RAM management module adopts a stack structure to realize the allocation and recovery of free storage blocks; the free block stack moves upward after the data packets leave and return the free blocks, and when the data packets arrive, the free blocks are allocated, The free block top pointer moves down.

The allocation and recovery of the free block, when the data packet arrives, the RAM management module takes out the free block address from the top of the stack to allocate the free block, and stores the data packet in; when the data packet leaves, the occupied storage block becomes a free block , the RAM management module writes its address into the stack structure again, and reclaims the free block.

Described RAM management module adopts linked list mode to realize the management of physical queue, for each physical queue, maintain a head pointer, point to the head of physical queue; Maintain a tail pointer, point to the tail of physical queue; A next pointer is saved in the data block, pointing to the next data block.

The RAM management module updates the queue tail pointer when the writing module writes a new data block, and updates the queue head pointer when the scheduling module schedules a data block.

The dynamic shared list includes a direct addressable storage table and a series of dynamic shared sub-tables; each position of the direct addressable storage table includes a one-bit identification bit and a pointer to the sub-list; wherein, the identification bit is "1", when there is a subtable in a certain location, and the pointer to the subtable is valid; the flag is "0", when there is no subtable in a certain location, and the pointer to the subtable is a null pointer.

The location of the direct addressing storage table is determined by the value of the flow number of the arriving packet after a hash function; wherein, the hash function includes any uniform hash function such as MD-5 or SHA-1.

The dynamic shared sublist can be organized in the form of a linked list.

The dynamic shared subtable can be organized in the form of a binary search tree.

The dynamic shared subtable can be organized in a balanced binary search tree.

The search mechanism of the dynamic sharing module refers to firstly determining the dynamic sharing subtable to be searched according to the flow number of the arriving packet through a hash function, and then searching in the corresponding dynamic sharing subtable.

The mechanism for searching in the corresponding dynamic shared sub-table is based on the linked list organization method described in claim 0, and uses the sequential search method of the linear table.

The mechanism for searching in the corresponding dynamic shared sub-table, when using a binary search tree or a binary balanced search tree, first compare the value of the stream number to be searched with the value of the stream number stored on the root node, which is greater than Then turn to the right subtree, if it is less than, turn to the left subtree, then compare the value of the stream number stored on the root node of the subtree, and so on, until you find the stream number you are looking for.

The insertion mechanism of the dynamic sharing module firstly determines the dynamic sharing subtable to be inserted according to the value of the packet flow number through the hash function, and then inserts the node to be inserted into the corresponding dynamic sharing subtable.

The described mechanism of inserting the node to be inserted into the corresponding dynamic shared sublist is inserted at the end of the linked list of the dynamic shared sublist in a linear table sequential insertion manner when the linked list organization mode is adopted.

The described mechanism of inserting the node to be inserted into the corresponding dynamic shared subtable, when using the binary search tree organization method, first compare the value of the stream number to be inserted into the entry with the value of the stream number stored on the root node size, if it is larger, turn to the right subtree, if it is smaller, turn to the left subtree, then compare the value of the flow number stored on the root node of the subtree, and so on, until the leaf node is found, if you want to insert the flow number in the entry If the value is greater than the value of the flow number stored on the leaf node, it will be inserted in the right child, otherwise it will be inserted in the left child.

The described mechanism of inserting the node to be inserted into the corresponding dynamic shared subtable, when using the balanced binary search tree organization method, first insert the subtable entry to be inserted according to the method under the binary search tree organization method, and then Adjust the binary search tree so that the depth difference between the left and right subtrees of each node does not exceed 1.

The deletion mechanism of the dynamic sharing module first determines the dynamic sharing sub-table where the node to be deleted is located according to the value of the hash function of the packet flow number, and then deletes in the corresponding dynamic sharing sub-table.

The public station sharing module deletes the corresponding dynamic shared sub-table. When the linked list organization mode is adopted, the node to be deleted is found by the linear list sequential search mode, and then deleted.

The mechanism for deleting the corresponding dynamic sharing subtable of the dynamic sharing module, when adopting the binary search tree organization method, first finds the node to be deleted by the binary search tree search method, and then deletes it; wherein, When the deleted node is a leaf node, just point its parent node to a NULL pointer; when the deleted node has only one left (or right) child node, use its parent node to directly point to the left (or right) of the node to be deleted. ) children; when the deleted node has both left and right children, the right subtree of the deleted node is used as the right subtree of the node with the largest value in its left subtree, and then the adjusted left subtree is used as its The subtree of the parent node.

The mechanism that the described dynamic sharing module deletes in the corresponding dynamic sharing subtable, when adopting the organizational mode of the binary search tree, first deletes the node to be deleted with the deletion mode of the binary search tree, and then adjusts the binary search tree so that The depth difference between the left and right subtrees of each node does not exceed 1.

The dynamic shared list can be replaced by content addressable memory CAM.

The device realizes the sharing of physical queues according to the following steps:

Step 1: When a data packet enters the writing module, the writing module uses the flow number of the data packet to request the corresponding physical queue from the dynamic sharing module;

Step 2: The dynamic sharing module looks up the entry corresponding to the corresponding flow number from the dynamic sharing list, and returns the physical queue write address to the writing module if it exists; otherwise, assigns a new physical queue to the flow and returns the physical queue number Write to the module, and write this new entry in the dynamic shared list;

Step 3: After the write module knows the write address of the corresponding physical queue, it obtains a free block from the RAM management module and writes it into RAM, and the RAM management module updates the tail pointer and the free block stack top pointer of the physical queue;

Step 4: the scheduling module schedules each physical queue according to the scheduling algorithm, asks the RAM management module for the queue head pointer of the currently scheduled queue, and reads it from the RAM; at the same time, the RAM management module reclaims the data block and adds it to the free block stack, and modifies the free block stack Top pointer, and modify the head pointer of the corresponding physical queue;

Step 5: When the currently scheduled queue becomes empty, the scheduling module notifies the dynamic sharing module to delete its entry in the dynamic sharing management list.

The scalable device proposed by the present invention, through a dynamic sharing mechanism, can still ensure that different service flows will not be cached in the same physical queue at any time, thereby realizing a high-speed broadband network. A wire-speed implementation of queuing per flow. The test results show that in 60% of the cases, the result can be returned in one clock cycle, and the queue sharing can be completed; in 90% of the cases, the result can be returned in 2 clock cycles, and the queue sharing can be completed.

Experimental verification

In order to verify the device solution of the present invention, the present invention has carried out related experiments, and the experiment selects two sections of actual network traffic data from NLANR (http://pma.nlanr.net/Special/): 1) OC-48: link The road capacity is 2.5Gbps. 2) OC-192: The link capacity is 10Gbps. Among them, the number of flows transmitted at the same time is shown in Figure 1. The number of flows counted by the OC-48 fluctuates around 300,000, and the number of flows counted by the OC-192 fluctuates around 360,000.

The simulation stores the packets in different queues according to their arrival time, and the scheduling allocates the bandwidth fairly among the occupied physical queues. The round-robin method is adopted, and each physical queue forwards a fixed-length byte ( 1500 bytes), then poll to the next physical queue. The performance parameters of the experimental statistics are as follows:

1) Average speed. The ratio of the amount of data passing through a node to the length of time in a certain period of time is represented by s;

2) The number of streams that coexist. Set the timeout of τ time for the stream, and count the number of streams being transmitted, represented by N _s (τ);

3) The number of active streams, the number of streams occupying the queue for queuing at a certain moment, that is, the number of occupied queues, represented by _Na .

The statistical process samples N _a and N _s (τ) every 25 ns, and accordingly obtains Max{N _a } and Max{N _s (τ)} within a certain period of time (eg, 1 second or 10 minutes). The load L of the system is defined as the ratio of the average rate of real business traffic to the egress bandwidth. Since the average rate of real business traffic cannot be changed, the simulated load L can only be adjusted by changing the egress bandwidth to count performance parameters under different load conditions. As shown in Figure 2, when the system load L is set to 0.97, the physical queue occupancy changes with time. It can be seen from the figure that the maximum flow count obtained by OC-48 is only 89, and that of OC-192 is only 406. Comparing the number of original co-existing flows in FIG. 2 with that in FIG. 1, the device of the present invention greatly reduces the number of physical queues that need to be set.

The dynamic sharing list is divided into multiple sub-tables by hash function as shown in the table below.

It can be seen from the table that after the hash function, the average length of each subtable is less than 3. Although the length of the sublist may still reach more than 10 in the worst case, the probability of sublist entries exceeding 1 or 2 is already very small. At the same time, increasing the number of sub-tables can also greatly reduce the length of the sub-tables.

Figure 3 and Figure 4 respectively show the operational complexity when using linked list and binary search tree to organize the sub-tables of the dynamic shared list. (a) in the two figures is the relationship between the search cycle and the number of sub-tables when the active flow already exists in the sub-table, and (b) is the relationship between the search cycle and the number of sub-tables when a new active flow arrives (need to insert new entries). It can be seen from the figure that as the number of sub-tables increases, the cost of searching decreases. When the number of sub-tables is greater than 64, the operation costs shown in (a) and (b) are all below 1.5 clocks.

Fig. 5 is the average time for the dynamic sharing management module to return the physical queue corresponding to the service flow to the writing module. (a) and (b) are respectively the average time overhead for the actual service flow of OC-48 and OC-192. It includes the time overhead of calculating the hash function for one cycle. It can be seen from the figure that as the number of sub-tables increases, the time overhead decreases. When the number of sub-tables is greater than 256, the operation costs shown in (a) and (b) are all below 2 clocks.

Fig. 6 is a cumulative probability function of time overhead when there are 256 sub-tables and a binary search tree is used to organize the sub-table structure. It can be seen from the figure that in 60% of the cases, the result can be returned in one clock cycle, and in 90% of the cases, the result can be returned in 2 clock cycles.

Description of drawings

Figure 1 shows the change curve of the number of coexisting streams with time, in which the solid line is the curve of OC-192, and the dotted line is the curve of OC-48.

Fig. 2 is a curve of the number of occupied physical queues over time, in which the lower triangle marked curve is the curve of OC-192, and the upper triangle marked curve is the curve of OC-48.

Figure 3 is the operational complexity when using the linked list structure to organize the sub-tables of the dynamic shared list, where the lower triangle marked curve is the curve of OC-192, and the upper triangle marked curve is the curve of OC-48; (a) shows that the search has been active In the case of a flow, Figure (b) is the case of inserting a new active flow into the physical queue map.

Fig. 4 Operational complexity when using a binary search tree to organize the sub-tables of a dynamic shared list, where the lower triangle marked curve is the curve of OC-192, and the upper triangle marked curve is the curve of OC-48; (a) shows that the search already exists In the case of an active flow, Figure (b) is the case of inserting a new active flow into the physical queue map.

Figure 5. The average time for the dynamic sharing management module to return to the physical queue corresponding to the business flow. The upper triangle mark curve is the situation when the dynamic share sub-table adopts the linked list organization method, and the square mark curve is the dynamic share sub-table adopts the binary search tree organization method. The situation at that time; (a) Figure shows the situation of OC-48, (b) Figure is the situation of OC-192.

In Fig. 6, when the sub-tables of the dynamic sharing list are organized by binary search tree, the dynamic sharing management module returns the cumulative distribution function of the average time of the physical queue corresponding to the business flow.

Figure 7 system structure diagram.

Figure 8 Realization of queue structure in block storage mode.

Figure 9 utilizes a hash function to partition a dynamic share list.

FIG. 10 uses a linked list structure to organize the sub-tables of the dynamic sharing list divided by the hash function.

Fig. 11 is an example of organizing sub-tables of a dynamic share list using a binary search tree.

Fig. 12 is an example of inserting an entry into a sub-table of a dynamic shared list organized by a binary search tree.

Figure 13 is an example of deleting an entry in the sub-table of the dynamic shared list organized by binary search tree, wherein (a) is an example of deleting 74, (b) is an example of deleting 12, and (c) is an example of deleting 66.

Detailed ways

Example 1

The write module is responsible for the writing of arriving packets. First, request the corresponding physical queue that is currently arriving at the shunt from the dynamic sharing module, and then obtain the tail write address of the physical queue from the RAM management module according to the result returned by the dynamic sharing module, and write the data packet into the address corresponding to the RAM.

For the convenience of management, the RAM management module usually divides the data packet storage space into fixed-size storage blocks. However, variable-length data packets are transmitted on the network, so it is necessary to cut the packets into units of fixed size, called Data Units (DU for short), and these DUs are reassembled into original variable-length packets before leaving the forwarding device. Data grouping. The size of the storage block into which the memory RAM is divided is the same as that of the DU, so one DU occupies exactly one storage block.

In the data packet memory, the unoccupied storage block is called a free block, and the RAM management module uses a stack structure to organize the address of the free block. When the data packet arrives, the RAM management module takes out the free block address from the top of the stack to allocate the free block, and stores the data packet in; when the data packet leaves, the occupied storage block becomes a free block, and the RAM management module writes its address into Stack structure, recover free blocks.

The RAM management module manages the management of the physical queue by means of a linked list. A head pointer is maintained in the linked list, pointing to the head of the physical queue list; a tail pointer is maintained, pointing to the tail of the physical queue list. The data in the physical queue is stored in RAM, and the next pointer is maintained behind each data block, pointing to the next data block. The head and tail pointers of all physical queues are stored in the RAM management module. The number of physical queues is not fixed in advance, and the physical queues are dynamically created and revoked according to the number of current active flows. The present invention uses the SRAM in the FPGA/ASIC chip to preserve the head and tail pointers of the physical queue and the free block stack, while the data grouping and the next pointer are stored in the external RAM storage device, as shown in Figure 8.

When a data packet arrives or leaves, the pointer data needs to be updated, and the update involves two parts: 1) The update of the next pointer, in units of DU. When a DU arrives, it needs to complete the enqueue operation, obtain a free block from the free block stack, and write the data. At this time, point the next pointer of the storage block where the previous DU is located to the current DU storage location; when a When DU leaves, it needs to complete the dequeue operation, add the free block to the end of the free block queue, update the next pointer of the previous free block to point to the recovered free block; 2) update the head and tail pointers. Updates are performed in units of data packets. When a new data packet arrives and is stored, the tail of the queue changes, and the tail pointer is updated to a new position; when the data packet leaves, the head position of the queue changes, and the head pointer is updated to a new position . In the free block stack, after the data packet leaves and returns the free block, the top pointer of the stack moves upward, and when the data packet arrives, a free block is allocated, and the top pointer of the free block moves downward.

Queuing by flow requires that the packets between different flows must be stored in different queues at every moment. The introduction of the dynamic sharing management module and the dynamic sharing list is just to realize that different flows can share physical queue resources without conflicts. Its characteristic of dynamic sharing mechanism of the present invention is:

1) The active flow set A is a subset of the overall flow set F, namely $A\⋐f,$ And A changes all the time in F;

2) A one-to-one mapping relationship is maintained between A and the physical queue PQ. The number of elements in A and PQ is the same, but much smaller than the number of elements in F;

3) Dynamic sharing management provides a fast search mechanism, which is responsible for finding the physical queue corresponding to the active flow from the dynamic sharing list;

4) Dynamic sharing management provides a fast insertion mechanism, when a new packet of an active flow arrives, it is responsible for inserting a new mapping from the active flow to the physical queue;

5) Dynamic sharing management provides a fast deletion mechanism, which is responsible for deleting the mapping from an active flow to a physical queue when the physical queue allocated by a flow becomes empty.

Different service flows can be distinguished through five source group information (source IP address, destination IP address, source port number, destination port number, protocol) in the header of the TCP/IP packet. Since the five source groups all have 13 bytes (taking IP v4 as an example), the total flow set F can contain ²¹⁰⁴ elements at most. Although the number of active streams does not exceed 1K, since active streams change dynamically in the set F that can contain up to 2 ¹⁰⁴ elements, it is very difficult to manage dynamic sharing. We solve the problem of dynamic sharing in two steps. First, we use a hash function to divide the entire dynamic shared list into multiple sub-tables; then we use the structure of linked list or binary search tree to organize the sub-tables.

The situation of dividing the entire dynamic shared list into multiple sub-tables by using the hash function is shown in FIG. 9 . In the figure, the dynamic shared list is a directly addressable storage table, and each location on it corresponds to a sub-list. The active flow is hashed to the corresponding subtable after passing through a hash function h(·), such as h(f ₇ ) is hashed to the subtable s ₁ , h(f ₃ ) and h(f ₅ ) is hashed onto subtable _s2 . Wherein, the hash function may be any uniform hash function such as MD-5 and SHA-1.

Through the function of hash, different streams are evenly distributed to each sub-table, and it is found through experiments that the number of active streams on each sub-table is very small (the experimental results will be listed in detail in the later experimental verification section). Therefore, we can simply use the linked list structure to organize each sub-table, and its structure is shown in Figure 10. Each position on the dynamic shared list uses a bit to indicate whether there is an element in the sublist, 1 indicates that there is a sublist, and then a pointer points to the element of the sublist; 0 indicates that there is no sublist, and it is followed by a null Null pointer. Each element in the sub-table contains a flow number f and a physical queue number PQ in addition to the pointer to the next element. Lookup, insertion and deletion operations on each subtable can be handled as a linear table.

When the writing module sends a lookup request with the stream number f ₅ to the dynamic sharing module, it first goes through a hash operation and is hashed to the subtable s ₂ , and the entries on s ₂ are searched sequentially. Find f ₅ through two searches, and return its corresponding physical queue number q ₈ .

When the writing module sends a lookup request with the flow number _f6 to the dynamic sharing module, it first undergoes a hash operation and is hashed to the subtable _s3 . Since the identifier on _s3 is 0, a physical queue is allocated Then directly insert a table entry in _s3 .

When the scheduling module schedules all the elements in the queue q ₇ to be empty, delete the corresponding entry on the sub-table s ₂ , and the entry on the sub-table s ₂ becomes <f ₅ , q ₈ >. In order to make the output operation easier, a previous pointer can be added to each entry of the subtable to point to the previous entry.

The scheduling module schedules in active physical queues in a round-robin manner. For example, the currently active physical queues are q ₁ and q ₈ , and the scheduling module schedules the two queues in turn. When scheduling q ₁ at the current time, it will schedule q ₈ at the next time, and so on. If a new queue q ₅ is inserted, the scheduling module will schedule these three queues in turn; if q ₁ is scheduled to be empty later, the how scheduling module will schedule the two queues q ₅ and q _{8 in} turn.

Example 2

The writing module works in the same way as in Embodiment 1.

The working mode of the RAM management module is consistent with that of Embodiment 1.

The scheduling module works in the same way as in Embodiment 1.

The dynamic shared list is also first divided into different sub-tables according to the hash method shown in Figure 9, and each sub-table is organized according to a binary search tree to reduce the time overhead on the sub-tables. Each node on the binary search tree also contains the active stream number and the corresponding physical queue number. An example of a binary search tree is shown in Figure 11. For convenience, only the value of the corresponding stream number is given on each node . The characteristic of a binary search tree is that the value of the left subtree is less than the value of the root node, and the value of the right subtree is greater than the value of the root node.

If you want to find the entry corresponding to the active flow number 74 on the binary search tree, first check the root node, 74>56, turn to the right subtree, 74>66, turn to the right subtree, 74<86, turn to the left subtree ,turn up.

When the desired node is not found during the search process, a new node is inserted at the leaf node. Figure 12 shows an example where the insertion flow number is 30. 30<56, turn to the left subtree, 30>18, turn to the right subtree, 30<36 and the left subtree of 36 is empty, then insert 30 as the left leaf node of 36.

There are three cases of deletion on the binary search tree, as shown in Figure 13. When the deleted node is a leaf node, it is only necessary to point its parent node to a NULL pointer, as shown in Figure 13(a). When the deleted node has only one left (or right) child node, use its parent node to directly point to the left (or right) child of the node to be deleted, as shown in Figure 13(b). When the deleted node has both left and right children, the right subtree of the deleted node is used as the right subtree of the node with the largest value in its left subtree, and then the adjusted left subtree is used as the right subtree of its parent node The subtree is shown in Figure 13(c).

Example 3

The writing module works in the same way as in Embodiment 1.

The working mode of the RAM management module is consistent with that of Embodiment 1.

The scheduling module works in the same way as in Embodiment 1.

The dynamic shared list is also firstly divided into different sub-tables according to the hash method shown in Figure 9, but each sub-table is organized according to a balanced binary search tree. The difference between it and the binary search tree is that the depth difference between the left and right subtrees of each node does not exceed 1. The search process of the balanced binary search tree is consistent with the search process of the binary search tree in Embodiment 2. When a balanced binary search tree is inserted into an entry, it is first consistent with the search process of the binary search tree in Embodiment 2, and then the generated binary search tree is adjusted so that the depth difference between the left and right subtrees does not exceed 1. When deleting an entry in the balanced binary search tree, the deletion process of the binary search tree in Embodiment 2 is first consistent, and then the generated binary search tree is adjusted so that the depth difference between the left and right subtrees does not exceed 1.

Claims (27)

1. An apparatus for dynamic per-flow queued physical queue sharing, the apparatus comprising: the system comprises a physical storage device RAM, a writing module, a scheduling module, a RAM management module, a dynamic sharing list and a dynamic sharing module, wherein the writing module, the scheduling module, the RAM management module, the dynamic sharing list and the dynamic sharing module are integrated on the FPGA/ASIC; wherein,

a physical storage device RAM, which is a physical storage device, for caching data packets and a next pointer for each data block; a write module provided with an arrival packet input end of an active stream; the corresponding physical queue input end of the current arrival packet in the flow is connected with the corresponding output end of the dynamic sharing module; the queue tail write address input end is used for writing data packets into idle blocks in the RAM of the physical memory device and is connected with the corresponding output end of the RAM management module; the request signal output end of the corresponding physical queue is connected with the corresponding input end of the dynamic sharing module; the queue tail write address request signal output end of the corresponding physical queue is connected with the corresponding input end of the RAM management module; a data packet output terminal connected to a corresponding input terminal of the physical memory device RAM; the writing module firstly requests a corresponding physical queue of a current arrival packet to the dynamic sharing module, then obtains a queue tail writing address of the physical queue from the RAM management module according to a result returned by the dynamic sharing module, and writes the data packet into the address corresponding to the RAM;

the scheduling module is used for scheduling data packets and is provided with: the input end of the physical queue which needs to obtain the scheduling at present is connected with the corresponding output end of the dynamic sharing module; the physical queue head reads an address input end and is connected with a corresponding output end of the RAM management module; a physical queue read-in end corresponding to the read-out address of the head of the physical queue is connected with a corresponding read-out end of a physical memory device RAM; also provided with: an active stream output end, which is a request signal output end respectively sent to the dynamic sharing module, the RAM management module and the RAM of the physical memory device, wherein the request signal comprises a mapping table item request signal sent to the dynamic sharing module and requesting to delete the scheduled empty physical queue from the dynamic sharing list; the scheduling module schedules in the stream in an active state according to a set scheduling mode to obtain a physical queue which needs to obtain scheduling, then obtains a read address of the head of the physical queue from the RAM management module, and reads a corresponding data packet from a physical memory RAM; the active state means that a data packet is stored in a corresponding physical queue of one flow; the RAM management module is respectively connected with the RAM, the write-in module and the scheduling module, and manages a data structure stored in the RAM by data grouping according to a set mode, wherein the data structure comprises the division of a memory, the allocation and recovery of idle blocks, the write-in module provides idle block write-in addresses, and the scheduling module provides addresses of head-of-line elements of a scheduled queue;

the dynamic sharing list maintains a one-to-one mapping relation between an active flow A and a physical queue PQ, and the number of elements in the A and the PQ is the same;

the dynamic sharing module is interconnected with the dynamic sharing list; the module provides a quick searching mechanism and is responsible for finding out a physical queue corresponding to the active flow from the dynamic sharing list; a quick insertion mechanism is also provided, and when a packet of an active flow is newly arrived, the quick insertion mechanism is responsible for inserting a new active flow into the mapping dynamic sharing list of the physical queue; and a quick deleting mechanism is also provided, and when the physical queue allocated by one flow becomes empty, the quick deleting mechanism is responsible for deleting the mapping of one active flow to the physical queue in the dynamic sharing list.

2. The apparatus of claim 1, wherein the scheduling module schedules the one or more active physical queues in a round robin fashion.

3. The apparatus of claim 1, wherein the RAM management module divides the RAM memory space into fixed-size memory blocks, the memory blocks being equal to one data transfer unit in size.

4. The apparatus according to claim 1, wherein said RAM management module implements allocation and reclamation of idle blocks in a stack structure; the idle block stack moves the top of the stack pointer up after the data packet leaves and returns to the idle block, and moves the top of the idle block stack pointer down when the data packet arrives and the idle block is allocated.

5. The apparatus of claim 4, wherein the RAM management module retrieves the free block address from the top of the stack to allocate the free block and stores the data packet; when the data packet leaves, the occupied storage block becomes a free block, and the RAM management module writes the address of the free block into the stack structure and withdraws the free block.

6. The apparatus of claim 1, wherein the RAM management module implements management of the physical queues in a linked list manner, and maintains a head pointer for each physical queue, pointing to the head of the physical queue; maintaining a tail pointer pointing to the tail of the physical queue; each data block of the physical queue holds a next pointer to the next data block.

7. The apparatus of claim 6, wherein the RAM management module updates the tail pointer when the write module writes a new data block and updates the head pointer when the scheduling module schedules a data block.

8. The apparatus for per-flow queued physical queue dynamic sharing of claim 1, wherein the dynamic share list comprises a direct-addressed memory table and a series of dynamic share sub-tables; each location of the direct addressing storage table comprises a bit of identification bits and a pointer to a sub-table; wherein, when a certain position exists in the sub-table and the pointer pointing to the sub-table is effective, the identification bit is '1'; a bit is identified as "0" when there is no child table in a location and the pointer to the child table is a null pointer.

9. The apparatus for dynamic per-flow queued physical queue sharing according to claim 8, wherein the location of the direct-addressed memory table is determined by the value of the stream number of the arriving packet after a hash function; wherein the hash function is a uniform hash function.

10. The apparatus of claim 8, wherein the dynamically shared sub-tables are organized in a linked list.

11. The apparatus of claim 8, wherein the dynamically shared sub-tables are organized in a binary tree lookup.

12. The apparatus of claim 8, wherein the dynamically shared sub-tables are organized in a binary balanced look-up tree.

13. The apparatus according to claim 1, 8 or 9, wherein the lookup mechanism of the dynamic sharing module is to determine the dynamic sharing sub-table to be looked up through a hash function according to the stream number of the arriving packet, and then look up the dynamic sharing sub-table.

14. The apparatus of claim 10, wherein the mechanism for performing lookups in the corresponding dynamic shared sub-tables is configured to perform linear table sequential lookups for the linked list organization of claim 10.

15. The apparatus of claim 1, 11 or 12 wherein the means for performing lookups in the corresponding dynamic shared sub-tables, when a binary lookup tree or a binary balanced lookup tree is used, compares the value of the stream number to be looked up with the value of the stream number stored at the root node, if it is larger, it is diverted to the right sub-tree, if it is smaller, it is diverted to the left sub-tree, then it compares the values of the stream numbers stored at the root nodes of the sub-trees, and so on until the stream number to be looked up is found.

16. The apparatus according to claim 1, 8 or 9, wherein the insertion mechanism of the dynamic sharing module determines the dynamic sharing sub-table to be inserted according to the packet stream number through the value of the hash function, and then inserts the node to be inserted into the corresponding dynamic sharing sub-table.

17. The apparatus of claim 16, wherein the node to be inserted is inserted into the corresponding dynamic shared sub-table mechanism, and when the linked list organization is adopted, the linear table sequential insertion is adopted to be inserted at the tail of the linked list of the dynamic shared sub-table.

18. The apparatus of claim 16, wherein the nodes to be inserted are inserted into the corresponding dynamic shared sub-table mechanism, when the binary tree is organized, the sizes of the stream number value to be inserted into the entry and the stream number value stored at the root node are compared, if the size is larger than the size, the entry is shifted to the right sub-tree, if the size is smaller than the size, the entry is shifted to the left sub-tree, if the size is smaller than the size, the entry is shifted to the root node, and if the size is larger than the size, the entry is inserted into the right sub-tree, and if the size is smaller than the size, the entry is shifted to the left sub-tree.

19. The apparatus of claim 16, wherein the node to be inserted is inserted into the corresponding dynamic shared sub-table mechanism, and when a binary balanced tree-lookup organization is used, the entry of the sub-table to be inserted is inserted in the binary tree-lookup organization, and then the binary tree-lookup is adjusted so that the difference between the depths of the left and right subtrees of each node does not exceed 1.

20. The apparatus according to claim 1 or 8, wherein the deleting mechanism of the dynamic sharing module determines the dynamic sharing sub-table where the node to be deleted is located according to the value of the packet stream number through a hash function, and then deletes the node from the corresponding dynamic sharing sub-table.

21. The apparatus according to claim 1, 10 or 14, wherein the dynamic sharing module is configured to delete the corresponding dynamic sharing sub-table, and when a linked list organization is adopted, find the node to be deleted by a linear table sequential lookup, and then delete the node.

22. The device according to claim 1, 8 or 11, wherein the dynamic sharing module is configured to delete the corresponding dynamic sharing sub-table, and when the binary tree is organized, the node to be deleted is found in the binary tree and then deleted; when the deleted node is a leaf node, only the father node of the deleted node needs to point to a NULL pointer; when the deleted node only has a left or right child node, the parent node of the deleted node is used for directly pointing to the left or right child of the node to be deleted; when the deleted node has both left and right children, the right sub-tree of the deleted node is taken as the right sub-tree of the node with the largest median value in the left sub-tree, and then the adjusted left sub-tree is taken as the sub-tree of the parent node.

23. The apparatus according to claim 1, 8 or 12, wherein the dynamic sharing module performs the deleting mechanism in the corresponding dynamic sharing sub-table, when the organization mode of the binary balanced search tree is adopted, the nodes to be deleted are deleted in the deleting mode of the binary search tree, and then the binary search tree is adjusted so that the depth difference between the left and right subtrees of each node does not exceed 1.

24. The apparatus according to claim 1 or 8, wherein said dynamic shared list can be replaced by a Content Addressable Memory (CAM).

25. The apparatus for per-flow queued physical queue dynamic sharing according to one of claims 1 to 12, wherein the apparatus implements physical queue sharing by:

step 25.1: when a data packet enters the write-in module, the write-in module requests a corresponding physical queue from the dynamic sharing module by using the stream number of the data packet;

step 25.2: the dynamic sharing module searches the table entry corresponding to the corresponding stream number from the dynamic sharing list, and if the table entry exists, the dynamic sharing module returns the physical queue write address to the write-in module; otherwise, a new physical queue is allocated to the flow, a physical queue number is returned to the writing module, and the new table entry is written in the dynamic sharing list;

step 25.3: after learning the write address of the corresponding physical queue, the write-in module writes data into the RAM in a grouped manner after obtaining an idle block from the RAM management module, and the RAM management module updates a tail pointer and an idle block stack top pointer of the physical queue;

step 25.4: the scheduling module schedules each physical queue according to a scheduling algorithm, inquires a head pointer of the currently scheduled queue to the RAM management module, and reads data pointed by the head pointer from the RAM; meanwhile, the RAM management module recycles the data block and adds the data block into an idle block stack, modifies a top pointer of the idle block stack and modifies a head pointer of a corresponding physical queue;

step 25.5: when the current scheduled queue becomes empty, the scheduling module informs the dynamic sharing module to delete the item of the dynamic sharing module on the dynamic sharing management list.

26. The apparatus for per-flow queued physical queue dynamic sharing of claim 1, wherein the physical storage device RAM can be SRAM or DRAM.

27. The apparatus for per-flow queued physical queue dynamic sharing according to claim 9, wherein the uniform hash function may be MD-5 or SHA-1.

Images