Method and system for network data transmitting

A method and system for network data transmitting in a communication system includes transmitting a data from at least one transmission node to at least one receiving node of a transmission-receiving group among the plurality of communication nodes by utilizing a node ID, the node ID of communication node in the group is being assigned by a N-carry operation of a determined number N.

TECHNICAL FIELD

The present disclosure relates generally to network systems and, more particularly, relates to method and system for network data transmitting.

BACKGROUND

In communication systems a network node (or so called host) can allocate its ID or address statically or dynamically. In a static configuration, users need to acquire an available address in advance and manually configure the address. In contrast, in a flexible multi-hop environment, such as the type described in IEEE 802.16j, it is not reasonable for operators or users to perform manual configuration. Another choice, dynamic configuration, allows a node to configure its ID or acquire an ID from a centralized server dynamically. In a typical dynamic configuration scheme, all node IDs are assigned randomly, and additional routing algorithms or routing tables are required in order for nodes to exchange or maintain additional routing information and to decide routing paths.

FIG. 1illustrates an exemplary multi-hop relay (MR) network100. In network100, a multi-hop relay base station BS (MR-BS)102acts as a root node, and relay stations (RSs) and mobile stations (MSs) act as intermediate nodes or leaf nodes. A network setup process assigns each network node an identification (or address) and constructs routing groups between nodes. For example, RS3104is assigned an address and is responsible for forwarding packets from MR-BS destined to RS4106, and RS1108will drop the packets it receives from MR-BS that are destined to RS3. Such routing information may be maintained in a routing table of each RS so that when an intermediate node leaves or enters the network, that newest routing information can be updated.

Two examples show utilization of routing tables. U.S. Pat. No. 6,192,051 discloses a multi-level tree data structure in a centralized routing table and in distributed forwarding tables for forwarding network packets. Each level of each structure is associated with a different field of a network address appearing in received packets. U.S. Pat. No. 6,934,252 discloses binary network address lookups using parent node information stored in routing table entries. Variable length prefixes are stored in a network address forwarding table. Each prefix corresponds to an entry in the forwarding table. Each entry in the forwarding table includes path information regarding parent nodes of each entry in the binary tree.

Node identification may be performed without maintaining a routing table. U.S. Pat. No. 6,618,755 discloses a software facility for automatically identifying subnets in a network by a range of addresses within the network represented by nodes in the network. The addresses each include an ordered series of a fixed number of bits.

A prime factorization method to represent nodes of a network and groups between nodes is described in US2006/0198320, as well as in IEEE C802.16j-06/171. In the forwarding process of this method, a receiving node needs to factorize the ID number of the packet received to determine where to forward the packet. Another method is described in IEEE C802.16j-07/048r6, which relates to a contiguous integer block routing method, in which a network node identifies the integer block of a received address to determine where to forward the packet or if it should drop the packet.

SUMMARY OF THE INVENTION

In one exemplary embodiment consistent with the present disclosure is a method for transmitting data in a network. The method comprises forming a logical tree topology by connecting a root node and one or more child nodes among a plurality of nodes in the network; generating a node ID for each of the child nodes by a N-carry operation of a determined number N, and transmitting data by utilizing the generated node ID of the child nodes.

In another exemplary embodiment consistent with the present disclosure is a communication system. The system comprises a plurality of communication nodes interconnected to form a network, and a root node and one or more child nodes are connected among the plurality of communication nodes to form a logical tree topology; each of the child nodes having assigned thereto a node ID generated by a N-carry operation of a determined number N; and wherein data is transmitted by utilizing the assigned node IDs of the child nodes.

Yet in another exemplary embodiment consistent with the present disclosure is a communication node in a transmission-receiving group of a network, the network including a plurality of network nodes and the transmission-receiving group including at least one transmission node and at least one receiving node. The communication node comprising: at least one memory to store data and instructions; and at least one processor configured to access the memory, and when executing the instructions, configured to: transmitting a communication data by utilizing a node ID, the node ID is being assigned by a N-carry operation of a determined number N.

DETAILED DESCRIPTION

In a communication system environment, data could be transmitted among a transmitting-receiving group of plurality of communication nodes through a transmitting-receiving path from a first level transmission node to its first level receiving node or subsequent levels of receiving nodes. As an exemplary example, a logical tree-based topology may be formed a network including a plurality of nodes by designating one of the network nodes as a root node, and one or more other nodes as child nodes among the plurality of nodes of the network.FIG. 2is a schematic example of a network200configured to have such a logical tree-based topology consistent with embodiments of the invention. The tree based topology configured with a maximum number of k child levels. More broadly, the communication system could be any network topology, for example, a tree-based network or a mesh network.

Each of the child nodes in a kthchild level of network200is assigned an identification akfor each parent node to identify this child node, where identification akcould be any number. During an implementation stage, identification akcould be an integer greater than or equal to 0, and less than or equal to N, N is a determined number. N may be pre-defined to any arbitrary number or to a maximum number of child nodes connected to each of the plurality of nodes of the tree topology. In some implementation, the determined number N could maintain by the system dynamically. Furthermore, identification akmay be assigned by a random sequence or sequentially. In one example, identification akof each child node may be assigned according to a sequence in which it becomes associated with its parent node.

As illustrated inFIG. 2a, child nodes of node S are connected to form the kthchild level of the tree topology and N child nodes are connected to Node S. In one exemplary embodiment consistent with the invention, the identification akof each of the child nodes of node S could be assigned a number selected within 1 to N. One of the implementation could be to assign N as identification akof node T, N−1 as identification akof node U, . . . , 2 as identification akof node Y and 1 as identification akof node Z.

In another exemplary embodiment consistent with the invention, the identification akeach of the child nodes of node S could instead be assigned a number selects within 0 to N−1, for example, identification akof node T is assigned as 0, identification akof node U is assigned as 1, . . . , identification akof node Y is assigned as N−2 and identification akof node Z is assigned as N−1. In this example, the identification a1of 1stchild level is assigned from 1 to N−1, and the determined number N is 2i, where i is an integer equal to or greater than 0.

The root node or at least one of some other nodes with control capability or a child node may store information to generate the node IDs, and manage data forwarding or network configuration. For example, such information may include: the determined number N, a maximum child node number of a parent node in a logical tree topology, an integer i in the implementation of N=2i, identification akof the child node, the child level k of the child node, a set of identification {a1, a2, . . . , ak-1} along a parent-child path from the first child level of the root node to the child node, and a maximum child level H of the logical tree. Other information or parameters could also be provided, and the kind of information to be stored optionally depends on the implementation.

Embodiments of the present invention may be practiced in any network communication system. For exemplary purposes, in the following paragraphs, multi-hop relay networks are described as exemplary communication systems to demonstrate data transmitting algorithms for generating a node ID in a communication network environment in which there is a determined number N of nodes, wherein the node IDs are utilized to transmit data.

The node ID of each child node may be generated by a 2's carry operation, as explained in the following paragraphs.FIG. 3illustrates an exemplary multi-hop relay network300that includes a multi-hop relay base station (MR-BS) and multiple relay stations (RSs). Mobile stations (MSs, not shown in figure) may be associated with either MR-BS or RS.

Network300is configured to have a logical tree topology including a MR-BS root node302having five child levels. The first child level contains child nodes RSA(a1=1, ID=1), RSB(a1=2, ID=2) and RSC(a1=3, ID=3). The second child level contains nodes: RSD(a2=0, ID=4) which is a child node of RSA, and RSE(a2=0, ID=12) and RSF(a2=1, ID=13) which are child nodes of node RSC. The third child level contains the following child nodes of RSD: RSG(a3=0, ID=16), RSH(a3=1, ID=17), RSI(a3=2, ID=18), and RSJ(a3=3, ID=19). The fourth child level contains three child nodes of ode RSI: RSK(a4=0, ID=72), RSL(a4=1, ID=73), and RSM(a4=2, ID=74). The fifth child level contains four child nodes of node RSK: RSN(a5=0, ID=288), RSO(a5=1, ID=289), RSP(a5=2, ID=290), and RSQ(a5=3, ID=291).

In the configuration of network300, i=2 so that the determined number N=2iof child nodes is 22=4, the maximum child level H is 5, and the identification akof each of the nodes of the first child level (k=1) is a sequentially assigned integer from 1 to 3. Relative to each parent node, the identification akof each of the nodes of other child levels is a sequentially assigned integer from 0 to 3 in this exemplary example.

FIG. 4illustrates network300in which node IDs are represented in binary notation. By converting the node ID of each of the child nodes of the logical tree topology of network300into binary notation, it becomes possible to perform a 4-carry operation to generate the node IDs of network300. Moreover, the computations of node ID assignments may be accomplished by bit operations.

With reference toFIG. 4and as an exemplary implementation consistent with embodiments of the invention, the node IDs of the first child level nodes are assigned by an integer selected within 1 to 2i−1 by setting different values of the lowest i bits of each node ID. For the nodes of other child levels, a control node, MR-BS for example, left shifts i bits of the parent node ID of each child and sets different values of the lowest i bits by selecting an integer within 0 to 2i−1. This process could be used to generate the node IDs for newly arriving nodes or for connecting the child nodes RS. For example, it is assumed that nodes RSIand RSJnewly arrive one after another to associate with node RSD(ID=00 00 01 00) as their parent node, after arrival of nodes RSGand RSHinFIG. 4. To assign an ID to RSI, control node MR-BS left shifts 2 bits of its own ID, as a parent node, resulting in 00 01 00 00, and sets the lowest 2 bits as 10 since node RSIis the third node that attaches to RSD, resulting in 00 01 00 10. Similarly, node MR-BS assigns 00 01 00 11 to node RSJafter assigning the ID to node RSI. Using a similar manner (not shown in the figure), the node IDs of the first child level nodes could also be assigned by an integer by setting different values of the highest i bits of each node ID. While for the nodes of other child levels, a control node, MR-BS for example, right shifts i bits of the parent node ID of each child and sets different values of the highest i bits by selecting an integer within 0 to 2i−1.

Referring again toFIG. 3, in another exemplary embodiment, each child node may assign an identification ak, and a node ID of each of the nodes of the first child level may assign its own identification a1. The node ID of each of nodes of other child levels is assigned by performing an operation of left shifting i bits of the parent node ID of each of the child nodes and setting the lowest i bits to the identification akof each of the child nodes. For example, inFIG. 3RSIand RSJare associated with a common parent node RSD(ID=4) (00 00 01 00). To assign an ID to RSI, the MR-BS perform a left shift of 2 bits of the ID of the parent node RSDand adds binary “10” (decimal 2, its identification a3) resulting in decimal 18. Similarly, node ID19of RSJis generated by left shifting 2 bits of the parent node ID and adding 3, it's a3identification.

The operation of assigning identifications of the child nodes could be an N-carry operation.FIG. 5illustrates an exemplary embodiment of an N-carry operation as a polynomial. With reference toFIG. 5, each child node of a kthchild level of a tree topology of network nodes in a communication system500has a node ID=(ak·Nk-1+ak-1·Nk-2+ . . . +a2·N1+a1·N0). The node ID of each child node of the first child level is generated by a polynomial (a1·N0), the node ID of each child node of the second child level is generated by a polynomial (a2·N1+a1·N0), the node ID of each child node of the third child level is generated by a polynomial (a3·N2+a2·N1+a1·N0), and the node ID of each child node of the fourth child level is generated by a polynomial (a4·N3+a3·N2+a2·N1+a1·N0). The previously described 2's carry operation illustrated byFIGS. 3 and 4could also be expressed by the same polynomial form with N=2i.

FIG. 6shows an exemplary embodiment of node ID assignment using an N-carry operation in a communication system having a logical tree topology600with N=5. The node ID of node X1in the first child level is assigned to be 2, generated by (2×50=2). The node ID of node X2of child level 1 is 22, generated by (2×50+4×51=22). Following the same polynomial computation rule, nodes X3and X4are assigned 47 and 672, respectively, generated by (2×50+4×51+1×52=47) and (2×50+4×51+1×52+5×53=672) respectively. The N-carry operation of child nodes of the kthchild level is performed by adding ak·Nk-1to the parent node ID.

By use of the illustrated node ID assignment embodiments, during a data routing process, data could be transmitted by utilizing the node IDs of child nodes. When forwarding data, a destination node ID of the data is checked against the node ID of each child node, and each child node accepts the data for further processing if the destination node ID is the node ID of each such child node; and decides to forward the data to subordinate child nodes or to discard the data depending on whether the destination node ID is not the node ID of the child node.

FIG. 7is a flowchart illustrating an exemplary example of data transmission in a communication system. Each time a node receives a data packet having a destination node ID (step705), the receiving node subtracts its own node ID from the destination node ID (step710). If the subtraction result equals 0 (step715, yes), the node accepts (receives) the data packet for further processing (step720). If the subtraction result is not 0 (step715, no), the subtraction result is subjected to a modulo Nkoperation (step725). If the result of the modulo operation equals 0 (step730, yes), the node forwards the data to its subordinate child nodes (step735). Otherwise (step730, no), the data is discarded (step740).

Referring again toFIG. 6, tree topology600is used to explain a data forwarding example for a data packet destined for node X4having ID672. When node X1receives the packet, ID672is subjected to subtraction by 2. Because the subtraction result is not equal 0, node X1determines that is not the destination of the packet and subjects the subtraction result to the modulo Nkoperation. After the calculation, the modulo result is 0 so that node X1forwards the packet to subordinate nodes. The same process is executed in nodes X2and X3. When node X4receives the forwarded data packet, it subtracts its ID from the node ID of the packet. The subtraction result is 0, so node X4receives the packet for further processing. When the other child nodes receive the forwarded data packet, after the modulo calculation, the modulo result is not 0 so these nodes discard the data packet.

With the routing-embedded ID assignment illustrated withFIG. 4, each RS may determine its level and perform forwarding of data packets efficiently. For upstream frames, each RS may readily determine its parent ID by right shifting i bits of its own ID. For example, the ID of RSMis 01 00 10 10, so that RSMknows the ID of its parent node RSIis 00 01 00 10 by right shifting 2 bits of its ID. For downstream frames received from its parent node, the child node needs to determine if it should accept, forward, or discard the frame, such as in accordance with the process shown inFIG. 7.

FIG. 8illustrates a flowchart for a data transmitting process consistent with the exemplary embodiment of the invention illustrated inFIG. 4, the node IDs of child nodes are assigned by left shifts i bits of the parent node ID of each child and setting different values of the lowest i bits of each node ID, wherein N=2i. A node receiving a data packet checks if the destination node ID of the packet is equal to its own ID (step810) and accepts the frame if these two IDs are the same (step810, yes). If the two IDs are not the same, the node performs an i-bit right shift of the destination node ID (step820) and checks the result against its own ID (step830). If the shifted destination node ID is the same as the node's own ID, the node forwards the frame to its subordinate child node (step830, yes). Otherwise, it continues to right shift and check (step820,830) j times (step840,850), where j=(H−k), where H is the maximum number of child levels and k is the child level of the data transmitting node. The node discards the frame if all checks fail (step840, yes). Similarly, when the node IDs of the child nodes are assigned by right shifts i bits of the parent node ID of each child and setting different values of the highest i bits of each node ID, during the data transmitting process, the step820performs left shift instead of right shift and the other steps remain the same procedure.

When nodes enter and leave a communication system, the network topology could be changed accordingly, and node IDs may need to be updated as a consequence of the possible change of allowable connected child nodes at any child level in the logical tree topology. For example in some implementation the network identifies the maximum number of child nodes, broadcasts or forwards the maximum number, and updates the node ID of each of the child nodes.

A root node or another designated node with network control capability may process the identifying and broadcasting/forwarding, and each of the child nodes may update its own ID based on the broadcasted or forwarded information to generate the node ID, for example by identifying a set {a1, a2, . . . , ak} or based on decoding its own old node ID, for example, by bit shifting the old node ID. The information could be stored in the child node or forwarded by at least one node with network control capability during a broadcasting or forwarding process.

As shown inFIG. 2b, a communication node220of the network system the invention disclosed may include one or more of the following components: at least one central processing unit (CPU)221configured to execute computer program instructions to perform various processes and methods, random access memory (RAM)222and read only memory (ROM)223configured to access and store information and computer program instructions, memory224or one or more databases225to store information and data, one or more antenna226, one or more I/O device227and one or more Interface228, etc. Each of these components is well-known in the art and will not be discussed further.

FIG. 9illustrates an exemplary network900which illustrates a node handover from a parent node to another node. The root node or another node has control capability to forward to the handover node its new information for generating a node ID, for example {a1′, a2′, . . . , ak′}. After receiving the information, the handover node may generate the new node ID. InFIG. 9, the node with ID90decides to handover from parent node19to another parent node37. The root node forwards new information, e.g., {1, 3, 3, 1}, to the handover node. As a result, the handover node may update its new node ID during or after the handover process.

FIG. 10ais an example of a mesh topology network1000mapped to logical trees consistent with embodiments of the invention.FIG. 10billustrates three logical trees formed in network1000with connecting nodes. The three logical trees are logical tree1(1010) having node1as a root node, logical tree2(1020) having node8as a root node, and logical tree3(1030) having root node9as a root node. In general, the gateway to an external network is taken as the root node in a logical tree network.

When forwarding a packet in the logical tree network, the packet may include a destination address including at least a logical tree prefix field1001and a destination node ID field1002as illustrated inFIG. 10a. A node that receives a packet with a destination address assigns a logical tree prefix to forward the data. For example, in order for node4to transmit a packet to node9using logical tree1(1010), node4assigns 1 to the logical tree prefix field, and allocates the ID of node9of logical tree1to the destination node ID field of the destination address.

For forwarding packets between logical trees, due to the different prefixes and node IDs in different logical trees, each node may transform a destination address by modifying the prefix and node ID.FIG. 11shows an exemplary schematic diagram1100illustrating transmission of data between logical trees. In order for node8to send a packet to node9, node8inserts the logical tree prefix field1and inserts the node ID of node9in logical tree1as the destination node ID field, and forwards the packet via logical tree1. When receiving the packet, node7decides to forward the packet via logical tree2, by utilizing a conventional algorithm to make that decision. Node7changes the logical prefix field to 2, and transforms the node ID of node9in logical tree1(represented by the notation91) into the node ID of node9in logical tree2(92). The packet is forwarded to node9using the node ID92and the data transmitting algorithm of logical tree2. In this manner, the system may assign a different logical tree prefix value and transform the destination node ID in original logical tree to the node ID in the assigned logical tree, to transmit data utilizing one or more logical trees.

FIG. 12illustrates an example of a data transmitting flow chart. When a network node receives a packet and extracts the destination address of the packet (step1210), it identifies the logical tree prefix (step1220) and identifies the destination node ID of the logical tree (step1230). After identifying the destination node ID, the receiving node decides whether to forward the packet to another logical tree or not (step1240). The receiving node may uses any conventional or any of previous described data transmitting methods base on assigning node ID (data transmitting algorithm) of the identified logical tree (step1250), if not forwarding the packet by another logical tree (step1240, No). If the node decides to forward the packet by another logical tree (step1240, Yes), the node indicates a new logical tree in the logical tree prefix field and transforms the destination node ID into the node ID of the new logical tree (step1270) after the new logical tree is assigned by some algorithm (step1260). The packet is forwarded via the new path by utilizing the data transmitting algorithm of the new logical tree (step1280).

It will be apparent to those skilled in the art that various modifications and variations may be made in the system and method for reducing signal interference in communication networks. It is intended that the standard and examples be considered as exemplary only, with a true scope of the disclosed embodiments being indicated by the following claims and their equivalents.