CN106688196B

CN106688196B - Method and apparatus for determining a data transfer sequence between multiple entries and multiple exits

Info

Publication number: CN106688196B
Application number: CN201480082375.5A
Authority: CN
Inventors: 刘才勇; 王小港
Original assignee: Alcatel Lucent SAS
Current assignee: Alcatel Lucent SAS
Priority date: 2014-09-30
Filing date: 2014-09-30
Publication date: 2020-06-26
Anticipated expiration: 2034-09-30
Also published as: WO2016049896A1; CN106688196A

Abstract

The invention aims to provide a method and a device for determining a data transfer sequence between multiple inlets and multiple outlets. The present invention provides a method for determining a data transfer sequence between a multiple-entry and a multiple-exit. Here, the number of the inlets and the number of the outlets are both N, and the data transmitted from the plurality of inlets form an N × N data matrix; wherein the depth of each entry is M, which indicates the number of transfer cycles used to transfer the data matrix; wherein, in each transfer cycle, the method comprises the steps of: a. determining a delivery cost for each non-zero element in the matrix based on the cross attribute and the numerical attribute of each non-zero element, and determining that the delivery cost for a zero element is zero; b. selecting an element having the largest cost from among the elements having the determined costs; c. returning to step a to re-determine the transfer costs of the remaining elements in the matrix, regardless of the rows and columns of the selected elements, until there remains only one element for which the transfer costs are to be re-determined; d. a data transfer sequence is determined based on N data samples, where each data sample is obtained from one of the N selected elements.

Description

Method and apparatus for determining a data transfer sequence between multiple entries and multiple exits

Technical Field

The present invention relates to a technique for transferring cross-parallel data between multiple entries and multiple exits.

Background

Cross-parallel data transfer between multiple entries and multiple exits is a matrix problem. The classical solution algorithm is to perform a row swap or a column swap so that the diagonal elements of the matrix are non-zero. When all diagonal elements are non-zero, a transfer matrix is generated. And, the identity matrix performs the same flow to obtain a transfer matrix. But the computational process is complex and takes more time, since many iterations are sometimes required.

Disclosure of Invention

The invention aims to provide a method and a device for determining a data transfer sequence between multiple inlets and multiple outlets.

According to one aspect of the invention, a method for determining a data transfer sequence between a multiple entry and a multiple exit is provided. The number of the inlets and the number of the outlets are both N, and the data transmitted from the multiple inlets form an N-by-N data matrix;

wherein the depth of each entry is M, which indicates the number of transfer cycles used to transfer the data matrix;

wherein, in each transfer cycle, the method comprises the steps of:

a. determining a delivery cost for each non-zero element in the matrix based on the cross-attribute (cross-attribute) and the value-attribute (value-attribute) of each non-zero element, and determining that the delivery cost for a zero element is zero;

b. selecting an element having the largest cost from among the elements having the determined costs;

c. returning to step a to re-determine the transfer costs of the remaining elements in the matrix, regardless of the rows and columns of the selected elements, until there remains only one element for which the transfer costs are to be re-determined;

d. a data transfer sequence is determined based on N data samples, where each data sample is obtained from one of the N selected elements.

According to one aspect of the present invention, a switching device for determining a data transfer sequence between a multi-ingress and a multi-egress is provided. The number of the inlets and the number of the outlets are both N, and the data transmitted from the multiple inlets form an N-by-N data matrix;

wherein, in each delivery cycle, the switching device is configured to:

a. determining a delivery cost for each non-zero element in the matrix based on the cross attribute and the numerical attribute of each non-zero element, and determining that the delivery cost for a zero element is zero;

According to one aspect of the invention, a computer-readable medium is provided. The computer readable medium contains computer code executed by a switching device comprising a plurality of entries and a plurality of exits, wherein the number of entries and exits are each N, and wherein data communicated from the plurality of entries constitutes a N x N data matrix;

wherein, in each delivery cycle, the switching device is configured to:

According to an aspect of the invention, a computer program is provided. The computer program is executed by a switching device comprising a plurality of entries and a plurality of exits, wherein the number of entries and exits is N, and wherein data communicated from the plurality of entries comprises an N x N data matrix;

wherein, in each delivery cycle, the switching device is configured to:

The invention allows efficient cross-parallel data transfer between multiple entries and multiple exits. The invention ensures that only one data sample in each row and column of the data matrix can be transferred during one transfer cycle.

Drawings

Other features, objects and advantages of the present invention will become more apparent from the following detailed description of non-limiting embodiments thereof, which proceeds with reference to the accompanying drawings.

FIG. 1 illustrates an exemplary flow of determining a data transfer sequence based on transfer costs of matrix elements in one transfer cycle in accordance with the present invention;

fig. 2 shows an exemplary schematic diagram of a RRH architecture suitable for use with the present invention;

fig. 3a) -d) respectively show a plurality of data matrices and their corresponding delivery sequences according to an embodiment of the invention.

The same or similar reference numbers in the drawings identify the same or corresponding elements.

Detailed Description

Hereinafter, the present invention will be described in more detail with reference to the accompanying drawings.

The present invention provides a solution for determining a data transfer sequence for cross-parallel data transfer between multiple entries and multiple exits. Further, the present invention is applicable to any type of switching device having symmetrical multiple inlets and outlets. Furthermore, the determination of the cost-based data transfer sequence may be made by other devices than the switching device, for example a dedicated determination device, although the data transfer sequence is used in a switching device with symmetrical multiple entry and multiple exit.

Specifically, for multiple entries and multiple exits, the number of entries and exits is N, so the data passing from the multiple entries constitutes an N x N matrix (hereinafter "data matrix"). The depth of each entry is M, and depth means the number of passes of data from the entry until the entry is empty. That is, for an N x N data matrix, it will go through M transfer cycles to transfer from multiple entries to multiple exits. And the total elemental value for each row and each column of the data matrix is M.

Further, in each delivery cycle, a data delivery sequence is determined based on the delivery cost. The specific steps for the determination are as follows:

1) the non-zero elements in the data matrix and the cost of the transmission of the zero elements are determined in different ways. A zero element means an element whose value is zero, and the delivery cost of the zero element is zero. Non-zero elements mean elements with non-zero values, and the cost of delivery of a non-zero element is based on its cross attribute and value attribute.

The cross-attributes of the non-zero elements include a zero attribute and a non-zero attribute. The zero attribute of a non-zero element indicates the total number of zeros in the same row and the same column of the non-zero element; and the non-zero attribute of a non-zero element indicates whether or not a non-zero element is present in the same row and/or the same column of the non-zero element.

2) Among all the elements for which the cost has been determined, the element with the largest cost is selected. If two or more elements have the same maximum cost, only one element is selected from among the elements.

3) The rows and columns of the selected element are excluded and the remaining elements in the data matrix are considered as new inputs to re-determine their transfer cost in step a until only one element remains to be re-determined.

That is, after the first element is selected based on its transfer cost in the transfer cycle, the next selection for the next element will be determined based on the transfer cost re-determined for the remaining elements in the matrix excluding the rows and columns of the selected element; steps 1) -3) will be repeated (N-1) times, whereupon after (N-1) times the transfer cost of the corresponding element in the data matrix is determined (N-1) times (N-1) elements are selected and finally only one element remains, i.e. the last selected element in the transfer cycle.

4) According to the previous steps 1) -3), a data delivery sequence is determined based on the N selected elements. Since only one data sample can be transferred from each selected element in one transfer cycle, the determined data transfer sequence also constitutes an N x N transfer matrix (hereinafter "transfer matrix") with N "1" elements respectively corresponding to each of the N selected elements and "0" elements filling the remainder of the transfer matrix. Thus, in each N x N transfer matrix, no more than one data sample is transferred in each row and column, thus transferring a maximum of N data samples in one transfer cycle.

Taking 4 × 4 multi-links (multi-links) as an example, the data to be passed from multiple entries also constitutes a 4 × 4 data matrix, and the depth of each entry is 64. Thus, there are 64 transfer cycles, and each cycle has one transfer sequence. The data matrix to be transferred is exemplarily shown as follows:

in a transfer cycle, the N selected elements are the elements of the data matrix indicated by row-column, such as 1-1, 2-2, 3-3, and 4-4. And only one data sample can be passed in each selected element. Thus, the data transfer sequence in this transfer cycle is:

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

5) the data matrix is updated after each transfer cycle, wherein the value of each of the N selected elements is decreased by 1. The updated data matrix is then applied to the next cycle of the delivery sequence. This update will go through (M-1) times or until all elements in the data matrix are zero.

Referring to fig. 1, an exemplary flow for determining a data transfer sequence based on a transfer cost of a matrix element in one transfer cycle is shown. For the exemplary illustration of the present invention, the determination of the data transfer sequence is described as being performed by a switching device.

In step 101, the switching device may determine a cost of delivery for each zero and non-zero element in the data matrix. The delivery cost of the zero element is zero. The delivery cost of each non-zero element is determined based on the intersection attribute and the numerical attribute of each non-zero element.

For non-zero elements, their cross attribute includes their zero attribute and their non-zero attribute. The zero attribute of a non-zero element indicates the total number of zeros in the same row and the same column of the non-zero element; and the non-zero attribute of a non-zero element indicates whether or not a non-zero element is present in the same row and/or the same column of the non-zero element.

Table 1 below shows a data matrix to be passed from multiple entries to multiple exits. The number of inlets and outlets is 4.

	Outlet 1	An outlet 2	An outlet 3	An outlet 4
						Inlet 1	0	0	1	0	1
Inlet 2	0	0	2—B	0	2
						An inlet 3	1	3—A	0	1	4
Inlet 4	0	1	0	1	0
							1	4	3	0

TABLE 1

Table 1 also shows the correspondence between multiple inlets and multiple outlets. For example, element a is at row entry 3 and list entry 2, which means that element a will be passed from entry 3 to exit 2.

Taking element a as an example, the transfer cost is calculated.

① zero attribute of element A

There are 1 zero in the same row and 2 zeros in the same column, so the total number of zeros is 3, and the zero attribute of element a is 3.

The zero attribute is updated each time an element is selected based on the maximum cost, so the row and column of the element are excluded.

② non-zero attribute of element A

There are 2 non-zeros in the same row, which makes the value of the

non-zero attribute

1, and 1 non-zero in the same column, which makes the value of the non-zero attribute 1, so the non-zero attribute of element a is eventually 2. That is, the non-zero attribute of an element may be 0, 1, or 2.

The non-zero attribute is updated after a data transfer sequence is determined.

③ numerical attribute of element A

The value of element a is 3, so the value attribute of element a is 3.

④ cost of delivery of element A

The transfer cost is a weighted sum of the cross attribute and the numeric attribute of an element. Specifically, the zero attribute and the non-zero attribute included in the cross attribute may be set with different weights.

For example, the transfer cost is 1 × zero attribute +0.1 × non-zero attribute +0.001 × numeric attribute.

Therefore, the transfer cost of element a is 1 × 3+0.1 × 2+0.001 × 3 — 3.203.

Further, for element B, its zero attribute is 5(3+2), its non-zero attribute is 1(0+1), and its numerical attribute is 2. Therefore, the transfer cost of element B is 1 × 5+0.1 × 1+0.001 × 2, 5.102.

In step 102, the switching device may select the element having the largest cost from among the elements having the determined costs. Assuming that the delivery cost of element B is the largest cost among all elements in table 1, then element B is selected.

The switching device may select one randomly, or the first element, when there is more than one element with the greatest cost. The selection rules may be set according to the specific application.

In step 103 the switching device may exclude the rows and columns of the selected element and return to step 101 to re-determine the transfer cost of the remaining elements in the data matrix until only one element remains to re-determine the transfer cost.

For example, for the next transfer cost determination in the transfer cycle, the row and column of element B are removed. It should be noted that the removal action is merely one example of "override" that is used to help calculate the delivery cost of the remaining elements, and thus does not imply that all elements in the same row and column of the selected element are actually deleted. Still referring to table 1, the cross-connection of element B is shown as (1) below.

The remaining data matrix (2) is then used as input to re-determine the delivery cost for each element. In matrix (2), element "3" is element a. The zero attribute of element a becomes 1 and its non-zero attribute is still 2. Therefore, the transfer cost of element a is 1 × 1+0.1 × 2+0.001 × 3 is 1.203. Element a is selected assuming that its delivery cost is the largest cost among all 9 elements in matrix (2).

Another element will be selected in the next cost determination. Only one element will then remain. Thus, all 4 elements in the delivery cycle are determined.

Further, the cost determination process may be terminated early when all remaining elements are zero. However, the determination of the delivery sequence will not terminate until the entire delivery sequence has been determined for all delivery cycles. This allows the number of transfer cycles to coincide with the number of other data packets.

In step 104, the switching device may derive a data transfer sequence of a 4 x 4 transfer matrix based on the 4 selected elements. In particular, only one data sample can be transferred per row and per column of the transfer matrix at a time, so that 4 data samples in different rows and columns can be transferred in one transfer cycle.

For example, elements 1-1, 2-3, 3-2 and 4-4 were selected in step 101-103, and one data sample of each of these four elements would then be removed, so the data transfer sequence in the transfer cycle is:

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

in step 105, the switching device may update the data matrix. The value of each of the N elements selected in the transfer period is decreased by 1 until the value becomes 0. The updated data matrix is then applied to the next delivery cycle for cost calculation and delivery sequence determination.

According to one embodiment of the invention, a RRH device is suitable. Referring to fig. 2, a RRH architecture is shown. The RRH device includes a crossbar module that acts as a packet switch. As shown in fig. 2, the cross module is located between the CPRI interface and the antenna processing chain (hereinafter referred to as antenna-x/x for short).

The LTE-BBU packs X Y Z data samples into one packet. X is the number of antennas, Y is the number of carriers per antenna, and K is the number of data samples per carrier.

For example, for illustrative purposes, the LTE-BBU packs 8 × 4 × 8 data samples into one packet in this specification. The total number of data samples is 256.

Packets are delivered from the LTE-BBU to the RRH over CPRI lanes (lane).

One CPRI lane provides only 64 data sample capability, so there are 4 CPRI lanes.

The LTE-BBU packs 64 data samples according to the user configuration. An exemplary example of a "packet format" is shown in table 2 below, where the LTE-BBU packetizes data samples based on the same carrier. The packet format is random for the RRH.

CPRI tunnel 1	CPRI tunnel 2	CPRI tunnel 3	CPRI tunnel 4
				Antenna 1-carrier 1	Antenna 1-carrier 2	Antenna 1-carrier 3	Antenna 1-carrier 4
Antenna 2-carrier 1	Antenna 2-carrier 2	Antenna 2-carrier 3	Antenna 2-carrier 4
				Antenna 3-carrier 1	Antenna 3-carrier 2	Antenna 3-carrier 3	Antenna 3-carrier 4
Antenna 4-carrier 1	Antenna 4-carrier2	Antenna 4-carrier 3	Antenna 4-carrier 4
				Antenna 5-carrier 1	Antenna 5-carrier 2	Antenna 5-carrier 3	Antenna 5-carrier 4
Antenna 6-carrier 1	Antenna 6-carrier 2	Antenna 6-carrier 3	Antenna 6-carrier 4
				Antenna 7-carrier 1	Antenna 7-carrier 2	Antenna 7-carrier 3	Antenna 7-carrier 4
Antenna 8-carrier 1	Antenna 8-carrier 2	Antenna 8-carrier 3	Antenna 8-carrier 4

TABLE 2

As shown in fig. 2, the crossover module provides switching functions to assign data samples from the CPRI into corresponding antenna processing chains. The packet format information has been delivered to the RRH over other channels.

Any CPRI container may be routed to any antenna container:

cpri-X delivers packets continuously. Data samples in the same group are combined into one container.

it takes only 64 cycles to deliver a packet from CPRI-X to antenna-X/X side.

cpri-X only ejects one data sample in one cycle. 4 data samples must be transferred synchronously.

Antenna-x/x accepts only one data sample in one period.

CPRI-X is an illustrative example of an ingress and an antenna is an illustrative example of an egress, so that data samples passed from CPRI to antenna constitute a multiple-ingress multiple-egress scenario.

Referring to fig. 2, each CPRI-X and antenna-X/X is loaded with only 64 data samples. Here, two antennas are combined into one group for equalization between CPRI lanes and antenna processing chains. Therefore, the number of CPRI lanes is 4, and the number of antenna groups is also 4.

256 data samples are input into 4 CPRIs, and each CPRI has 64 data samples arranged randomly, as indicated in table 2. The arrangement of data samples is exemplarily shown in table 3 below.

		Aerial-1/2	Aerial-3/4	Aerial-5/6	Aerial-7/8
						CPRI-1	64	16	16	16	16
CPRI-2	64	16	16	16	16
						CPRI-3	64	16	16	16	16
CPRI-4	64	16	16	16	16
							Total number of	64	64	64	64

TABLE 3

According to table 3, the data matrix to be transferred is determined as:

each CPRI-X has a depth of 256/4 64, and thus the data matrix needs to be transferred in 64 cycles. In each cycle, only 4 data samples from different CPRI-X can be removed and a delivery sequence determined. Thus, 64 transfer sequences are generated for one transfer packet, and each transfer sequence forms one transfer matrix.

For example, for the first pass cycle, when count down is employed, it is cycle 64. And in this 64 th cycle, elements 1-1, 2-3, 3-2, and 4-4 are selected according to the transfer cost, and the 4 data samples to be transferred form a corresponding transfer sequence as:

1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

then in the second transfer cycle (i.e., cycle 63), the data matrix to be transferred is reduced to:

fig. 3 shows the first 8 data matrices and their corresponding transfer sequences and the last 8 data matrices and their corresponding transfer sequences. Here, fig. 3a) shows the first 4 data matrices and their corresponding transfer sequences; fig. 3b) shows the next 4 data matrices and their corresponding delivery sequences; fig. 3c) -3d) show the last 8 data matrices and their corresponding delivery sequences.

Although fig. 3 shows only a portion of the data matrix of a transfer packet and its corresponding transfer sequence, those skilled in the art will also recognize that the data matrix of the remaining portion of the transfer packet and its corresponding transfer sequence may be readily determined based on the calculation of the transfer cost described in the present invention.

From the delivery sequence, each CPRI-X knows which data samples are to be delivered, the crossover module knows where to deliver the received data samples, and each antenna-X/X knows where to store the received data samples.

It should be noted that the present invention can be implemented by software or a combination of software and hardware; for example, the present invention may be implemented by an ASIC (application specific integrated circuit), a general purpose computer, or any other similar hardware device.

The software routines of the present invention may be executed by a processor to perform the preceding steps or functions. Likewise, the software programs (including associated data structures) of the present invention can be stored in a computer readable recording medium, such as RAM memory, magnetic or optical drive or diskette and other similar devices. Further, some of the steps or functions of the present invention may be implemented by hardware, such as a circuit that performs various functions or steps in cooperation with a processor.

Furthermore, parts of the present invention may be applied as a computer program product, such as computer program instructions, which, when executed by a computer, may invoke or provide the method and/or technical solution according to the present invention by the operation of the computer. Further, program instructions invoking the inventive methods may be stored in fixed or removable recording media and/or transmitted via broadcast or data streams in other signal bearing media and/or stored in a working memory of a computer device operating based on the program instructions. An embodiment according to the invention herein comprises an apparatus comprising a memory for storing computer program instructions and a processor for executing the program instructions, wherein the apparatus is triggered to execute the method and/or technical solution according to the various embodiments of the invention when the computer program instructions are executed by the computer.

It will be appreciated by those skilled in the art that the invention is not limited to details of the foregoing exemplary embodiments, and that the invention may be practiced in other embodiments without departing from the spirit or essential characteristics thereof. The described embodiments are, therefore, to be considered in all respects as illustrative and not restrictive; the scope of the invention is indicated by the appended claims rather than by the foregoing description, and all changes which come within the meaning and range of equivalency of the claims are intended to be embraced therein. Reference signs in the claims shall not be construed as limiting the claim concerned. It will furthermore be appreciated that the term "comprising" does not exclude other elements or steps and that the singular does not exclude the plural. A plurality of units or modules recited in the system claims may also be implemented by a single unit or module, either in software or hardware. Terms such as "first" and "second" are used to indicate names, but not to indicate any particular order.

Claims

1. A method for determining a data transfer sequence between multiple entries and multiple exits, wherein the number of entries and exits is N, and wherein data to be transferred from the multiple entries constitutes an N x N data matrix;

wherein, in each transfer cycle, the method comprises the steps of:

c. returning to step a to re-determine the transfer costs of the remaining elements in the matrix, regardless of the rows and columns of the selected elements, until only one element remains for which the transfer costs are to be re-determined, thereby obtaining N selected elements;

d. obtaining a data sample having a value of "1" from each of the N selected elements to obtain a data transfer sequence comprising N data samples;

wherein after each transfer cycle the data matrix is updated by decreasing the value of the N selected elements by 1, respectively.

2. The method of claim 1, wherein the delivery cost of a non-zero element is determined by a weighted sum of its cross attribute and its numeric attribute.

3. The method of claim 1, wherein the cross-attributes of non-zero elements in the matrix include a zero attribute and a non-zero attribute,

wherein the zero attribute indicates a total number of zeros in the same row and the same column of the non-zero element,

wherein the non-zero attribute indicates whether a non-zero element is present in the same row and/or the same column of the non-zero element.

4. The method of claim 3, wherein the zero attribute is updated after the rows and columns of the selected element are disregarded in step c, and the non-zero attribute is updated in each pass cycle.

5. The method of claim 1, wherein the delivery cost of a zero element is zero.

6. The method of claim 1, wherein step b further comprises:

if the number of elements having the largest cost is more than one, one element is selected from among the elements having the largest cost.

7. The method of claim 1, wherein each data transfer sequence constitutes an N x N transfer matrix with N "1" elements and other "0" elements respectively corresponding to the N selected elements from the data matrix.

8. A switching apparatus for determining a data transfer sequence between a plurality of entries and a plurality of exits, wherein the number of entries and exits is N, and wherein data to be transferred from the plurality of entries forms an N x N data matrix;

wherein, in each delivery cycle, the switching device is configured to:

9. A computer readable medium containing computer program instructions executed by a switching device comprising a plurality of entries and a plurality of exits, wherein the number of entries and exits is N, and wherein data communicated from the entries constitutes a N x N data matrix;

wherein, by executing the computer program instructions, in each delivery cycle, the switching device is configured to: