PACKET FORWARDING MECHANISM

Effective data distribution without special hardware such as CAM. A unique Route ID in the network is used to determine the destinations for a sent packet. On creating the routing information for the Route ID, each node in the network creates an entry in its own forwarding table within the node. A linear memory offset in the table, called LookUp ID, is used to access the entry. By exchanging the LookUp ID with neighboring nodes and updating the forwarding table entry, the packet distribution path can be determined for the given Route ID. When a packet is sent for the given Route ID, each node updates the predetermined field in the packet with neighbor LookUp ID and sends it to the neighbor node, so the neighbor node can access its own entry as a regular memory access with the LookUp ID to determine where to forward the packet.

FIELD OF THE INVENTION

The present invention generally relates to systems and methods for communication between networking systems, and, more particularly, relates to a mesh networked system formed with multiple networking nodes connected each other via one to one connection via multiple ports on each node.

BACKGROUND

In the current local networking system, MAC address is used as the destination of the packet, which represents a single node or a broadcast to all nodes in given local network. When a routing node (e.g. networking switch) exists between the sender and the target node addressed by the MAC, the appropriate entry in the routing table is looked up to forward the packet to a proper node.

At a higher layer, Internet Protocol (IP) is used. The routing table within the router node is are used to determine where to forward the packet. In general, it requires a mechanism to provide {Routing ID, Forwarding Port} pair information. In order to sustain many nodes and services at global scale, the Routing ID requires a large name space (e.g. Ethernet MAC is 48 bit, IP v6 is 128 bit), but usually actual active addresses in a given system are very sparse. So, to avoid the look up table becoming huge, a special data structure such as hash or tree is used to reduce the memory size. In such case, Routing ID to port look up takes a multi-step computational resource or special hardware that increases the system cost as well as the time to complete the look up.

To avoid traffic congestion, many network switches are used. These devices use CAM (content addressable memory) to store the switching information for the network port. Such special hardware is high cost and limited in table size. This makes it difficult to extend the connection to very large scale.

Therefore, what is needed is a robust technique for effective data distribution, without special hardware such as CAM.

SUMMARY

The present disclosure addresses the above-mentioned shortcomings with a protocol and data structure for efficient information transfer between computational nodes connected via multiple communication ports to form a mesh network where communication from any node to all destinations is specified by a single identifier for effective data distribution without special hardware such as CAM.

Computational nodes are connected to each other via multiple point to point communication ports to form a mesh network. It provides flexible generic communication path between nodes within the mesh network. A unique routing index (Route ID) is used to represent a communication path between nodes within the mesh network. When a new Route ID is created in the system, higher level routing mechanism provides the path for the routing. A simple case is a pair of {source, destination}. This can also be a path for multicast, which gives a set of destinations {destination1, destination2, . . . }. Here, it is assumed that there is a higher communication protocol which transfers this routing information on the network. On such side communication path, the Route ID and necessary forwarding information is passed to the source, destination nodes, as well as the nodes in between. The calculation of such path is assumed to be done in the upper routing protocol/mechanism, and is not a subject of this invention.

When a node receives such a routing information, it will be a set of {Route ID, Forwarding Ports} pair, where the ports can be multiple targets including the node itself. When all the nodes within the routing path received such information, the mesh system can handle the packet transfer for the given Route ID. Each node looks up the table with Route ID, and determines where to forward the packet.

With the present technique, each node uses a linear table to store the routing information entries. The new entry is indexed directly as the memory offset within the table. This index is called the LookUp ID. Within the new entry in the routing table, the Forwarding Port to the destination is recorded. Then, via the upper routing protocol, this LookUp ID is passed to the source side of the next neighbor on this routing path. The neighbor receives the LookUp ID of next forwarding neighbor, and records it into the entry associated to Route ID, as the next Lookup ID of the forwarding port. So, each node has an entry for the Route ID with {Forwarding Port, Next LookUp ID} pair according to the routing path.

When a packet is sent from the destination, the sender looks up the entry in the lookup table. At the very beginning of the transfer, it uses a mapping mechanism to determine the table entry from the Route ID. Then, it forwards the packet to the port specified in the table entry. At this point, the sender updates a field in the packet header with the Next LookUp ID corresponding to the forwarding port. Thus, the next neighbor node will receive the packet header with the LookUp ID of its own, and it can directly lookup the Forwarding Table with LookUp ID as the direct memory offset. Each node updates the LookUp ID field in the packet header with the value associated with the forwarding port when it forwards the packet to the next node. So, all nodes can use direct table lookup, without the need for a more complex and thus slower mapping mechanism between Routing ID and the table entry.

The forwarding port information can be more than one, to support multi-cast information. The table entry also can holds Child port and Parent port with corresponding LookUp IDs to support bidirectional path with a single entry.

Advantageously, effective data distribution is achieved without special hardware such as CAM.

DETAILED DESCRIPTION

This disclosure generally discloses computer-implemented methods, non-transitory computer-readable media, and devices for packet forwarding in a distributed computer system. One of ordinary skill in the art will recognize various alternatives within the spirit of this disclosure, even if not specifically discussed herein.

In one aspect, a mesh network is formed with communication nodes each having multiple communication ports. Ports are connected to ports on other nodes. A port on a node is connected to only one port on another node, in some embodiments, to distinguish the other node by its local port. A unique Route ID in the network is used to determine the destinations for a sent packet. On creating the routing information for the Route ID, each node in the network can create an entry in its own forwarding table within the node, in some embodiments. By exchanging the LookUp ID with neighboring nodes and updating the forwarding table entry, the packet distribution path can be determined for the given Route ID. When a packet is sent for the given Route ID, each node updates the predetermined field in the packet with neighbor LookUp ID and sends it to the neighbor node, so the neighbor node can access its own entry as a regular memory access with LookUp ID to determine where to forward the packet. With this mechanism, effective data distribution mechanism is achieved without special hardware such as CAM (content addressable memory).

In more detail, multiple communication nodes with multiple communication ports are connected with each other via ports to form a mesh network. The connection between any two nodes is point to point, and directly connected each other using any type of network technology such as Ethernet, PCIe, etc. This example assumes those nodes are computational servers in a data center, but the techniques can be applied to network switches used to connect such servers. In such case, the cluster of switches provides the mechanism as a network fabric to connect severs connected to the cluster. In any case, the essence of the invention is to provide an effective data transfer mechanism on a given unique network address, according to an embodiment. In this example, the address can be defined by the Route ID. This invention provides a unique data distribution path for a given logical Route ID in any addressing scheme, on top of which a conventional protocol may be overlaid.

In one embodiment, the present technique assumes the routing decision to determine where to send the data using a Route ID is done within a higher level of the networking protocol. This example does not show the higher-level protocol implementation, but existing network routing protocols such as STP, RIP, OSPF, etc. show the implementation is possible. One way of implementing such protocol is using a spanning tree. Each node first creates a spanning tree (a graph without cyclic paths) with the root as itself and uses it as the base of creating the communication substrate. The spanning tree provides a single acyclic path from a root to any nodes in the mesh. Each node runs a protocol to create the spanning tree so that each node has own spanning tree. Using this tree, a node can reach any nodes in the network mesh on a unique path.

When a node (Source Node) wants to create a communication path to a root node, first it creates a Route ID which is unique in the network mesh. Then, it allocates an entry in the forwarding table. This entry is picked from an unused table entry pool, and is accessed directly by a memory offset within the table which is called the LookUp ID. The node creates a map between the Route ID and the LookUp ID. Such map can be achieved by a hash table, but it can be done with linear search if access speed is not an issue. Then, using the path to the destination node provided by the higher routing layer, the source node sends a Route Request to the next node on the routing path to the destination node. Such request may carry information such as {Route ID, Route Path Information to the destination node}.

Each node on the path to the destination node processes the Route Request in the same way. First, it creates a new entry within its own forwarding table, accessed with a unique LookUP ID. The node creates the map between the Route ID and the LookUp ID, and write the port number to the next node on the path into the table entry. Then, it forwards the Request to the next node on the routing path. It also sends back a Route Reply message to the sending node, with information of {Route ID, LookUp ID of this node}.

On receiving the Route Reply message, the received node updates the corresponding entry in the forwarding table with the child's LookUp ID for the child port accordingly. Once the Route Request reaches the destination and all the Route Replies are returned to each connection over the routing path, a unique data distribution chain via the forwarding table entries for the Route ID is created over the mesh network nodes.

When a packet is sent from the source along the path using the Route ID, the source looks up the map to get the corresponding LookUp ID. Then it gets the entry via direct memory reference with the LookUP ID. The packet header is updated with the value of LookUP ID for the next neighbor, and forwarded to the proper node according to the entry. [0035] The node receiving such data packet can just use the LookUP ID in the packet header and directly access the table with the ID to get own entry, update the LookUP ID on the packet with next neighbor value in the entry, and forward the packet to the port the entry designates. This process is continued till the packet reaches to the destination. By the direct memory access with the LookUp ID on each node, it can achieve high performance processing without special hardware mechanism such as CAM.

Mesh Network and Routing Path Construction

FIG. 1shows a communication node1with six ports2. These ports2are named P1, P2, P3, P4, P5, P6. This example uses6ports but another embodiment is not limited to any specific number of ports. Those ports2on the node1are connected to other nodes to form a mesh network. A port2on a node1is only connected to a single port2on another node, to form a point to point connection.

FIG. 2shows a mesh network that connects multiple Nodes1via communication link3. Ports2are connected to other ports on other node via a link3. The picture shows a very uniform connection structure, but some embodiments are not limited to such form. The mesh structure may be very random, as long as the link3is connected point to point and every node in the mesh can be reachable via multiple hop routing.

FIG. 3shows the routing path from node A1ato node G1g.Fat lines3ashows the path from node A1ato node G1g, and dashed lines3bare unused links in the mesh. This routing path is provided by the higher routing protocol.

FIG. 4shows the steps to construct the routing path from node A1ato node G1g.Following the routing path shown inFIG. 3, a route request will be sent from node A1a,and forwarded to node B1b,node C1c,node D1d,node E1e,node F1f,then reached to node G1gvia the routing path3a.The node outside the mesh1pshows the port number assignment in each node. During the communication over this routing path, each node creates a proper forwarding entry, and exchanges the LookUP ID with neighbor nodes in the path to form the route path information accessed with LookUp ID directly.

Forwarding Table and Forwarding Entry

FIG. 5shows a forwarding table5in a node1. A unique identifier Route ID4represents a routing path to send data within the network mesh as shown inFIG. 2. For a new Route ID4, a new forwarding table entry6is allocated within the forwarding table5. This entry is accessed with linear offset LookUp ID7. Within a routing entry, it keeps forward port number8, and Next LookUp ID9. The forward port number8designates the port connected to the next node in the route path. If the port number is set to zero, the packet will be forwarde to upper layer of this node as the destination of the packet. The Next LookUp ID is the LookUp ID in the next node on the routing path.

The Map10is a mechanism to map the Route ID4to the LookUp ID7. Each node create the relation between the Route ID4and its LookUp ID7in the Map10. This Map10can be implemented with hash or other data structure. This Map10is only used during the forwarding table construction and the very beginning of the packet transfer to the mesh. So the Map10can be located in the upper protocol layer to reduce the size of the Forwarding Table5.

FIG. 6shows the process of constructing a forwarding entry6in the forwarding table5. To create a forwarding path for a specific Route ID4, a Route Request Message11is sent from the source node, which contains the information of {Route ID4, Route Path Information12}. The node that received such a message allocates a new entry6from the unused pool of the Routing Table5. This entry is accessed with local LookUp ID7as a memory offset in the table5. The Map10is updated to have the relation between Route ID4and LookUp ID7. A forwarding port number8is calculated by the routing protocol13from the route path information12, and written to the forward entry6. Then the Route Request Message11is forwarded to the next node on the routing path. On the neighbor node, the same process is executed, and the route request is forwarded to the next node. It also returns the Route Reply message14with the receiver's LookUp ID7nand the Route ID4to the sender node. The sender node updates the Next LookUp ID field9on the forward entry6with the LookUP ID7non the reply message14.

FIG. 15shows the flow chart of the table entry construction explained above.

FIG. 7shows the relation of the route entries in neighbor nodes. The node B1bis connected to node A on port p6and the node C1cis connected to node B on port p5. The node D1dis connected to node C1con port p6. Node A1bsent the Route Request with the Route ID4, and node B1b,node C1cprocessed the route request and route reply accordingly. Then the Routing Table A5ain the node A1ahas the entry6afor Route ID4with the forwarding port number field8with port p6and Next LookUp ID field9awith LookUp ID B7b.The entry6bon the node B1bstores port number field8with port p5, and LookUp ID C7con the field9c.By creating such table entries along the routing path, the packet forwarding chain is created for the given Route ID4.

Packet Forwarding

FIG. 8shows an example usage of the conventional Ethernet packet frame for an embodiment. The Ethernet packet frame15is formed with Preamble, SFD, Destination MAC Address16, Source MAC Address17, Ether Type18, Payload, and FCS. As commonly used, the Ethernet packet uses the Destination MAC Address16to determine where to route the packet. But in one embodiment, the port is only connected to a single node. Thus, the destination port is not actually needed in this application. Here, we use the Ether Type field18with unused type to distinguish from regular Ether packet activity. Then, we use the Destination MAC Address for Next LookUP ID field. This field is updated with the value on the table, when the packet is forwarded to the next node. So that the next node can directly use this field to access to the routing table entry.

FIG. 9shows an example of packet forwarding. The source node A1asends a packet using the Route ID4. Node A1auses the Map10to find the routing table entry6acorresponding to the Route ID4. The forwarding port P6and LookUp ID9bfor node B1bare found from the entry6aand the LookUp ID field19ain the packet15ais updated to B LookUp ID9band forwarded to the node B1b.

Node B1breceives the packet15aand accesses the routing table entry6busing the LookUp ID field19aon the packet15a. With the new entry6b,forwarding port P5and C LookUp ID9care used from the entry6b.The LookUp field19bon the packet15bis updated with the C LookUp value9cand forwarded to the node C. The node C1cprocess is exactly the same. This process is continued till the packet reached to the destination with the Forward Port Number is set to zero.

FIG. 16shows the flow chart of the packet forwarding explained above.

Bidirectional and Multicast Routing

FIG. 10shows another example of the forwarding table5in the node1to support bidirectional and multicast transfer. The Route ID4is used to represent a routing path in the mesh shown in theFIG. 2. For a new Route ID4, a new route entry6is allocated within the forwarding table5. This entry is accessed with linear offset LookUp ID7. The map10is used to correspond the Route ID and the LookUp ID as explained in the previous example. Within a routing entry, it keeps the Forward (FW) Vector20, Parent Port21, and an array of LookUp ID9corresponds to all ports2. The FW Vector20contains bit vector20a,with bit P1to P6correspond to the network ports2as shown inFIG. 1, and P0represents the node itself. When bits in P1to P6are set, the packet will be forwarded to the node connected to those ports, and if P0is set, the packet will be forwarded to upper layer of this node as the destination of the packet. The FW Vector21specifies which ports the packet should be forwarded in the case the packet direction is forward. The Parent Port21keeps the port that packet should be sent, when the packet direction is backward. The LookUp ID9forms an array to keep LookUp ID values for all the ports2on the node1. With this structure, a single Route ID can be used for bidirectional packet transfer. Also, the FW Vector20allows to construct the multicast transfer path (explained later).

FIG. 11shows the process of constructing a route entry6in the routing table5for the example inFIG. 10. To create a routing path for a specific Route ID4, a Route Request Message11is sent from the parent node, which contains the information of {Route ID4, Route Path Information12, Parent LookUp ID7p}. The node that received such a message allocates a new entry6from the unused pool of the Routing Table5. This entry is accessed with local LookUp ID7as a memory offset in the table5. The Map10is updated to have the relation between Route ID4and LookUp ID7. The forwarding port vector20aand the parent port number21is calculated by the routing protocol13from the route path information12, and written to the forward entry6. The Parent LookUp ID7pfrom the request message12is also written into the entry field9a. In the figure, P3 bit is set on the FW Vector20a,and the request is forwarded to the neighbor node connected to P3. On the neighbor node, the same process is executed, and forward the request to the next node with new LookUp ID7. It also returns the LookUp ID7nof the new entry for the Route ID4as Route Reply14to the sending node. The sending node updates the corresponding port LookUp ID9bwith the LookUP ID7non the reply message.

FIG. 12shows the relation of the forward table entries in neighbor nodes for the example in theFIG. 11. The node B1bis connected to node A on own port p3, and connected to node C1con own port p5. The node C1cis connected to node B1bon own port p2and node D1don own port p6. Node A1bsent the Route Request with own LookUp ID, and node B1b,node C1cprocessed the route request and route reply accordingly. Then the relation between the Route ID4and the LookUP ID B7bis created on the Map10on the node1b,and the Forwarding Table B5bin the node B1bhas the entry6bfor Route ID4with LookUp ID B7b.The entry6bstores FW Vector20with P5 bit set, Parent Port21with value 3, Child LookUp ID9bwith Look Up ID C7c,and Parent LookUp ID9awith LookUP ID for node A. The same way, the Routing Table C5cin node C1chas the entry6cfor the Route ID4with LookUp ID C7c. The entry6cstores FW Vector20with P6 bit set, Parent Port21with value 2, Child LookUp ID9bwith Look Up ID D, and Parent LookUp ID9awith LookUP ID7bfor node B.

FIG. 13shows an example usage of the conventional Ethernet packet frame to support the bidirectional transfer. The Ethernet packet frame15is formed with Preamble, SFD, Destination MAC Address16, Source MAC Address17, Ether Type18, Payload, and FCS. The same as theFIG. 8, the destination MAC can be used to carry the forwarding information. For bidirectional transfer support, we use MSB of Destination MAC Address as Direction Bit22, where 0 means forward, and 1 means backward. The rest of the MAC address will be used for Next LookUP ID field19for the next node.

When the Direction bit22is set to 0 (zero), the packet is forwarded using the FW Vector20in the table entry6. When the Direction bit22is set to 1 (one), the packet is transfer backward using the Parent Port21. So this example can support bidirectional path for a given Route ID4.

Multicast Routing

FIG. 14shows an example of multicast routing path. In the figure, multiple nodes, node U1u,node V1v,node W1w,node X1x,node Y1y,node Z1zare part of the mesh network. The nodes U1u,W1w,X1x,Z1zare the target destination nodes for a specific Route ID, and node Y1yand node V1vare the passing node that transfer a packet to next nodes. The FW Vector fields in the routing table entries are shown as20u,20v,20w,20x,20yand20z.For the destination nodes1u1w1x1zhas the P0 bit set, so that the packet received by the node is forwarded to the upper layer of the node. On each node, the received packet is forwarded to all the ports with the FW Vector bit set, except the port where the packet is received. With this rule, the FW Vector20and LookUp IDs9for all the ports can form the multicast path to any nodes in the mesh network.

This second example uses the FW Vector20for constructing multicast mechanism, but this is totally optional and it can carry just the child port number and parent port number if multicasting is not needed. In such case, the size of routing table entry6will be reduced and the table size requirement is much smaller. Multicasting can still be implemented using multiple table entries.

FIG. 9is a block diagram illustrating an example computing device900for use in the system500A ofFIG. 5A, according to one embodiment. The computing device900is an exemplary device that is implementable for the authentication server520A. Additionally, the computing device900is merely an example implementation itself, since the system500A can also be fully or partially implemented with laptop computers, tablet computers, smart cell phones, Internet appliances, and the like.

The computing device900, of the present embodiment, includes a memory910, a processor920, a hard drive930, and an I/O port940. Each of the components is coupled for electronic communication via a bus999. Communication can be digital and/or analog, and use any suitable protocol.

The memory910further comprises network applications912and an operating system914. The network applications912can include a web browser, a mobile application, an application that uses networking, a remote application executing locally, a network protocol application, a network management application, a network routing application, or the like.

The operating system914can be one of the Microsoft Windows® family of operating systems (e.g., Windows 95, 98, Me, Windows NT, Windows 2000, Windows XP, Windows XP x64 Edition, Windows Vista, Windows CE, Windows Mobile), Windows 7, Windows 8, Linux, HP-UX, UNIX, Sun OS, Solaris, Mac OS X, Alpha OS, AIX, IRIX32, or IRIX64. Other operating systems may be used. Microsoft Windows is a trademark of Microsoft Corporation.

The processor920can be a network processor (e.g., optimized for IEEE 802.11), a general purpose processor, an application-specific integrated circuit (ASIC), a field programmable gate array (FPGA), a reduced instruction set controller (RISC) processor, an integrated circuit, or the like. Qualcomm Atheros, Broadcom Corporation, and Marvell Semiconductors manufacture processors that are optimized for IEEE 802.11 devices. The processor920can be single core, multiple core, or include more than one processing elements. The processor920can be disposed on silicon or any other suitable material. The processor920can receive and execute instructions and data stored in the memory910or the storage device930.

The storage device930can be any non-volatile type of storage such as a magnetic disc, EEPROM, Flash, or the like. The storage device930stores code and data for applications.

The I/O port940further comprises a user interface942and a network interface944. The user interface942can output to a display device and receive input from, for example, a keyboard. The network interface944connects to a medium such as Ethernet or Wi-Fi for data input and output. In one embodiment, the network interface944includes IEEE 802.11 antennae.

Many of the functionalities described herein can be implemented with computer software, computer hardware, or a combination.