Topology discovery in a computing system

A computer network may comprise a plurality of computing devices. In one example, a method may be provided for discovering topology of the computer network. The method may comprise sending, by a host computing device of the computing network, a neighbor discovery packet to each network interface of the host that has a connection, receiving a reply packet responding to the neighbor discovery packet, building a neighbor map for all neighbor computing devices to the host, sending a connection discovery packet to each network interface of the host that has a connection, receiving reply packets responding to the connection discovery packet, and building a connection map for connections among computing devices based on the information in the reply packets.

FIELD OF THE DISCLOSURE

The systems, methods and apparatuses described herein relate to a computing system having a plurality of multi-core processing devices and a topology discovery mechanism to discover the connections among the processing devices.

BACKGROUND

Conventional technology has used various complex and cumbersome methods to determine the topology of a network. For example, in one existing method, the discovery process requires pre-existing knowledge of nodes in the computing system. At a system start up, the network adapters must work in a “promiscuous” mode. In this mode, all packets that arrive at the network card are received, regardless of addressing. Then, the network adapters must switch to a normal mode for normal operation. In the normal mode, only packets addressed to a particular network card are received. The existing methods are complex, slow and may produce inaccurate results, and therefore there exists a need for a method of discovering network topology that is simple, fast, and accurate.

SUMMARY

The present disclosure provides systems, methods and apparatuses for topology discovery in a computer network. In one aspect of the disclosure, a method may be provided for discovering topology of the computer network. The method may comprise sending, by a host computing device of the computing network, a neighbor discovery packet to each network interface of the host that has a connection, receiving a neighbor discovery reply packet responding to the neighbor discovery packet, building a neighbor map for all neighbor computing devices to the host, sending a connection discovery packet to each network interface of the host that has a connection, receiving connection discovery reply packets responding to the connection discovery packet, and building a connection map for connections among computing devices based on the information in the connection discovery reply packets.

In another aspect of the disclosure, a computer network according to the present disclosure may comprise a host and a plurality of computing devices. The host may comprise a plurality of network interfaces to be coupled to other computing devices in the computer network and a processor. The processor may be configured to send a neighbor discovery packet to each network interface of the plurality of network interfaces that has a connection, receive a neighbor discovery reply packet to the neighbor discovery packet, build a neighbor map for all neighbor computing devices to the host, send a connection discovery packet to each network interface of the host that has a connection, receive connection discovery reply packets responding to the connection discovery packet, and build a connection map for connections among computing devices based on the information in the connection discovery reply packets.

In yet another aspect of the disclosure, a method may be provided for operating a computing device in a computer network that has a plurality of computing devices. The method may comprise receiving a first neighbor discovery packet sent by a neighbor, replying to the first neighbor discovery packet on the network interface on which the first neighbor discovery packet is received, sending a second neighbor discovery packet to each network interface of the computing device that has a connection other than the network interface on which the first neighbor discovery packet is received, receiving a neighbor discovery reply packet responding to the second neighbor discovery packet, building a neighbor map for all neighbor computing devices, receiving a connection discovery packet on a network interface, recording the network interface on which the connection discovery packet is received, sending a connection discovery reply packet to the connection discovery packet, forwarding the connection discovery packet, and forwarding connection discovery reply packet(s) responding to the connection discovery packet.

In yet another aspect, the present disclosure may provide a computing device for use a part of a computer network that has a plurality of computing devices. The computing device may comprise a plurality of network interfaces to be coupled to other computing devices in the computer network and a processor. The processor may be configured to receive a first neighbor discovery packet sent by a neighbor, reply to the first neighbor discovery packet on the network interface on which the first neighbor discovery packet is received, send a second neighbor discovery packet to each network interface of the computing device that has a connection other than the network interface on which the first neighbor discovery packet is received, receive a neighbor discovery reply packet responding to the second neighbor discovery packet, build a neighbor map including all neighbor computing devices, receive a connection discovery packet on a network interface, record the network interface on which the connection discovery packet is received, send a connection discovery reply packet responding to the connection discovery packet, forward the connection discovery packet, and forward connection discovery reply packet(s) responding to the connection discovery packet.

DETAILED DESCRIPTION

Certain illustrative aspects of the systems, apparatuses, and methods according to the present invention are described herein in connection with the following description and the accompanying figures. These aspects are indicative, however, of but a few of the various ways in which the principles of the invention may be employed and the present invention is intended to include all such aspects and their equivalents. Other advantages and novel features of the invention may become apparent from the following detailed description when considered in conjunction with the figures.

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. In other instances, well known structures, interfaces, and processes have not been shown in detail in order to avoid unnecessarily obscuring the invention. However, it will be apparent to one of ordinary skill in the art that those specific details disclosed herein need not be used to practice the invention and do not represent a limitation on the scope of the invention, except as recited in the claims. It is intended that no part of this specification be construed to effect a disavowal of any part of the full scope of the invention. Although certain embodiments of the present disclosure are described, these embodiments likewise are not intended to limit the full scope of the invention.

FIG. 1Ashows an exemplary computing system100according to the present disclosure. The computing system100may comprise at least one processing device102. A typical computing system100, however, may comprise a plurality of processing devices102. Each processing device102, which may also be referred to as device102, may comprise a router104, a device controller106, a plurality of high speed interfaces108and a plurality of clusters110. The router104may also be referred to as a top level router or a level one router. Each cluster110may comprise a plurality of processing engines to provide computational capabilities for the computing system100. The high speed interfaces108may comprise communication ports to communicate data outside of the device102, for example, to other devices102of the computing system100and/or interfaces to other computing systems. Unless specifically expressed otherwise, data as used herein may refer to both program code and pieces of information upon which the program code operates.

In some implementations, the processing device102may include 2, 4, 8, 16, 32 or another number of high speed interfaces108. Each high speed interface108may implement a physical communication protocol. In one non-limiting example, each high speed interface108may implement the media access control (MAC) protocol, and thus may have a unique MAC address associated with it. The physical communication may be implemented in a known communication technology, for example, Gigabit Ethernet, or any other existing or future-developed communication technology. In one non-limiting example, each high speed interface108may implement bi-directional high-speed serial ports, such as 10 Giga bits per second (Gbps) serial ports. Two processing devices102implementing such high speed interfaces108may be directly coupled via one pair or multiple pairs of the high speed interfaces108, with each pair comprising one high speed interface108on one processing device102and another high speed interface108on the other processing device102.

Data communication between different computing resources of the computing system100may be implemented using routable packets. The computing resources may comprise device level resources such as a device controller106, cluster level resources such as a cluster controller or cluster memory controller, and/or the processing engine level resources such as individual processing engines and/or individual processing engine memory controllers. An exemplary packet140according to the present disclosure is shown inFIG. 5. The packet140may comprise a header142and a payload144. The header142may include a routable destination address for the packet140. The router104may be a top-most router configured to route packets on each processing device102. The router104may be a programmable router. That is, the routing information used by the router104may be programmed and updated. In one non-limiting embodiment, the router104may be implemented using an address resolution table (ART) or Look-up table (LUT) to route any packet it receives on the high speed interfaces108, or any of the internal interfaces interfacing the device controller106or clusters110. For example, depending on the destination address, a packet140received from one cluster110may be routed to a different cluster110on the same processing device102, or to a different processing device102; and a packet140received from one high speed interface108may be routed to a cluster110on the processing device or to a different processing device102.

The device controller106may control the operation of the processing device102from power on through power down. The device controller106may comprise a device controller processor, one or more registers and a device controller memory space. The device controller processor may be any existing or future-developed microcontroller. In one embodiment, for example, an ARM® Cortex M0microcontroller may be used for its small footprint and low power consumption. In another embodiment, a bigger and more powerful microcontroller may be chosen if needed. The one or more registers may include one to hold a device identifier (DEVID) for the processing device102after the processing device102is powered up. The DEVID may be used to uniquely identify the processing device102in the computing system100. In one non-limiting embodiment, the DEVID may be loaded on system start from a non-volatile storage, for example, a non-volatile internal storage on the processing device102or a non-volatile external storage. The device controller memory space may include both read-only memory (ROM) and random access memory (RAM). In one non-limiting embodiment, the ROM may store bootloader code that during a system start may be executed to initialize the processing device102and load the remainder of the boot code through a bus from outside of the device controller106. The instructions for the device controller processor, also referred to as the firmware, may reside in the RAM after they are loaded during the system start.

The registers and device controller memory space of the device controller106may be read and written to by computing resources of the computing system100using packets. That is, they are addressable using packets. As used herein, the term “memory” may refer to RAM, SRAM, DRAM, eDRAM, SDRAM, volatile memory, non-volatile memory, and/or other types of electronic memory. For example, the header of a packet may include a destination address such as DEVID:PADDR, of which the DEVID may identify the processing device102and the PADDR may be an address for a register of the device controller106or a memory location of the device controller memory space of a processing device102. In some embodiments, a packet directed to the device controller106may have a packet operation code, which may be referred to as packet opcode or just opcode to indicate what operation needs to be performed for the packet. For example, the packet operation code may indicate reading from or writing to the storage location pointed to by PADDR. It should be noted that the device controller106may also send packets in addition to receiving them. The packets sent by the device controller106may be self-initiated or in response to a received packet (e.g., a read request). Self-initiated packets may include for example, reporting status information, requesting data, etc.

In one embodiment, a plurality of clusters110on a processing device102may be grouped together.FIG. 1Bshows a block diagram of another exemplary processing device102A according to the present disclosure. The exemplary processing device102A is one particular embodiment of the processing device102. Therefore, the processing device102referred to in the present disclosure may include any embodiments of the processing device102, including the exemplary processing device102A. As shown onFIG. 1B, a plurality of clusters110may be grouped together to form a super cluster130and an exemplary processing device102A may comprise a plurality of such super clusters130. In one embodiment, a processing device102may include 2, 4, 8, 16, 32 or another number of clusters110, without further grouping the clusters110into super clusters. In another embodiment, a processing device102may include 2, 4, 8, 16, 32 or another number of super clusters130and each super cluster130may comprise a plurality of clusters.

FIG. 2Ashows a block diagram of an exemplary computing system100A according to the present disclosure. The computing system100A may be one exemplary embodiment of the computing system100ofFIG. 1A. The computing system100A may comprise a plurality of processing devices102designated as F1, F2, F3, F4, F5, F6, F7and F8. As shown inFIG. 2A, each processing device102may be directly coupled to one or more other processing devices102. For example, F4may be directly coupled to F1, F3and F5; and F7may be directly coupled to F1, F2and F8. Within computing system100A, one of the processing devices102may function as a host for the whole computing system100A. The host may have a unique device ID that every processing devices102in the computing system100A recognizes as the host. For example, any processing devices102may be designated as the host for the computing system100A. In one non-limiting example, F1may be designated as the host and the device ID for F1may be set as the unique device ID for the host.

In another embodiment, the host may be a computing device of a different type, such as a computer processor known in the art (for example, an ARM® Cortex or Intel® x86 processor) or any other existing or future-developed processors. In this embodiment, the host may communicate with the rest of the system100A through a communication interface, which may represent itself to the rest of the system100A as the host by having a device ID for the host.

The computing system100A may implement any appropriate techniques to set the DEVIDs, including the unique DEVID for the host, to the respective processing devices102of the computing system100A. In one exemplary embodiment, the DEVIDs may be stored in the ROM of the respective device controller106for each processing devices102and loaded into a register for the device controller106at power up. In another embodiment, the DEVIDs may be loaded from an external storage. In such an embodiment, the assignments of DEVIDs may be performed offline, and may be changed offline from time to time or as appropriate. Thus, the DEVIDs for one or more processing devices102may be different each time the computing system100A initializes. Moreover, the DEVIDs stored in the registers for each device controller106may be changed at runtime. This runtime change may be controlled by the host of the computing system100A. For example, after the initialization of the computing system100A, which may load the pre-configured DEVIDs from ROM or external storage, the host of the computing system100A may reconfigure the computing system100A and assign different DEVIDs to the processing devices102in the computing system100A to overwrite the initial DEVIDs in the registers of the device controllers106.

FIG. 2Bis a block diagram of a topology of another exemplary system100B according to the present disclosure. The computing system100B may be another exemplary embodiment of the computing system100ofFIG. 1and may comprise a plurality of processing devices102(designated as P1through P16onFIG. 2B), a bus202and a processing device P_Host. Each processing device of P1through P16may be directly coupled to another processing device of P1through P16by a direct link between them. At least one of the processing devices P1through P16may be coupled to the bus202. As shown inFIG. 2B, the processing devices P8, P5, P10, P13, P15and P16may be coupled to the bus202. The processing device P_Host may be coupled to the bus202and may be designated as the host for the computing system100B. In the exemplary system100B, the host may be a computer processor known in the art (for example, an ARM® Cortex or Intel® x86 processor) or any other existing or future-developed processors. The host may communicate with the rest of the system100B through a communication interface coupled to the bus and may represent itself to the rest of the system100B as the host by having a device ID for the host.

FIG. 3Ashows a block diagram of an exemplary cluster110according to the present disclosure. The exemplary cluster110may comprise a router112, a cluster controller116, an auxiliary instruction processor (AIP)114, a cluster memory118and a plurality of processing engines120. The router112may be coupled to an upstream router to provide interconnection between the upstream router and the cluster110. The upstream router may be, for example, the router104of the processing device102if the cluster110is not part of a super cluster130.

The exemplary operations to be performed by the router112may include receiving a packet destined for a resource within the cluster110from outside the cluster110and/or transmitting a packet originating within the cluster110destined for a resource inside or outside the cluster110. A resource within the cluster110may be, for example, the cluster memory118or any of the processing engines120within the cluster110. A resource outside the cluster110may be, for example, a resource in another cluster110of the computer device102, the device controller106of the processing device102, or a resource on another processing device102. In some embodiments, the router112may also transmit a packet to the router104even if the packet may target a resource within itself. In one embodiment, the router104may implement a loopback path to send the packet back to the originating cluster110if the destination resource is within the cluster110.

The cluster controller116may send packets, for example, as a response to a read request, or as unsolicited data sent by hardware for error or status report. The cluster controller116may also receive packets, for example, packets with opcodes to read or write data. In one embodiment, the cluster controller116may be any existing or future-developed microcontroller, for example, one of the ARM® Cortex-M microcontroller and may comprise one or more cluster control registers (CCRs) that provide configuration and control of the cluster110. In another embodiment, instead of using a microcontroller, the cluster controller116may be custom made to implement any functionalities for handling packets and controlling operation of the router112. In such an embodiment, the functionalities may be referred to as custom logic and may be implemented, for example, by FPGA or other specialized circuitry. Regardless of whether it is a microcontroller or implemented by custom logic, the cluster controller116may implement a fixed-purpose state machine encapsulating packets and memory access to the CCRs.

Each cluster memory118may be part of the overall addressable memory of the computing system100. That is, the addressable memory of the computing system100may include the cluster memories118of all clusters of all devices102of the computing system100. The cluster memory118may be a part of the main memory shared by the computing system100. In some embodiments, any memory location within the cluster memory118may be addressed by any processing engine within the computing system100by a physical address. The physical address may be a combination of the DEVID, a cluster identifier (CLSID) and a physical address location (PADDR) within the cluster memory118, which may be formed as a string of bits, such as, for example, DEVID:CLSID:PADDR. The DEVID may be associated with the device controller106as described above and the CLSID may be a unique identifier to uniquely identify the cluster110within the local processing device102. It should be noted that in at least some embodiments, each register of the cluster controller116may also be assigned a physical address (PADDR). Therefore, the physical address DEVID:CLSID:PADDR may also be used to address a register of the cluster controller116, in which PADDR may be an address assigned to the register of the cluster controller116.

In some other embodiments, any memory location within the cluster memory118may be addressed by any processing engine within the computing system100by a virtual address. The virtual address may be a combination of a DEVID, a CLSID and a virtual address location (ADDR), which may be formed as a string of bits, such as, for example, DEVID:CLSID:ADDR. The DEVID and CLSID in the virtual address may be the same as in the physical addresses.

In one embodiment, the width of ADDR may be specified by system configuration. For example, the width of ADDR may be loaded into a storage location convenient to the cluster memory118during system start and/or changed from time to time when the computing system100performs a system configuration. To convert the virtual address to a physical address, the value of ADDR may be added to a base physical address value (BASE). The BASE may also be specified by system configuration as the width of ADDR and stored in a location convenient to a memory controller of the cluster memory118. In one example, the width of ADDR may be stored in a first register and the BASE may be stored in a second register in the memory controller. Thus, the virtual address DEVID:CLSID:ADDR may be converted to a physical address as DEVID:CLSID:ADDR+BASE. Note that the result of ADDR+BASE has the same width as the longer of the two.

The address in the computing system100may be 8 bits, 16 bits, 32 bits, 64 bits, or any other number of bits wide. In one non-limiting example, the address may be 32 bits wide. The DEVID may be 10, 15, 20, 25 or any other number of bits wide. The width of the DEVID may be chosen based on the size of the computing system100, for example, how many processing devices102the computing system100has or may be designed to have. In one non-limiting example, the DEVID may be 20 bits wide and the computing system100using this width of DEVID may contain up to 220processing devices102. The width of the CLSID may be chosen based on how many clusters110the processing device102may be designed to have. For example, the CLSID may be 3, 4, 5, 6, 7, 8 bits or any other number of bits wide. In one non-limiting example, the CLSID may be 5 bits wide and the processing device102using this width of CLSID may contain up to 25clusters. The width of the PADDR for the cluster level may be 20, 30 or any other number of bits. In one non-limiting example, the PADDR for the cluster level may be 27 bits and the cluster110using this width of PADDR may contain up to 227memory locations and/or addressable registers. Therefore, in some embodiments, if the DEVID may be 20 bits wide, CLSID may be 5 bits and PADDR may have a width of 27 bits, a physical address DEVID:CLSID:PADDR or DEVID:CLSID:ADDR+BASE may be 52 bits.

For performing the virtual to physical memory conversion, the first register (ADDR register) may have 4, 5, 6, 7 bits or any other number of bits. In one non-limiting example, the first register may be 5 bits wide. If the value of the 5 bits register is four (4), the width of ADDR may be 4 bits; and if the value of 5 bits register is eight (8), the width of ADDR will be 8 bits. Regardless of ADDR being 4 bits or 8 bits wide, if the PADDR for the cluster level may be 27 bits then BASE may be 27 bits, and the result of ADDR+BASE may still be a 27 bits physical address within the cluster memory118.

FIG. 3Ashows that a cluster110may comprise one cluster memory118. In another embodiment, a cluster110may comprise a plurality of cluster memories118that each may comprise a memory controller and a plurality of memory banks, respectively. Moreover, in yet another embodiment, a cluster110may comprise a plurality of cluster memories118and these cluster memories118may be connected together via a router that may be downstream of the router112.

The AIP114may be a special processing engine shared by all processing engines120of one cluster110. In one example, the AIP114may be implemented as a coprocessor to the processing engines120. For example, the AIP114may implement less commonly used instructions such as some floating point arithmetic, including but not limited to, one or more of addition, subtraction, multiplication, division and square root, etc. As shown inFIG. 3A, the AIP114may be coupled to the router112directly and may be configured to send and receive packets via the router112. As a coprocessor to the processing engines120within the same cluster110, although not shown inFIG. 3A, the AIP114may also be coupled to each processing engines120within the same cluster110directly. In one embodiment, a bus shared by all the processing engines120within the same cluster110may be used for communication between the AIP114and all the processing engines120within the same cluster110. In another embodiment, a multiplexer may be used to control communication between the AIP114and all the processing engines120within the same cluster110. In yet another embodiment, a multiplexer may be used to control access to the bus shared by all the processing engines120within the same cluster110for communication with the AIP114.

The grouping of the processing engines120on a computing device102may have a hierarchy with multiple levels. For example, multiple clusters110may be grouped together to form a super cluster.FIG. 3Bis a block diagram of an exemplary super cluster130according to the present disclosure. As shown onFIG. 3B, a plurality of clusters110A through110H may be grouped into an exemplary super cluster130. Although 8 clusters are shown in the exemplary super cluster130onFIG. 3B, the exemplary super cluster130may comprise 2, 4, 8, 16, 32 or another number of clusters110. The exemplary super cluster130may comprise a router134and a super cluster controller132, in addition to the plurality of clusters110. The router134may be configured to route packets among the clusters110and the super cluster controller132within the super cluster130, and to and from resources outside the super cluster130via a link to an upstream router. In an embodiment in which the super cluster130may be used in a processing device102A, the upstream router for the router134may be the top level router104of the processing device102A and the router134may be an upstream router for the router112within the cluster110. In one embodiment, the super cluster controller132may implement CCRs, may be configured to receive and send packets, and may implement a fixed-purpose state machine encapsulating packets and memory access to the CCRs, and the super cluster controller132may be implemented similar to the cluster controller116. In another embodiment, the super cluster130may be implemented with just the router134and may not have a super cluster controller132.

An exemplary cluster110according to the present disclosure may include 2, 4, 8, 16, 32 or another number of processing engines120.FIG. 3Ashows an example of a plurality of processing engines120that have been grouped into a cluster110andFIG. 3Bshows an example of a plurality of clusters110that have been grouped into a super cluster130. Grouping of processing engines is not limited to clusters or super clusters. In one embodiment, more than two levels of grouping may be implemented and each level may have its own router and controller.

FIG. 4shows a block diagram of an exemplary processing engine120according to the present disclosure. As shown inFIG. 4, the processing engine120may comprise an engine core122, an engine memory124and a packet interface126. The processing engine120may be coupled to an AIP114. As described herein, the AIP114may be shared by all processing engines120within a cluster110. The processing core122may be a central processing unit (CPU) with an instruction set and may implement some or all features of modern CPUs, such as, for example, a multi-stage instruction pipeline, one or more arithmetic logic units (ALUs), a floating point unit (FPU) or any other existing or future-developed CPU technology. The instruction set may comprise one instruction set for the ALU to perform arithmetic and logic operations, and another instruction set for the FPU to perform floating point operations. In one embodiment, the FPU may be a completely separate execution unit containing a multi-stage, single-precision floating point pipeline. When an FPU instruction reaches the instruction pipeline of the processing engine120, the instruction and its source operand(s) may be dispatched to the FPU.

The instructions of the instruction set may implement the arithmetic and logic operations and the floating point operations, such as those in the INTEL® x86 instruction set, using a syntax similar or different from the x86 instructions. In some embodiments, the instruction set may include customized instructions. For example, one or more instructions may be implemented according to the features of the computing system100. In one example, one or more instructions may cause the processing engine executing the instructions to generate packets directly with system wide addressing. In another example, one or more instructions may have a memory address located anywhere in the computing system100as an operand. In such an example, a memory controller of the processing engine executing the instruction may generate packets according to the memory address being accessed.

The engine memory124may comprise a program memory, a register file comprising one or more general purpose registers, one or more special registers and one or more events registers. The program memory may be a physical memory for storing instructions to be executed by the processing core122and data to be operated upon by the instructions. In some embodiments, portions of the program memory may be disabled and powered down for energy savings. For example, a top half or a bottom half of the program memory may be disabled to save energy when executing a program small enough that less than half of the storage may be needed. The size of the program memory may be 1 thousand (1K), 2K, 3K, 4K, or any other number of storage units. The register file may comprise 128, 256, 512, 1024, or any other number of storage units. In one non-limiting example, the storage unit may be 32-bit wide, which may be referred to as a longword, and the program memory may comprise 2K 32-bit longwords and the register file may comprise 256 32-bit registers.

The register file may comprise one or more general purpose registers for the processing core122. The general purpose registers may serve functions that are similar or identical to the general purpose registers of an x86 architecture CPU.

The special registers may be used for configuration, control and/or status. Exemplary special registers may include one or more of the following registers: a program counter, which may be used to point to the program memory address where the next instruction to be executed by the processing core122is stored; and a device identifier (DEVID) register storing the DEVID of the processing device102.

In one exemplary embodiment, the register file may be implemented in two banks—one bank for odd addresses and one bank for even addresses—to permit fast access during operand fetching and storing. The even and odd banks may be selected based on the least-significant bit of the register address for if the computing system100is implemented in little endian or on the most-significant bit of the register address if the computing system100is implemented in big-endian.

The engine memory124may be part of the addressable memory space of the computing system100. That is, any storage location of the program memory, any general purpose register of the register file, any special register of the plurality of special registers and any event register of the plurality of events registers may be assigned a memory address PADDR. Each processing engine120on a processing device102may be assigned an engine identifier (ENGINE ID), therefore, to access the engine memory124, any addressable location of the engine memory124may be addressed by DEVID:CLSID:ENGINE ID: PADDR. In one embodiment, a packet addressed to an engine level memory location may include an address formed as DEVID:CLSID:ENGINE ID: EVENTS:PADDR, in which EVENTS may be one or more bits to set event flags in the destination processing engine120. It should be noted that when the address is formed as such, the events need not form part of the physical address, which is still DEVID:CLSID:ENGINE ID:PADDR. In this form, the events bits may identify one or more event registers to be set but these events bits may be separate from the physical address being accessed.

The packet interface126may comprise a communication port for communicating packets of data. The communication port may be coupled to the router112and the cluster memory118of the local cluster. For any received packets, the packet interface126may directly pass them through to the engine memory124. In some embodiments, a processing device102may implement two mechanisms to send a data packet to a processing engine120. For example, a first mechanism may use a data packet with a read or write packet opcode. This data packet may be delivered to the packet interface126and handled by the packet interface126according to the packet opcode. The packet interface126may comprise a buffer to hold a plurality of storage units, for example, 1K, 2K, 4K, or 8K or any other number. In a second mechanism, the engine memory124may further comprise a register region to provide a write-only, inbound data interface, which may be referred to a mailbox. In one embodiment, the mailbox may comprise two storage units that each can hold one packet at a time. The processing engine120may have a event flag, which may be set when a packet has arrived at the mailbox to alert the processing engine120to retrieve and process the arrived packet. When this packet is being processed, another packet may be received in the other storage unit but any subsequent packets may be buffered at the sender, for example, the router112or the cluster memory118, or any intermediate buffers.

In various embodiments, data request and delivery between different computing resources of the computing system100may be implemented by packets.FIG. 5illustrates a block diagram of an exemplary packet140according to the present disclosure. As shown inFIG. 5, the packet140may comprise a header142and an optional payload144. The header142may comprise a single address field, a packet opcode (POP) field and a size field. The single address field may indicate the address of the destination computing resource of the packet, which may be, for example, an address at a device controller level such as DEVID:PADDR, an address at a cluster level such as a physical address DEVID:CLSID:PADDR or a virtual address DEVID:CLSID:ADDR, or an address at a processing engine level such as DEVID:CLSID:ENGINE ID:PADDR or DEVID:CLSID:ENGINE ID:EVENTS:PADDR. The POP field may include a code to indicate an operation to be performed by the destination computing resource. Exemplary operations in the POP field may include read (to read data from the destination) and write (to write data (e.g., in the payload144) to the destination).

In some embodiments, the exemplary operations in the POP field may further include bulk data transfer. For example, certain computing resources may implement a direct memory access (DMA) feature. Exemplary computing resources that implement DMA may include a cluster memory controller of each cluster memory118, a memory controller of each engine memory124, and a memory controller of each device controller106. Any two computing resources that implemented the DMA may perform bulk data transfer between them using packets with a packet opcode for bulk data transfer.

In addition to bulk data transfer, in some embodiments, the exemplary operations in the POP field may further include transmission of unsolicited data. For example, any computing resource may generate a status report or incur an error during operation, the status or error may be reported to a destination using a packet with a packet opcode indicating that the payload144contains the source computing resource and the status or error data.

The POP field may be 2, 3, 4, 5 or any other number of bits wide. In some embodiments, the width of the POP field may be selected depending on the number of operations defined for packets in the computing system100. Also, in some embodiments, a packet opcode value can have different meaning based on the type of the destination computer resources that receives it. By way of example and not limitation, for a three-bit POP field, a value001may be defined as a read operation for a processing engine120but a write operation for a cluster memory118.

In some embodiments, the header142may further comprise an addressing mode field and an addressing level field. The addressing mode field may contain a value to indicate whether the single address field contains a physical address or a virtual address that may need to be converted to a physical address at a destination. The addressing level field may contain a value to indicate whether the destination is at a device, cluster memory or processing engine level.

The payload144of the packet140is optional. If a particular packet140does not include a payload144, the size field of the header142may have a value of zero. In some embodiments, the payload144of the packet140may contain a return address. For example, if a packet is a read request, the return address for any data to be read may be contained in the payload144.

FIG. 6is a flow diagram showing an exemplary process200of addressing a computing resource using a packet according to the present disclosure. An exemplary embodiment of the computing system100may have one or more processing devices configured to execute some or all of the operations of exemplary process600in response to instructions stored electronically on an electronic storage medium. The one or more processing devices may include one or more devices configured through hardware, firmware, and/or software to be specifically designed for execution of one or more of the operations of exemplary process600.

The exemplary process600may start with block602, at which a packet may be generated at a source computing resource of the exemplary embodiment of the computing system100. The source computing resource may be, for example, a device controller106, a cluster controller118, a super cluster controller132if super cluster is implemented, an AIP114, a memory controller for a cluster memory118, or a processing engine120. The generated packet may be an exemplary embodiment of the packet140according to the present disclosure. From block602, the exemplary process600may continue to the block604, where the packet may be transmitted to an appropriate router based on the source computing resource that generated the packet. For example, if the source computing resource is a device controller106, the generated packet may be transmitted to a top level router104of the local processing device102; if the source computing resource is a cluster controller116, the generated packet may be transmitted to a router112of the local cluster110; if the source computing resource is a memory controller of the cluster memory118, the generated packet may be transmitted to a router112of the local cluster110, or a router downstream of the router112if there are multiple cluster memories118coupled together by the router downstream of the router112; and if the source computing resource is a processing engine120, the generated packet may be transmitted to a router of the local cluster110if the destination is outside the local cluster and to a memory controller of the cluster memory118of the local cluster110if the destination is within the local cluster.

At block606, a route for the generated packet may be determined at the router. As described herein, the generated packet may comprise a header that includes a single destination address. The single destination address may be any addressable location of a uniform memory space of the computing system100. The uniform memory space may be an addressable space that covers all memories and registers for each device controller, cluster controller, super cluster controller if super cluster is implemented, cluster memory and processing engine of the computing system100. In some embodiments, the addressable location may be part of a destination computing resource of the computing system100. The destination computing resource may be, for example, another device controller106, another cluster controller118, a memory controller for another cluster memory118, or another processing engine120, which is different from the source computing resource. The router that received the generated packet may determine the route for the generated packet based on the single destination address. At block608, the generated packet may be routed to its destination computing resource.

FIG. 7illustrates an exemplary computer network700according to the present disclosure. The exemplary computer network700may comprise a plurality of nodes. Each of the plurality of nodes may be a computing device. One such computing device may be designated as a host, such as the host11shown inFIG. 7. Other computing devices may be the nodes702A through702K, which may also be referred to as computing devices702A through702K. Each of the computing devices may be assigned an identifier, which may be referred to as a computing device ID, to uniquely identify the respective computing device in the computer network700. The host11may have a unique identifier that each of the computing devices702A through702K recognize as the host identifier. The number of the computing devices702may be as low as a couple or as high as hundreds of thousands, or even higher, limited only by the width of computing device identifier. The exact number of computing devices702is immaterial and thus, the computing devices702are shown in phantom.

The computing devices702may be the same type or different types of computing devices. Exemplary computing device may be a computer (such as but not limited to, a commercially available personal computer, a commercially available server computer, a computer built using one or more processing devices102as CPUs) or a computer processor (such as but not limited to, a commercially available single core computer processor, a commercially available multi-core processor, or a processing device102). The host11may be the same type of computing device as at least one of the computing device702or may be a different type of computing device from all the computing devices702. In one embodiment, all of the computing devices702may be processing devices102, and the computer network700may be one exemplary embodiment of the system100and may implement all features of the computing system100described herein. In another embodiment, all of the computing devices702may be computers comprising processing devices102, and each computing device702may be one exemplary embodiment of the system100and may implement some or all of the features of the computing system100according to the present disclosure.

In one embodiment, the computing devices702may have multiple network interfaces. For example, if the computing device702is a computer, that computer may have at least two, but maybe more, network cards; on the other hand, if the computing device702is a computer processor, the computer processor itself or its mother board may have at least two but may be more network ports.

In one embodiment, the bidirectional links between the computing devices may represent direct links between the computing devices. In one embodiment, a direct link may be a point to point wired link with one end coupled to a network card or network port on one computing device and another end coupled to a network card or network port on another computing device. In another embodiment, there may be other components on a direct link, such as but not limited to, a signal booster, or a relay. In yet another embodiment, a direct link may be a wireless communication link. Regardless of the types of links, communication between the computing devices (including the host11and computing devices702) may be based on packets. The packets may be in a format in accordance with a network protocol implemented by both the sender and the receiver. For example, the packets may be IP packets if both the sender and receiver implement the TCP/IP network protocols. In an embodiment, the computing devices702may be processing devices102, and the packets may be embodiments of the packet shown inFIG. 5. Other packets may also be used, including packets according to any existing or future-developed network protocols.

In one embodiment, the network among the computing devices of the computer network700may be a homogeneous network. That is, the network may include only one type of network connections, such as but not limited to, one of Ethernet, Asynchronous Transfer Mode (ATM), and Gigabit Ethernet, etc. In another embodiment, the network among the computing devices of the computer network700may be a heterogeneous network and include a variety of types of network connections. For example, the host11may have an Ethernet connection to the computing device702A, an Asynchronous Transfer Mode (ATM) connection to the computing device702J, and a Gigabit Ethernet connection to the computing device702C, and each of computing devices702A,702J and702C may have other types of network connections to other computing devices that are connected to them.

The host11may comprise one or more processors20, a physical storage60, and an interface40. Interface40may be configured to provide an interface between the computer network700and a user (e.g., a system administrator) through which the user can provide and/or receive information. This enables data, results, and/or instructions and any other communicable items, collectively referred to as “information,” to be communicated between the user and the computer network700. Examples of interface devices suitable for inclusion in interface40include a keypad, buttons, switches, a keyboard, knobs, levers, a display screen, a touch screen, speakers, a microphone, an indicator light, an audible alarm, and a printer. Information may be provided by interface40in the form of auditory signals, visual signals, tactile signals, and/or other sensory signals.

It is to be understood that other communication techniques, either hard-wired or wireless, are also contemplated herein as interface40. For example, in some implementations, interface40may be integrated with physical storage60. In this example, information is loaded into the host11from storage (e.g., a smart card, a flash drive, a removable disk, etc.) that enables the user(s) to customize the implementation of the host11. Other exemplary input devices and techniques adapted for use with the host11as interface40include, but are not limited to, an RS-232 port, RF link, an IR link, modem (telephone, cable, Ethernet, internet or other). In short, any technique for communicating information with the host11is contemplated as interface40.

Physical storage60of the host11inFIG. 7may comprise electronic storage media that stores information. In some implementations, physical storage60may store representations of computer program components, including instructions that implement the computer program components. The electronic storage media of physical storage60may include one or both of system storage that is provided integrally (i.e., substantially non-removable) with host11and/or removable storage that is removably connectable to host11via, for example, a port (e.g., a USB port, a FIREWIRE port, etc.) or a drive (e.g., a disk drive, etc.). Physical storage60may include one or more of optically readable storage media (e.g., optical disks, etc.), magnetically readable storage media (e.g., magnetic tape, magnetic hard drive, floppy drive, etc.), electrical charge-based storage media (e.g., EEPROM, RAM, etc.), solid-state storage media (e.g., flash drive, etc.), network-attached storage (NAS), and/or other electronically readable storage media. Physical storage60may include virtual storage resources, such as storage resources provided via a cloud and/or a virtual private network. Physical storage60may store software algorithms, information determined by processor20, information received from outside of host11, and/or other information that enable host11and computer network700to function properly. Physical storage60may be one or more separate components within the host11, or physical storage60may be provided integrally with one or more other components of the host11(e.g., processor20).

One or more processors20(interchangeably referred to herein as processor20) may be configured to execute one or more computer program components. The computer program components may include a discovery component24, and/or other components. The functionality provided by component24may be attributed for illustrative purposes to one or more particular components of host11. This is not intended to be limiting in any way, and any functionality may be provided by any component or entity described herein.

The functionality provided by the discovery component24may be used to discover the topology of the computer network700. As used herein, the topology may comprise information that shows how the computing devices702may be interconnected. In one embodiment, the computer network700may be configured to discover the interconnections of the computing devices702in two phases. During the first phase, the host11may send a packet to each of its network interfaces that has a link coupled to it. For example, as shown inFIG. 7, the host11may have links to computing devices702A,702C,702J and702I, and the host11may send a packet to the computing devices702A,702C,702J and702I, respectively. Regardless of its format or network protocol, the packet may contain a piece of information to identify itself as a neighbor discovery packet. For example, the packet may contain a label (in its header or payload), such as but not limited to, “NEIGHBOR-DISCOVERY” or a sequence of bits “00001.” In one embodiment, the sender's computing device ID may also be included in the packet. In another embodiment, the sender's computing device ID is not needed in the packet.

In one embodiment, the recipient of the neighbor discovery packet may then create and send further neighbor discovery packets on all the ports other than the one on which the neighbor discovery packet was received. In another embodiment, the recipient of the neighbor discovery packet has an indication of whether each port is connected or disconnected. In this embodiment, the recipient of the neighbor discovery packet may send a further neighbor discovery packet only out of those ports that are connected. For example, the computing device702A may have links to the computing devices702B and702D in addition to the host11, so it may send a further neighbor discovery packet to the computing devices702B and702D, respectively. In the embodiment in which the neighbor discovery packet contains the sender's computing device ID, the computing device ID for the computing device that sends a further neighbor discovery packet will be included as the sender's computing device ID.

The recipient of the neighbor discovery packet may record the network interface (e.g., a port number) on which the neighbor discovery packet is received and generate a neighbor discovery reply packet. The recorded network interface information may be maintained, for example, in a database, table, file or data structure with appropriate fields, entries, records or the like. The neighbor discovery reply packet may contain the recipient's computing device ID and a piece of information to identify itself as a neighbor discovery reply packet. The piece of information may be, for example, a label (in its header or payload), such as but not limited to, “NEIGHBOR-DISCOVERY-REPLY” or a sequence of bits “00010.” The recipient may send the neighbor discovery reply packet on the same network interface on which the neighbor discovery packet is received. That is, the neighbor discovery reply packet may be sent back to the sender of the neighbor discovery packet on a one-to-one mapping. For example, the host11may receive respective neighbor discovery reply packets from the computing devices702A,702C,702J and702I; and the computing device702A may receive respective neighbor discovery reply packets from the computing devices702B and702D.

A computing device702may receive neighbor discovery packets on multiple network interfaces. For example, the computing device702B may receive one neighbor discovery packet on the network interface that is connected to the computing device702A and another neighbor discovery packet on the network interface that is connected to the computing device702J. In one embodiment, the computing device702may send a further neighbor discovery packet only responsive to the first neighbor discovery packet it receives, but it still needs to respond to all received neighbor discovery packets with neighbor discovery reply packets. For example, the computing device702B may receive the neighbor discovery packet on the network interface connected to the computing device702J first. In this case, although the computing device702B will receive neighbor discovery packets from both the computing devices702A and702J, it only sends further neighbor discovery packets responsive to the first neighbor discovery packet it receives from the computing device702J. The further neighbor discovery packets will be sent to both computing devices702A and702E because these two computing devices are coupled to by network interfaces other than the one on which the first neighbor discovery packet is received. Further, the computing device702B needs to generate and send two neighbor discovery reply packets responsive to the neighbor discovery packets from the computing devices702A and702J respectively.

Once the neighbor discovery reply packets are received by the senders of the neighbor discovery packets, these senders may record the network interface (e.g., the port number) on which the individual neighbor discovery reply packet was received and generate a map of its neighboring computing devices. The first phase may conclude once each computing device702has completed this process and generated a map of its neighboring computing devices, which may also be referred simply as neighbors. In one embodiment, the map may be in a format of a database, table, file and data structure that contain entries for each neighboring computing device ID and its corresponding network interface.

The computer network700may implement some mechanism to mark the conclusion of the first phase. In one embodiment, the host11may have a timer that starts counting when it sends the first neighbor discovery packet. Each time a computing device receives the first neighbor discovery packet, it may respond by sending a status reporting packet on the network interface on which the first neighbor discovery packet is received. The status reporting packet may be forwarded by each receiving computing device on the network interface on which it receives its first neighbor discovery packet and may ultimately be received by the host11. The host11may reset the timer each time such a status reporting packet is received. The conclusion of the first phase may be determined when the timer's counting reaches a predetermined amount of time, for example, 1 millisecond, 2 milliseconds, or another amount of time, which may be programmable. In one embodiment, the predetermined amount of time may be configured based on the size of the network700.

In one embodiment, the discovery component24may be configured to send the neighbor discovery packet, respond with the neighbor discovery reply packets and generate the map of neighboring computing devices. Each computing device702may also implement these features in a component similar to the discovery component24, which may be implemented in hardware, software or combination of both.

The second phase of the discovery may start by the host11sending out packets to inquire about each computing devices' connections. In one embodiment, the discovery component11of the host11may be configured to send out a connection discovery packet to each of its immediate neighbors. Referring toFIG. 7, because the host11is directly coupled to computing devices702A,702C,702J and702I, the connection discovery packets may be sent computing devices702A,702C,702J and702I, respectively.

Each computing device702may be configured to handle a connection discovery packet by recording the network interface on which the connection discovery packet is received. For example, the computing device702A may record the network interface linked to the host11as a “host-ward” network interface. Each computing device702may also be configured to send a connection discovery reply packet (on that host-ward network interface) containing the computing device IDs of the computing devices to which the computing device702is directly connected (e.g., as recorded in the previous phase). For example, the computing device702A may reply that it is directly connected to the computing devices702B and702D; the computing device702C may reply that it is directly connected to the computing devices702G and702F; the computing device702J may reply that it is directly connected to the computing devices702B and702H; and the computing device702I may reply that it is directly connected to the computing device702D.

Each computing device702may also be configured to forward the received connection discovery packet to all network interfaces that are connected by links to other computing devices702. For example, the computing device702A may forward the received connection discovery packet to the computing devices702B and702D; the computing device702C may forward the received connection discovery packet to the computing devices702G and702F; the computing device702J may forward the received connection discovery packet to the computing devices702B and702H; and the computing device702I may forward the received connection discovery packet to the computing device702D.

In one embodiment, a computing device702may be configured to process the first connection discovery packet it receives by recording the network interface on which the first connection discovery packet is received, and to ignore any subsequently received connection discovery packet(s). For example, the computing device702D may receive the connection discovery packets from the computing devices702A and702I respectively. For whatever reason, one of the connection discovery packets may be received earlier than the other. In that case, the first one maybe recorded, responded to and forwarded, and the second one may be ignored. For example, if the first one is the connection discovery packet received from the computing device702A, then this one may be recorded, responded to and forwarded (e.g., to the computing devices702I and702E); and the second one received from the computing device702I may be ignored.

The computing devices702may also receive connection discovery reply packet(s) responding to any connection discovery packet(s) they forwarded to neighboring computing device(s)702. The connection discovery reply packet(s) may also include connection discovery reply packet(s) received by the neighboring computing device(s)702after it (they) forwarded the connection discovery packet. In one embodiment, the computing devices702may be configured to forward the connection discovery reply packet(s) they receive on their respective “host-ward” network interface.

Because the connection discovery reply packets are all sent on the “host-ward” network interface, the host11will ultimately receive all of the connection discovery reply packets. Based on the connection discovery reply packets, the host11may build a complete map of all connection(s) from every computing device702to every other computing devices702in the computer network700. Reference to a complete map of all connections is intended to refer to a record of all the connections between and among all the computing devices and the host in the network700. Such a record may be maintained, for example, in a database, table, file or data structure with appropriate fields, entries, records or the like to indicate, for each computing device702(or host), all other computing device(s) (or host) to which the particular computing device is connected and the network interface through which the connection is implemented.

In one embodiment, each computing device702may be configured to store a look-up table that may describe how packets are to be routed. After building the complete map of the physical connections between computing devices702, the host11may send out programming packets to program these look-up tables. The programming packets may contain routing information to define the routing to be used by each computing device702. The host11may first program the look-up tables of the computing device(s) to which the host11is directly connected, and then the computing devices702to which those already programmed are directly connected may be programmed, and the process may be repeated to all computing devices702in the network.

At the conclusion of the process, the host11may have a map of all the physical connections in the computer network700. Each computing device702may also have a map of its physical connections to its neighbors, and its lookup table programmed to indicate how to route packets to a computing device to which the computing device from which the packet originates is not directly connected. For example, with respect to the embodimentFIG. 7, the computing device702G has no direct connection to the computing device702F. At the conclusion of the process, the look up table associated with the computing device702G may be programmed such that a packet that is to be sent from the computing device702G to the computing device702F is sent to the computing device702C which will then forwarded to the computing device702F. In one embodiment, the look up tables may also be programmed to include alternative routes. For example, the route from the computing device702G through the computing device702C to the computing device702F may be designated as a primary path and the route from the computing device702G through the computing device702K to the computing device702F may be designated as a secondary path. Secondary paths may be used when , for example, the primary path is not available (e.g., because of a hardware or software malfunction along the primary path) or when the primary path is unduly slow or experiences delay (e.g., because of congestion).

In one embodiment, the discovery component24may be configured to send the connection discovery packet and generate the complete map. Programming look-up tables of the computing devices702may be optionally implemented by the discovery component24but may also be implemented by other components of the host11.

In some embodiments, the computing devices702may be embodiments of the processing devices102, the functionality for the topology discovery may be implemented in hardware, software or both by the device controller106of each processing device102. Further, in such an embodiment, the look up tables may be maintained in the top level router104of each processing device102.

Referring toFIG. 7, one or more processors20may be configured to provide information-processing capabilities in the computer network700and/or host11. As such, processor20may include one or more of a digital processor, an analog processor, a digital circuit designed to process information, an analog circuit designed to process information, a state machine, and/or other mechanisms for electronically processing information. Although processor20may be shown inFIG. 7as a single entity, this is for illustrative purposes only. In one embodiment, processor20may include a plurality of processing units. For example, each processor20may be a processing device102as described herein or a processor of a different type. These processing units may be physically located within the same physical apparatus, or processor20may represent processing functionality of a plurality of apparatuses operating in coordination (e.g., “in the cloud”, and/or other virtualized processing solutions).

The description of the functionality provided by the discovery components24described herein is for illustrative purposes, and is not intended to be limiting, as the discovery component24may provide more or less functionality than is described. For example, the discovery component24may be eliminated and some or all of its functionality may be provided in other components (not shown) of host11.

FIG. 8illustrates an exemplary process800for discovering topology of a computer network by a host of the computer network according to the present disclosure. In some implementations, the exemplary process800may be accomplished with one or more additional operations not described, and/or without one or more of the operations discussed. Additionally, the order in which the operations of process800are illustrated inFIG. 8and described below is not intended to be limiting.

The exemplary process800may start with block802, at which a neighbor discovery packet may be sent to each network interface with physical connections. For example, as shown inFIG. 7, the host11may be connected to the computing devices702A,702C,702J and702I and the host11may be configured to send a neighbor discovery packet to the network interfaces connected to each of the computing devices702A,702C,702J and702I, respectively.

At block804, the host11may receive the neighbor discovery reply packets in response to the neighbor discovery packets. The neighbors may send neighbor discovery reply packets to the host11in response to the neighbor discovery packets. For example, the host11may receive neighbor discovery reply packets from the computing devices702A,702C,702J and702I and the neighbor discovery reply packets may contain the computing device IDs for the computing devices702A,702C,702J and702I respectively. As described above with respect toFIG. 7, in one embodiment, each neighbor discovery reply packet may contain the neighbor discovery packet recipient's computing device ID and thus, the computing devices702A,702C,702J and702I may include their respective computing device IDs in the respective neighbor discovery reply packets. At block806, a neighbor map may be built that may include all neighbor computing devices. For example, the host11may build a map for all its neighbor computing devices, in this case, the computing devices702A,702C,702J and702I. As described above with respect toFIG. 7, the map may also include the network interface information for linking the host11to each of the neighbors.

At block808, the host11may send a connection discovery packet to each computing device to which it is connected. For example, in the embodiment ofFIG. 7, the host11may send connection discovery packets to the computing devices702A,702C,702J and702I on respective network interfaces that are connected to these computing devices. At block810, connection discovery reply packets to the connection discovery packet may be received. As described above with respect toFIG. 7, the computing devices702may generate connection discovery reply packets to report their connections with other computing devices702in response to the connection discovery packet, and they may also forward the connection discovery packet to its neighbors, and forward the connection discovery reply packets it receives from its neighbors back to the host11(e.g., via the “host-ward” network interface). In one embodiment, the host11may implement a programmable maximum wait period for receiving the connection discovery reply packets.

At block812, a connections map may be built for connections among the computing devices702based on the information in the connection discovery reply packets. For example, each connection discovery reply packet may include the connections information for the computing device702that sends the connection discovery reply packet. The host11may obtain the connections information from all connection discovery reply packets and build the connections map. At optional block814, one or more packets may be sent to program look-up tables in the computing devices. As described above with respect toFIG. 7, the computing devices702may each contain a look-up table and the host11may use the connections map to program each computing device702to configure the routing information for each computing device702.

FIG. 9illustrate an exemplary process900for a computing device in a network to participate topology discovery according to the present disclosure. In some implementations, the exemplary process900may be accomplished with one or more additional operations not described, and/or without one or more of the operations discussed. Additionally, the order in which the operations of process900are illustrated inFIG. 9and described below is not intended to be limiting.

The exemplary process900may start with block902, a neighbor discovery packet sent by a neighbor may be received. In the exemplary network700, each computing device702may be connected to several other computing devices702by direct links. For example, as shown inFIG. 7,the computing device702B may be directly connected to the computing devices702A,702J and702E respectively, and thus, the computing device702B may receive neighbor discovery packets from the computing devices702A and702B respectively.

At block904, neighbor discovery reply packets to the neighbor discovery packets may be sent on the network interfaces on which the respective neighbor discovery packets are received. For example, the computing device702B may receive neighbor discovery packets from the computing devices702A and702J respectively, and thus, the computing device702B may send neighbor discovery reply packets on the respective network interfaces linked to the computing devices702A and702J. As described above with respect toFIG. 7, in one embodiment, each neighbor discovery reply packet may contain the neighbor discovery packet recipient's computing device ID and thus, the computing device702B may include its computing device ID in the neighbor discovery reply packets.

At block906, the computing device702may send further neighbor discovery packet(s) on network interface(s) other than the network interface on which the first neighbor discovery packet is received. As described with response toFIG. 7, a computing device702may receive several neighbor discovery packets, and may generate and send further neighbor discovery packet(s) only responsive to the first neighbor discovery packet it receives.

At block908, the computing device702which sent the further neighbor discovery packets may receive neighbor discovery reply packets in response to the further neighbor discovery packets. The neighbors may send neighbor discovery reply packets in response to receiving the further neighbor discovery packets. For example, the computing device702B may receive neighbor discovery reply packets from the computing devices702A and702E because it receives the neighbor discovery packet from the computing device702J first and hence only sends further neighbor discovery packets to the computing devices702A and702E. The neighbor discovery reply packets may contain the computing device IDs for the computing devices702A and702E respectively. At block910, a neighbor map may be built that may include all neighbor computing devices. For example, the computing device702B may build a map for all its neighbor computing devices, in this case, the computing device702J from which the computing device702B may receive the first neighbor discovery packet and the computing devices702A and702E that respond to the further neighbor discovery packet with their respective neighbor discovery reply packets. As described above with respect toFIG. 7, the map may also include the network interface information for linking the computing device702B to each of the neighbors.

At block912, a connection discovery packet may be received. For example, the computing device702A may receive a connection discovery packet from the host11directly, the computing device702B may receive connection discovery packets from the computing devices702A and702J, and so forth. At block914, the network interface on which the connection discovery packet is received may be recorded. As described with respect toFIG. 7, in one embodiment, the first received connection discovery packet may be processed and any subsequent connection discovery packet(s) may be ignored and the network interface that received the first received discovery packet may be recorded as “host-ward.” At block916, a connection discovery reply packet responsive to the connection discovery packet may be sent. The connection discovery reply packet may include, for example, the connections information for the computing device that is originating the connection discovery reply packet. The connections information may be based on the neighbor map built at block910.

At block918, the connection discovery packet may be forwarded. As described above with respect toFIG. 7, a computing device702may be configured to forward the connection discovery packet to its neighbors. For example, the computing device702A may forward the connection discovery packet to the computing devices702B and702D. At block920, any connection discovery reply packets responsive to the connection discovery packets received from neighbors may be forwarded back to the host, for example, using the “host-ward” network interface. At optional block922, one or more packets may be received to program look-up tables in the computing devices. As described herein, the computing devices702may each contain a look-up table and the host11may use the connections map program each computing device702to configure the routing information for each computing device702.

In one embodiment, the host11and all computing devices702may participate in the topology discovery process and therefore, some operations the processes800and900may be performed by the host11and respective computing devices702in an interleaved manner.

While specific embodiments and applications of the present invention have been illustrated and described, it is to be understood that the invention is not limited to the precise configuration and components disclosed herein. The terms, descriptions and figures used herein are set forth by way of illustration only and are not meant as limitations. Various modifications, changes, and variations which will be apparent to those skilled in the art may be made in the arrangement, operation, and details of the apparatuses, methods and systems of the present invention disclosed herein without departing from the spirit and scope of the invention. By way of non-limiting example, it will be understood that the block diagrams included herein are intended to show a selected subset of the components of each apparatus and system, and each pictured apparatus and system may include other components which are not shown on the drawings. Additionally, those with ordinary skill in the art will recognize that certain steps and functionalities described herein may be omitted or re-ordered without detracting from the scope or performance of the embodiments described herein.

The various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. The described functionality can be implemented in varying ways for each particular application—such as by using any combination of microprocessors, microcontrollers, field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and/or System on a Chip (SoC)—but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM, flash memory, ROM, EPROM, EEPROM, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art.