WO2024099565A1

WO2024099565A1 - Method and apparatus for scheduling for input-queued switches

Info

Publication number: WO2024099565A1
Application number: PCT/EP2022/081425
Authority: WO
Inventors: Rami Zecharia; Zion GAL
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2022-11-10
Filing date: 2022-11-10
Publication date: 2024-05-16
Anticipated expiration: 2025-05-10
Also published as: CN120167109A

Abstract

There is a processor configured for: in an initial iteration: sending by input ports, first instances of a request message to output ports. Each request message includes an identifier of the input port. Each output port that selected an input port sends a grant message to the selected input port. The identifier of the selected input port is stored. In each respective iteration: sending, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier. Each corresponding output port that received the subsequent instance of the request message checks that the identifier included in the subsequent request message matches the stored identifier. In response to termination of the iterations: forwarding by each input port, data destined for the corresponding output port.

Description

METHOD AND APPARATUS FOR SCHEDULING FOR INPUT-QUEUED SWITCHES

BACKGROUND

The present disclosure, in some embodiments thereof, relates to switches and, more specifically, but not exclusively, to a method and apparatus for scheduling for input-queued switches.

A switch may include buffered input ports, a switch fabric and buffered output ports. If first-in first-out (FIFO) input buffers are used, only the oldest packet is available for forwarding. More recent arrivals cannot be forwarded if the oldest packet cannot be forwarded because its destination output is busy. The output may be busy if there is output contention.

SUMMARY

It is an object of the present invention to provide a device, a system, a computer program, a method for establishing communication channels between input and output ports.

The foregoing and other objects are achieved by the features of the independent claims. Further implementation forms are apparent from the dependent claims, the description and the figures.

According to a first aspect, a device for establishing a plurality of communication channels, comprises: at least one processor in communication with a plurality of input ports and a plurality of output ports, configured for: in an initial iteration: sending by the plurality of input ports, a plurality of first instances of a request message to the plurality of output ports, each respective request message including an identifier of the respective input port, sending by each output port that selected an input port, a respective grant message to the selected input port, and storing the identifier of the selected input port, in each respective iteration of one or more iterations: sending, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier of the input port, checking by each corresponding output port that received the subsequent instance of the request message, that the identifier of the input port included in the subsequent request message matches the stored identifier, and in response to termination of the iterations: forwarding by each input port, data destined for the corresponding output port.

According to a second aspect, a device including an input port for establishing a communication channel with one of a plurality of output ports, comprises: a processor in communication with the input port, configured for: in an initial iteration: sending to each one of a plurality of output ports, a first instance of a request message, each respective request message including an identifier of the input port, receiving a grant message from an output port of the plurality of output ports, in each respective iteration of one or more iterations: in response to receiving the grant message in a preceding iteration, sending a subsequent instance of the request messages that includes the identifier, to the output port, in response to not receiving the grant message in the preceding iteration, sending a plurality of subsequent instances of the request message to the plurality of output ports, and in response to termination of the iterations: forwarding data to the output port.

According to a third aspect, a device including an output port for establishing a communication channel with one of a plurality of input ports, comprises: a processor in communication with the output port, configured for: in an initial iteration: receiving a plurality of first instances of request messages each including an identifier of an input port of a plurality of input ports that sent the respective request message, selecting one of the plurality of input ports, sending a grant message to the selected input port, storing the identifier of the selected input port included in the request message, in each respective iteration of one or more iterations: receiving a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message, checking that the identifier in the subsequent instance of the request message matches the stored identifier, in response to termination of the iterations: receiving data from the input port.

According to a fourth aspect, a computer implemented method for establishing a plurality of communication channels, comprises: in an initial iteration: sending by the plurality of input ports, a plurality of first instances of a request message to the plurality of output ports, each respective request message including an identifier of the respective input port, sending by each output port that selected an input port, a respective grant message to the selected input port, and storing the identifier of the selected input port, in each respective iteration of one or more iterations: sending, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier of the input port, checking by each corresponding output port that received the subsequent instance of the request message, that the identifier of the input port included in the subsequent request message matches the stored identifier, and in response to termination of the iterations: forwarding by each input port, data destined for the corresponding output port. According to a fifth aspect, a computer implemented method for establishing a communication channel with one of a plurality of output ports, comprises: in an initial iteration: sending to each one of a plurality of output ports, a first instance of a request message, each respective request message including an identifier of the input port, receiving a grant message from an output port of the plurality of output ports, in each respective iteration of one or more iterations: in response to receiving the grant message in a preceding iteration, sending a subsequent instance of the request messages that includes the identifier, to the output port, in response to not receiving the grant message in the preceding iteration, sending a plurality of subsequent instances of the request message to the plurality of output ports, and in response to termination of the iterations: forwarding data to the output port.

According to a sixth aspect, a computer implemented method for establishing a communication channel with one of a plurality of input ports, comprising: in an initial iteration: receiving a plurality of first instances of request messages each including an identifier of an input port of a plurality of input ports that sent the respective request message, selecting one of the plurality of input ports, sending a grant message to the selected input port, storing the identifier of the selected input port included in the request message, in each respective iteration of one or more iterations: receiving a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message, checking that the identifier in the subsequent instance of the request message matches the stored identifier, in response to termination of the iterations: receiving data from the input port.

Each of the programs below may be provided on a non-transitory storage medium.

According to a seventh aspect, a computer program for establishing a plurality of communication channels, the computer program comprising program instructions which, when executed by at least one processor, cause the at least one processor to: in an initial iteration: send by the plurality of input ports, a plurality of first instances of a request message to the plurality of output ports, each respective request message including an identifier of the respective input port, send by each output port that selected an input port, a respective grant message to the selected input port, and storing the identifier of the selected input port, in each respective iteration of one or more iterations: send, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier of the input port, check by each corresponding output port that received the subsequent instance of the request message, that the identifier of the input port included in the subsequent request message matches the stored identifier, and in response to termination of the iterations: forward by each input port, data destined for the corresponding output port.

According to an eight aspect, a computer program for establishing a communication channel with one of a plurality of output ports, the computer program comprising program instructions which, when executed by at least one processor, cause the at least one processor to: in an initial iteration: send to each one of a plurality of output ports, a first instance of a request message, each respective request message including an identifier of the input port, receive a grant message from an output port of the plurality of output ports, in each respective iteration of one or more iterations: in response to receiving the grant message in a preceding iteration, send a subsequent instance of the request messages that includes the identifier, to the output port, in response to not receiving the grant message in the preceding iteration, send a plurality of subsequent instances of the request message to the plurality of output ports, and in response to termination of the iterations: forward data to the output port.

According to a ninth aspect, a computer program for establishing a communication channel with one of a plurality of input ports, the computer program comprising program instructions which, when executed by at least one processor, cause the at least one processor to: in an initial iteration: receive a plurality of first instances of request messages each including an identifier of an input port of a plurality of input ports that sent the respective request message, select one of the plurality of input ports, send a grant message to the selected input port, store the identifier of the selected input port included in the request message, in each respective iteration of one or more iterations: receive a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message, check that the identifier in the subsequent instance of the request message matches the stored identifier, in response to termination of the iterations: receive data from the input port.

Output ports may operate independent of one another.

Input ports may operate independently of one another.

Implementations described herein use 2 steps per iteration and 3 steps at the last iteration, in contrast to prior approaches that use 3 steps per iteration, for all iterations. The decrease in iterations reduces traffic between the input and output ports over the switching fabric, which improves performance of the switching fabric and/or of the input and output ports.

Communication channels are established faster and/or with fewer messages between the input and output ports, by sending the subsequent instance of the request messages instead of an accept message. In a further implementation form of the first, fourth, and seventh aspects, further comprising: defining by each input port that received the grant message, a match with the corresponding output port to which the subsequent instance of the request message was sent, in response to the checking by each corresponding output port, defining by each corresponding output port that received the subsequent instance of the request message, a match with the input port that sent the subsequent instance of the request message, wherein forwarding comprises forwarding by each input port matched to the corresponding output port, data destined for the corresponding output port.

The match is defined based on the checking of the identifier instead of an accept message, which saves on sending the accept message.

In a further implementation form of the first, fourth, and seventh aspects, the plurality of input ports and the plurality of output ports are network ports, the communication channels are established over a network, the data comprises network traffic, and the network traffic is routed from each input port to each matched output port.

Network traffic and/or time to setup the communication channels is reduced by avoiding sending the accept messages.

In a further implementation form of the first, fourth, and seventh aspects, each input port is associated with a queue of network packets with destination addresses of different output ports, and the plurality of output ports to which the plurality of first instances of the request message are sent by each input port have addresses matching the destination addresses of the network packets.

Network packets are sent earlier.

In a further implementation form of the first, fourth, and seventh aspects, the plurality of input ports are of a plurality of clients and the plurality of output ports are of a plurality of servers, where clients request servers.

Connections between clients and servers are established faster.

In a further implementation form of the first, fourth, and seventh aspects, wherein: in a preceding iteration: an input port of the plurality of input ports receives at least two grant messages from at least two output ports, and the input port selects one output port from the at least two output ports, in a subsequent iteration: the input port sends the subsequent instance of the request message to the selected one output port.

Two grants are handled by the input port.

In a further implementation form of the first, fourth, and seventh aspects, the input port sends the subsequent instance of the request message only to the selected one output port. An output port that does not receive the subsequent instance understands that the output port has not accepted its grant.

In a further implementation form of the first, fourth, and seventh aspects, the input port selects the one output port using a round robin scheme.

The round robin scheme prevents dominant output ports from being selected, and/or ensures a distribution for selection of the output ports.

In a further implementation form of the first, fourth, and seventh aspects, each respective input port sends the plurality of first instances of the request messages to output ports that are targets for communication with the respective input port.

Output ports that are not targets are not sent message, reducing the message traffic.

In a further implementation form of the first, fourth, and seventh aspects, each output port is configured for receiving request messages from at least two different input ports.

The output port can select from the different input ports.

In a further implementation form of the first, fourth, and seventh aspects, the output port selects a single input port from the plurality of input ports that sent request messages.

The non-selected input ports understands it has not been selected when no grant message is received.

In a further implementation form of the first, fourth, and seventh aspects, the output port selects the single input port using a round robin scheme.

In a further implementation form of the first, fourth, and seventh aspects, in the one or more iterations, input ports that did not receive grant message in the preceding iteration send a plurality of subsequent instances of the request messages to a plurality of output ports.

In a further implementation form of the first, fourth, and seventh aspects, in the one or more iterations, each input port that received at least one grant messages in the preceding iteration sends the subsequent instance of the request message only to one of the corresponding output ports that sent the grant message.

Sending only to the output port reduces the message traffic.

In a further implementation form of the first, fourth, and seventh aspects, in response to the match, the output port ignores additional request messages from other input ports, and does not send additional grant messages to the other input ports. The amount of message traffic is reduced.

In a further implementation form of the first, fourth, and seventh aspects, the one or more iterations terminate when at least one of the following is met: a predefined percentage of input ports are matched to output ports, a predefined number of input ports are matched to output ports, or a predefined number of iterations have elapsed.

Some input ports and output ports may remain unmatched. Placing a limit on iterations helps avoid endless loops.

In a further implementation form of the first, fourth, and seventh aspects, the at least one processor excludes sending an accept message from the input port to the corresponding output port for explicitly indicating acceptance of the grant.

Accept messages are avoided, reducing the number of messages sent and/or reducing time to establish the sessions.

In a further implementation form of the first, fourth, and seventh aspects, the plurality of input ports are 1-to-l matched to the plurality of output ports, and each input port only sends data to the matched output port.

One to one matching is efficient.

In a further implementation form of the second, fifth, and eighth aspects, the processor excludes sending an accept message to the output port for explicitly indicating acceptance of the grant.

In a further implementation form of the second, fifth, and eighth aspects, receiving the grant message comprises receiving a plurality of grant messages from at least two output ports of the plurality of output ports, and further comprising selecting one output port from the at least two output ports, wherein the substance instance of the request is sent to the selected one output port, and data is forwarded to the selected one output port.

In a further implementation form of the second, fifth, and eighth aspects, the input port is matched to the output port and unmatched to other output ports, and the output port is matched to the input port and unmatched to other input ports, and data is forward from the input port only to the matched output port.

In a further implementation form of the second, fifth, and eighth aspects, the input port is associated with a queue of network packets with destination addresses of different output ports, and the plurality of output ports to which the request messages are sent have addresses matching the destination addresses of the network packets. In a further implementation form of the third, sixth, ninth aspects, the input port that sent the subsequent instance of the request message is identified as the selected input port when the identifier in the subsequent instance of the request message matches the stored identifier.

In a further implementation form of the third, sixth, ninth aspects, further comprising: in response to the subsequent instance of the request message matching the stored identifier, ignoring additional request messages received from other input ports.

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the disclosure pertains. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments of the disclosure, exemplary methods and/or materials are described below. In case of conflict, the patent specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and are not intended to be necessarily limiting.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Some embodiments of the disclosure are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the disclosure. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the disclosure may be practiced.

FIG. 1 is a schematic of a Bipartite Graph, to help understand embodiments of the disclosure;

FIG. 2 is a sequence diagram for resolving the matching problem using an input PE and output PE based on the iSLIP and PIM approaches, to help understand some embodiments of the present disclosure;

FIG. 3 is a block diagram of components of a system for matching input ports to output ports, in accordance with some embodiments;

FIG. 4 is a flowchart of a method for establishing communication channels between input ports and output ports, in accordance with some embodiments;

FIG. 5 is a flowchart of a method for an input port for establishing a communication channel with one of multiple output ports, in accordance with some embodiments;

FIG. 6 is a flowchart of a method for an output port for establishing a communication channel with one of multiple input ports, in accordance with some embodiments; and FIG. 7 is a sequence diagram for matching input ports to output ports, in accordance with some embodiments.

DETAILED DESCRIPTION

An aspect of some embodiments relates to a device, a method, and/or a computer program for establishing communication channels between input ports and output ports. In an initial iteration, a processor instructs sending first instances of a request message by the input ports, to the plurality output ports. Each respective request message includes an identifier of the respective input port. The processor instructs sending by each output port that selected an input port, a respective grant message to the selected input port. Each input port stores the identifier of the selected input port. In each respective iteration of one or more iterations the processor instructs sending, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier of the input port. Each corresponding output port that received the subsequent instance of the request message checks that the identifier of the input port included in the subsequent request message matches the stored identifier. In response to termination of the iterations the processor instructs forwarding by each input port, data destined for the corresponding output port.

An aspect of some embodiments relates to a device, a method, and/or a computer program that includes and/or instructs an input port for establishing a communication channel with one of multiple output ports. A processor in communication with the input port instructs: in an initial iteration: sending to each one of the output ports, a first instance of a request message. Each respective request message includes an identifier of the input port. The input port receives a grant message from one or more of the output ports. In each respective iteration of one or more iterations: in response to receiving the grant message in a preceding iteration, the processor instructs sending a subsequent instance of the request messages that includes the identifier, to the output port. In response to not receiving the grant message in the preceding iteration, the processor instructs sending subsequent instances of the request message to the output ports. In response to termination of the iterations: the processor instructs forwarding data to the output port. An aspect of some embodiments relates to a device, a method, and/or a computer program that includes and/or instructs an output port for establishing a communication channel with one of multiple input ports. A processor in communication with the output port instructs: in an initial iteration: receiving first instances of request messages each including an identifier of an input port of the multiple input ports that sent the respective request message. The processor instructs selecting one of the input ports, sending a grant message to the selected input port, and storing the identifier of the selected input port included in the request message. In each respective iteration of one or more iterations: the processor instructs receiving a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message, and checking that the identifier in the subsequent instance of the request message matches the stored identifier. In response to termination of the iterations the processor instructs receiving data from the input port.

At least some implementations described herein address the technical problem of resolving matching in a Bipartite graph. Matching can be for example, in the field of network communications, for matching between input ports and outputs ports, in order to deliver traffic from the input ports to the output ports. Other examples of matching may be between applicants and jobs. At least some implementations described herein improve the technical field of switching, by resolving matching in a Bipartite graph.

A matching in a Bipartite Graph is a set of edges chosen in such a way that no two edges share an endpoint. A maximum matching is a matching of maximum size (maximum number of edges), therefore, if any edge is added to it, it is no longer a matching. There can be more than one maximum matchings for a given Bipartite Graph.

Rreference is now made to FIG. 1, which is a schematic of a Bipartite Graph 102, to help understand embodiments of the disclosure. A simple example with reference to applicants and jobs is provided to help the reader understand the concept. However, it is to be understood that the Bipartite Graph may be used for technical applications, for example, switching of packets between input and output ports over a switching fabric.

Circles 104 represents applicants and circles 106 represent jobs. Thin lines 108 between applicants 104 and jobs 106 represent demand by specific applicants to one or more specific jobs. It is noted that a certain applicant may be suited for one or more jobs. However, each applicant may only accept one job, and each job may only be filled by a single application. Thick lines 110 represent matching between applicants 104 and jobs 106. In this example, a maximum matching was found as all applicants have a match, as shown in graph 112 where each circle 104 is connected to a single circle 106 by a single thick line 110.

In another example, in the networking field, circles 104 represent input ports that have traffic destined to output ports marked as circles 106. Each input port has a dedicated queue for traffic to a specific output port. A thin line 108 from an input port to an output port represents the fact that the input port has traffic to be delivered to the corresponding output port, which means the corresponding queue is not empty. Thick lines 110 represent matching between input ports 104 and output ports 106.

Maximum matching is considered as NP-Hard problem and consumes significant amount of time to resolve (O(N³) where N is the number of ports). Therefore, multiple approaches were developed to find maximal matching. Maximal matching is the process of finding as many input/output pairs as possible within a time that is as short as possible.

Among maximal matching approaches, PIM and iSLIP approaches were developed, where iSLIP performs better than PIM in terms of average delay, for example, as described with reference to N. McKeown, "The iSLIP scheduling algorithm for input-queued switches" in lEEE/ACM Transactions on Networking, vol. 7, no. 2, pp. 188-201, April 1999, doi: 10.1109/90.769767, incorporated herein by reference in its entirety.

These approaches are implemented using a processing element (PE) for each input port and for each output port and communication channels from each input-PE to each output-PE in order to resolve the matching problem.

Reference is now made to FIG. 2, which is a sequence diagram 202 for resolving the matching problem using an input PE 204 and output PE 206 based on the iSLIP and PIM approaches, to help understand some embodiments of the present disclosure. iSLIP and PIM operates using multiple iterations where each iteration has 3 steps:

Step 1, Request 208: Each unmatched input sends a request to every output for which it has a queued cell. Step 1 requires a message from input PEs 204 to output Pes 206.

Step 2, Grant 210: If an unmatched output receives any requests, it grants to one on the requesting input ports. Step 2 requires a message from output PEs 206 to input PEs 204.

Step 3, Accept 212: If an input port receives a grant, it accepts one of the granting output ports. Step 3 requires a message from input PEs 204 to output Pes 206.

After one such iteration some input ports are matched with output ports. Several iterations are required to get as many matching ports as possible. PIM and iSLIP achieve very high throughput at high load (load means the amount of traffic waiting at the input port to be delivered to output ports). iSLIP and PIM differs between them on 2 things:

• The way ‘Grant’ is generated in an output port that receives multiple requests.

• The way ‘Accept’ is generated in an input port that receives multiple grants.

At least some implementations described herein address the technical problem of improving performance of matching between inputs and outputs, where each input is associated with one or more queues for one or more outputs. At least some implementations described herein improve the technical field of switching, by improving performance of matching between inputs and outputs, where each input is associated with one or more queues for one or more outputs. In high radix switches iSLIP and PIM require increased number of iterations to achieve as many matches between input and output ports as possible. Furthermore, communication between input and output processors, i.e. transferring request, grant and accept messages, may take longer than 1 clock cycle.

Therefore, the time it takes to converge the algorithm to high number of matching pairs may be longer than required.

The original iSLIP/PIM approaches have the following number of steps:

#Steps = 3 * N

Where N is the number of iterations used.

In contrast, at least some embodiments described herein address the aforementioned technical problem, and/or improve the aforementioned technical field, by providing performance that is the same or similar as the original iSLIP/PIM approaches, with 2 steps per iteration and 3 steps at the last iteration.

At least some embodiments described herein has the following number of steps: #Steps = 2 * (A - 1) + 3 = 2 * N + 1

Where N is the number of iterations used.

At least some embodiments described herein provide a reduction of N-l steps as compared to the original iSLIP/PIM approaches.

For high-radix switches where the communication between input and output processors require 2 clock cycles per step (one clock cycle for the delivery of the message to all processors and another clock cycle to lock the message in order to process it), at least some embodiments described herein provide performance which is the same or similar to the original iSLIP/PIM approaches, with 2*(N-1) fewer clock cycles. Before explaining at least one embodiment of the disclosure in detail, it is to be understood that the disclosure is not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. The disclosure is capable of other embodiments or of being practiced or carried out in various ways.

The present disclosure may be a system, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present disclosure.

The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing.

Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network.

The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present disclosure.

Aspects of the present disclosure are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the disclosure. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present disclosure. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

Reference is now made to FIG. 3, which is a block diagram of components of a system 300 for matching input ports 302 to output ports 304, in accordance with some embodiments. Reference is also made to FIG. 4, which is a flowchart of a method for establishing communication channels between input ports and output ports, in accordance with some embodiments. Reference is also made to FIG. 5, which is a flowchart of a method for an input port for establishing a communication channel with one of multiple output ports, in accordance with some embodiments. Reference is also made to FIG. 6, which is a flowchart of a method for an output port for establishing a communication channel with one of multiple input ports, in accordance with some embodiments. Reference is also made to FIG. 7, which is a sequence diagram 700 for matching input ports 702 to output ports 704, in accordance with some embodiments.

System 300 may implement the acts of the methods described with reference to FIGs. 4-7, as described herein.

Referring now back to FIG. 3, system 300 includes multiple input ports 302 and multiple output ports 304, connected by a switch 306.

Input ports 302 and/or output ports 304 may be implemented as, for example, virtual ports implemented in software, and/or physical ports implemented in hardware. Switch 306 may be implemented as, for example, a crossbar switch, switching fabric, and one or more networks (e.g., internet, a local area network, a virtual private network, a wireless network, a cellular network, and/or combinations of the aforementioned.

Each input port 302 is associated with an input processor 308 that generate request message and/or receives grant messages, as described herein.

Each output port 304 is associated with an output processor 310 that receives request message and/or generates grant messages, as described herein.

Optionally, a control processor(s) 370 is in communication with input ports 302 and/or output ports 304 and/or input processor(s) 308 and/or output processor(s) 310 and/or switch 306. For example, control processor(s) 370 provides centralized control and/or synchronization for matching the input ports 203 with the output ports 304.

In an example, in the network field using switch 306, the approach described herein for matching input ports 302 to output ports 304 is for delivery of traffic from the input ports 302 to the output ports 304. The matching as described herein may be done by control processor(s) 370 in communication with switch. Control processor(s) 370 may control delivery of traffic from input ports 302 to the matched output port 304 destinations

Input processor(s) 308 and/or output processor(s) 310 and/or control processor(s) 370 may be implemented as, for example, a software processor, a single processor per port, a single processor for multiple input ports and another single processor for multiple output ports, and a single processor for the input and output ports. Exemplary processor(s) 308 and/or 310 and/or 370 include: central processing unit(s) (CPU), graphics processing unit(s) (GPU), field programmable gate array(s) (FPGA), digital signal processor(s) (DSP), application specific integrated circuit(s) (ASIC), customized circuit(s), processors for interfacing with other units, and/or specialized hardware accelerators. Processor(s) may be implemented as a single processor, a multi-core processor, and/or a cluster of processors arranged for parallel processing (which may include homogenous and/or heterogeneous processor architectures).

Each processor 308 and/or 310 and/or 370 may be implemented entirely in hardware, and/or may be associated with a memory 312 storing code instructions for execution by the associated processor. Memory 312 may be implemented as, for example, a random access memory (RAM), dynamic random access memory (DRAM) and/or storage class memory (SCM), non-volatile memory, magnetic media, semiconductor memory devices, hard drive, removable storage, and optical media (e.g., DVD, CD-ROM).

Input processor(s) 308 and input port 302, with optional memory 312, may be arranged as an input device 314. Input device 314 may be a physical unit, and/or may be logically defined, and/or may be a concept without hardware and/or software definition. For example, input device 314 may be a computer, a router, and an executing process.

Output processor(s) 310 and input port 304, with optional memory 312, may be arranged as an output device 316. Output device 316 may be a physical unit, and/or may be logically defined, and/or may be a concept without hardware and/or software definition. For example, output device 316 may be a computer, a router, and an executing process.

Each input port 302 is associated with a data queue 318, which may be included in input device 314, for queueing data destined to one or more output ports 304, for example, packets. Data queued in data queue 318 may be generated by a data device 320, for example, a computer, a network, a sensor, a virtual device, a executing process, and a router.

Each output port 304 may be associated with a data device 322 that is a destination of the data stored in data queue 318. Data device 322 may be implemented as, for example, a computer, a network, a sensor, a virtual device, a executing process, and a router.

Each input port 302 and/or output port 304 may be associated with a switch interface 324 for connecting to switch 306. Switch interface 324 may be included in input device 314 and/or output device 316. Switch interface 324 may be implemented, as for example, one or more of, a bus interface for connecting to local busses, a network interface card, a wireless interface to connect to a wireless network, a physical interface, a virtual interface implemented in software, network communication software providing higher layers of network connectivity, and/or other implementations.

Input devices 314 and/or output devices 316 may be in communication with one or more user interfaces 326 that include a mechanism for a user to enter data and/or view data. Exemplary user interfaces 326 include, for example, one or more of, a touchscreen, a display, a keyboard, a mouse, and voice activated software using speakers and microphone.

Referring now back to FIG. 4, a flowchart of a method for establishing communication channels between input ports and output ports is presented. The features of the method described with reference to FIG. 4 may be implemented, for example, by a centralized processor controlling multiple input ports and/or multiple output ports, and/or by an independent processor for each of the input ports and/or output ports.

Features described with reference to 402 and 404 represent an initial iteration.

At 402, one or more of the input ports send a request message to the output ports. Each sending input port sends one or more request messages to one or more output ports. The initially sent request message is referred to herein as first instance of the request message. Each request message includes an identifier of the respective input port, for example, a network address of the sending input port, and/or other unique identifier of the sending input port.

The sending of request messages by multiple input ports may be synchronized, for example, triggered by a central clock and/or central processor, and/or triggered to occur every defined amount of time within a defined time interval. Alternatively, the sending of request messages by multiple input ports may be asynchronous, for example, each input port sends its own request messages according to its own schedule.

Optionally, each respective input port sends multiples first instances of the request messages to output ports that are targets for communication with the respective input port. For example, for a certain input port for which network packets are queued in a queue, the certain input port sends request messages to the different output ports which are destinations for the queued network packets.

Each output port is capable of receiving request messages from two or more different input ports.

When an output port receives multiple request messages from multiple input ports, the output port selects a single input port, for example, using a round robin scheme (e.g., to help spread out the selected input ports), random selection, according to the first received request message, or other approaches.

In an example, the input ports and the output ports are implemented as network ports, optionally of different devices (e.g., loT) and/or of multiple processes (e.g., applications) running on a common device. The request messages may be for establishing communication channels over a network. Data that is sent over the established communication channels may be network traffic that is routed from each input port to each matched output port. Each input port may be associated with a queue of network packets with destination addresses of different output ports. The output ports to which the first instances of the request message are sent by each input port may have addresses matching the destination addresses of the network packets.

In another example, the input ports are of clients and the output ports are of servers. Clients send the request message to the servers.

At 404, each output port that selected an input port sends a grant message to the selected input port.

Each output port that send the grant message stores the identifier of the selected input port to which the grant message was sent. At 406, each input port that received the grant message in a preceding iteration (or the initial iteration) sends a subsequent instance of the request message to the corresponding output port that sent the grant message. The subsequent instance of the request messages includes the same identifier of the input port that was sent in a preceding instance (or the first instance) of the request message.

Each input port that received the grant message defines a match with the corresponding output port to which the subsequent instance of the request message was sent.

Each input port that received the grant message in the preceding iteration (or the initial iteration) sends the subsequent instance of the request message only to the corresponding output port that sent the grant message. The input port sends a single subsequent instance of the request message to the output port that sent the grant message. Now additional request message are sent to other output ports by the input port that received the grant message.

In a preceding iteration, an input port of the may receive two or more grant messages from two or more different output ports. In such scenario, the input port selects one output port from the two or more output ports. Selection may be done, for example, using a round robin scheme, randomly, according to the first received grant message, and other approaches. In a subsequent iteration, the input port sends the subsequent instance of the request message to the single selected output port. The input port sends the subsequent instance of the request message only to the selected single output port. The input port does not send additional request message to the other output ports that sent grant messages but that were not selected.

At 408, each corresponding output port that received the subsequent instance of the request message checks that the identifier of the input port included in the subsequent request message matches the stored identifier.

In response to the checking by each corresponding output port, each corresponding output port that received the subsequent instance of the request message defines a match with the input port that sent the subsequent instance of the request message.

After an output port has defined a match with the input port, the output port ignores additional request messages from other input ports, and does not send additional grant messages to the other input ports.

At 410, features described with reference to 406 and 408 iterated in multiple iterations, until the iterations are terminated.

During the iterations, input ports that did not receive grant message in the preceding iteration send subsequent instances of the request messages to one or more output ports, in an attempt to obtain grant messages. The iterations terminate when one or more of the following conditions are met: a predefined percentage of input ports are matched to output ports, a predefined number of input ports are matched to output ports, and a predefined number of iterations have elapsed.

Optionally, an accept message is not sent from the input port to the corresponding output port for explicitly indicating acceptance of the grant. The subsequent request message sent during the next iteration serves at the accept message, thereby reducing the number of messages and the amount of time taken to match input ports to output ports in the multiple iterations.

At 412, each matched input port sends data destined for the corresponding output port. Each input port matched to the corresponding output port forwards data destined for the corresponding output port.

The approach described herein matches input ports in a 1-to-l manner to the output ports. Each input port only sends data to the matched output port.

Referring now back to FIG. 5, a flowchart of a method for an input port for establishing a communication channel with one of multiple output ports, is presented. The features described with reference to FIG. 5 may be implemented, for example, by a processor of the input port (e.g., loT device, client) operating independently, or by a central processor controlling multiple input ports and/or multiple output ports.

Features described with reference to 502-504 represent an initial iteration.

At 502, the input ports sends a first instance of a request message to one or more output ports to which communication sessions are to be established. Each request message includes an identifier of the input port, that uniquely identifies the input port from other input ports which may be attempting to establish communication session with the output ports.

In an example, the input port is associated with a queue of network packets with destination addresses of different output ports. The output ports to which the request messages are sent have addresses matching the destination addresses of the network packets.

At 504, the input port receives a grant message from one or more of the output ports to which the request message was sent.

When two or more grant messages are received from two or more output ports, the input port select one of the output ports. The subsequent instance of the request (as in 506) is sent to the selected output port, and data is forwarded to the selected output port (as in 512).

At 506, in response to receiving the grant message in a preceding iteration (or in the initial iteration), the input port sends a subsequent instance of the request messages that includes the identifier to the output port. The input port does not necessarily send an accept message to the output port for explicitly indicating acceptance of the grant. Sending of the subsequent instance of the request message replaces the accept message, saving time and/or number of transmitted messages for establishing the communication channel with the output port.

At 512, the input port forwards data to the output port.

The input port is matched to the output port that sent the grant message (selected message in the case of multiple grants) and unmatched to other output ports. The output port that sent the grant message (selected message in the case of multiple grants) is matched to the input port and unmatched to other input ports. The input port forwards data only to the matched output port.

At 508, alternatively to 504, no grant message is received by the input port.

At 510, features 502-508 are iterated in multiple iterations until a grant message is received.

In response to not receiving the grant message in the preceding iteration (or the initial iteration), the input port sends another set of subsequent instances of the request message to the output ports as in 502.

Referring now back to FIG. 6, a flowchart of a method for an output port for establishing a communication channel with one of multiple input ports, is presented. The features described with reference to FIG. 6 may be implemented, for example, by a processor of the output port (e.g., loT device, server) operating independently, or by a central processor controlling multiple input ports and/or multiple output ports.

Features described with reference to 602-604 represent an initial iteration.

At 602, the output port receives one or more first instances of request messages sent by one or more input ports. Each request message includes an identifier of the input port that uniquely identifies the sending input port from the other input ports that sent other request message.

In the case of multiple requests from multiple input ports, one of the input ports is selected by the output port.

At 604, the output port sends a grant message to the selected input port. The output port stores the identifier of the selected input port (to which the grant message was sent). The stored identifier is obtained from the request message.

At 606, the output receives a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message.

At 608, the output port checks that the identifier in the subsequent instance of the request message matches the stored identifier. The input port that sent the subsequent instance of the request message is identified as the selected input port when the identifier in the subsequent instance of the request message matches the stored identifier.

At 610, features 606-608 may be iterated in multiple iterations, until the output port finds a subsequent instance of the request message matching the stored identifier, and identifies the input port as a match for communication.

In response to the subsequent instance of the request message matching the stored identifier (i.e., a matching input port for communication is found), the output port ignores additional request messages received from other input ports.

At 612, in response to termination of the iterations, the output port receives data from the input port.

Referring now back to FIG. 7, a sequence diagram 700 for matching input ports 702 to output ports 704, is presented. Matching may be done by communication between input processor(s) in communication with input ports 702 and output processor(s) in communication with output ports 704, and/or by a control processor(s) in communication with input ports 702 and output ports 704.

Sequence diagram 700 illustrates that the number of steps for matching is reduced in comparison to the standard iSLIP/PIM approach, by the input port 702 that received a grant from an output port 704 responding with an implied ‘accept’ message, which is different than an explicit accept message in the standard iSLIP/PIM approach, using a subsequent request message of a next iteration. This saves the additional step a dedicated and explicit accept messages uses in the standard iSLIP/PIM approach. The input port that has been provided a grant by a certain output port generates another request message in the first step of the next iteration to the output port that granted its request, without sending additional request messages to other output ports that did not grant the request. The output port in return understands this additional request as being an implied accept message, which saves sending an additional explicit accept message. The output port stores locally an ID of the input port that it granted to. Therefore, in the grant step of the next iteration, if a request is received from the input port that has its ID stored (the one that was granted), then this is an indication to a match.

At 710, each unmatched input port generates requests to all relevant output ports, for example, to each output port for which the input port has a queued packet. A single input port may send message to no output ports, to a single output port, or to multiple output ports, for example, according to the queued packets.

At 712, the requests are sent from the input ports to the output ports, for example, synchronized by a central clock, controlled by a central controller, and/or in an asynchronous mode independently in which each input port sends its own requests independently from other input ports.

At 714, when an unmatched output port receives one or more requests, the output port grants the request to one of the requesting input ports. An ID indicative of the input port that has been granted its request is stored in association with the granting output port, for example, stored in a memory or other data storage device.

At 716, the output ports send the grants to the selected input ports.

710-716 may represent an initial first iteration.

At 718, the input port that received a grant generates another request message to the corresponding output port that provided the grant. The additional request message includes the ID of the input port. The input port send the additional request message to the output port that granted its previous request, and does not send the additional request message to other output ports (e.g., that did not grant its request). The additional request message may be sent only to the output port that granted its previous request. The input port sets its internal states to indicate a match to the output port that granted its request. Input ports that remain unmatched sends another request to every output for which it has a queued packet, as described with reference to 710.

At 720, the input ports send their request messages to the output ports.

At 722, if an unmatched output port receives a request from an input port that has an ID equal to the ID stored from the previous iteration, the output port sets its internal states to indicate a match with the input port. The output port subsequently ignores all other received requests and it does not generate grants to other input ports.

At 724, if an unmatched output port receives any other requests, it grants the request to one of the requesting input ports. In addition, the output port stores the ID of the input port it granted to.

726 and 728 are iterated as described with reference to 718, 720, 722, and 724, until a stop condition is met. For example, a maximum number of iterations is reached, and/or a percentage and/or number of input ports have been matched.

730, 732, and 734 represent a last iteration, as described with reference to 718, 720, 722, and 724.

At 738, the input port that received a grant may accept one of the granting output ports, by optionally sending an accept message. The accept message may be omitted. For example, if the list of matching input/output ports is provided or if the output ports do not need to know their matching input ports then the accept step in 738 is not required. The input ports established a match to output port and provide matching indications without the need for the output ports to be aware of this as there are no other iterations to follow.

Other systems, methods, features, and advantages of the present disclosure will be or become apparent to one with skill in the art upon examination of the following drawings and detailed description. It is intended that all such additional systems, methods, features, and advantages be included within this description, be within the scope of the present disclosure, and be protected by the accompanying claims.

The descriptions of the various embodiments of the present disclosure have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

It is expected that during the life of a patent maturing from this application many relevant input ports, output ports, and switches will be developed and the scope of the terms input port, output port, and switch, are intended to include all such new technologies a priori.

As used herein the term “about” refers to ± 10 %.

The terms "comprises", "comprising", "includes", "including", “having” and their conjugates mean "including but not limited to". This term encompasses the terms "consisting of' and "consisting essentially of'.

The phrase "consisting essentially of means that the composition or method may include additional ingredients and/or steps, but only if the additional ingredients and/or steps do not materially alter the basic and novel characteristics of the claimed composition or method.

As used herein, the singular form "a", "an" and "the" include plural references unless the context clearly dictates otherwise. For example, the term "a compound" or "at least one compound" may include a plurality of compounds, including mixtures thereof.

The word “exemplary” is used herein to mean “serving as an example, instance or illustration”. Any embodiment described as “exemplary” is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments. The word “optionally” is used herein to mean “is provided in some embodiments and not provided in other embodiments”. Any particular embodiment of the disclosure may include a plurality of “optional” features unless such features conflict.

Throughout this application, various embodiments of this disclosure may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of the disclosure. Accordingly, the description of a range should be considered to have specifically disclosed all the possible subranges as well as individual numerical values within that range. For example, description of a range such as from 1 to 6 should be considered to have specifically disclosed subranges such as from 1 to 3, from 1 to 4, from 1 to 5, from 2 to 4, from 2 to 6, from 3 to 6 etc., as well as individual numbers within that range, for example, 1, 2, 3, 4, 5, and 6. This applies regardless of the breadth of the range.

Whenever a numerical range is indicated herein, it is meant to include any cited numeral (fractional or integral) within the indicated range. The phrases “ranging/ranges between” a first indicate number and a second indicate number and “ranging/ranges from” a first indicate number “to” a second indicate number are used herein interchangeably and are meant to include the first and second indicated numbers and all the fractional and integral numerals therebetween.

It is appreciated that certain features of the disclosure, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the disclosure, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination or as suitable in any other described embodiment of the disclosure. Certain features described in the context of various embodiments are not to be considered essential features of those embodiments, unless the embodiment is inoperative without those elements.

It is the intent of the applicant(s) that all publications, patents and patent applications referred to in this specification are to be incorporated in their entirety by reference into the specification, as if each individual publication, patent or patent application was specifically and individually noted when referenced that it is to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention. To the extent that section headings are used, they should not be construed as necessarily limiting. In addition, any priority document(s) of this application is/are hereby incorporated herein by reference in its/their entirety.

Claims

WHAT IS CLAIMED IS:

1. A device (314, 316) for establishing a plurality of communication channels, comprising: at least one processor (370, 308, 310) in communication with a plurality of input ports

(302) and a plurality of output ports (304), configured for: in an initial iteration: sending by the plurality of input ports, a plurality of first instances of a request message (712) to the plurality of output ports, each respective request message including an identifier of the respective input port; sending by each output port that selected an input port, a respective grant message (716) to the selected input port, and storing the identifier of the selected input port; in each respective iteration of one or more iterations: sending, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message (720) that includes the identifier of the input port; checking by each corresponding output port that received the subsequent instance of the request message, that the identifier of the input port included in the subsequent request message matches the stored identifier; and in response to termination of the iterations: forwarding by each input port, data destined for the corresponding output port.

2. The device of claim 1, further comprising: defining by each input port that received the grant message, a match with the corresponding output port to which the subsequent instance of the request message was sent; in response to the checking by each corresponding output port, defining by each corresponding output port that received the subsequent instance of the request message, a match with the input port that sent the subsequent instance of the request message, wherein forwarding comprises forwarding by each input port matched to the corresponding output port, data destined for the corresponding output port.

3. The device of any of the preceding claims, wherein the plurality of input ports and the plurality of output ports are network ports, the communication channels are established over a network, the data comprises network traffic, and the network traffic is routed from each input port to each matched output port.

4. The device of claim 3, wherein each input port is associated with a queue of network packets with destination addresses of different output ports, and the plurality of output ports to which the plurality of first instances of the request message are sent by each input port have addresses matching the destination addresses of the network packets.

5. The device of any of the preceding claims, wherein the plurality of input ports are of a plurality of clients and the plurality of output ports are of a plurality of servers, where clients request servers.

6. The device of any of the preceding claims, wherein: in a preceding iteration: an input port of the plurality of input ports receives at least two grant messages from at least two output ports, and the input port selects one output port from the at least two output ports; in a subsequent iteration: the input port sends the subsequent instance of the request message to the selected one output port.

7. The device of claim 6, wherein the input port sends the subsequent instance of the request message only to the selected one output port.

8. The device of claim 6, wherein the input port selects the one output port using a round robin scheme.

9. The device of any of the preceding claims, wherein each respective input port sends the plurality of first instances of the request messages to output ports that are targets for communication with the respective input port.

10. The device of any of the preceding claims, wherein each output port is configured for receiving request messages from at least two different input ports.

11. The device of any of the preceding claims, wherein the output port selects a single input port from the plurality of input ports that sent request messages.

12. The device of claim 11, wherein the output port selects the single input port using a round robin scheme.

13. The device of any of the preceding claims, wherein in the one or more iterations, input ports that did not receive grant message in the preceding iteration send a plurality of subsequent instances of the request messages to a plurality of output ports.

14. The device of any of the preceding claims, wherein in the one or more iterations, each input port that received at least one grant messages in the preceding iteration sends the subsequent instance of the request message only to one of the corresponding output ports that sent the grant message.

15. The device of any of the preceding claims, wherein in response to the match, the output port ignores additional request messages from other input ports, and does not send additional grant messages to the other input ports.

16. The device of any of the preceding claims, wherein the one or more iterations terminate when at least one of the following is met: a predefined percentage of input ports are matched to output ports, a predefined number of input ports are matched to output ports, or a predefined number of iterations have elapsed.

17. The device of any of the preceding claims, wherein the at least one processor excludes sending an accept message from the input port to the corresponding output port for explicitly indicating acceptance of the grant.

18. The device of any of the preceding claims, wherein the plurality of input ports are 1-to- 1 matched to the plurality of output ports, and each input port only sends data to the matched output port.

19. A device (314) including an input port (302) for establishing a communication channel with one of a plurality of output ports (304), comprising: a processor (308) in communication with the input port, configured for: in an initial iteration: sending to each one of a plurality of output ports, a first instance of a request message, each respective request message including an identifier of the input port; receiving a grant message from an output port of the plurality of output ports; in each respective iteration of one or more iterations: in response to receiving the grant message in a preceding iteration, sending a subsequent instance of the request messages that includes the identifier, to the output port; in response to not receiving the grant message in the preceding iteration, sending a plurality of subsequent instances of the request message to the plurality of output ports; and in response to termination of the iterations: forwarding data to the output port.

20. The device of claim 19, wherein the processor excludes sending an accept message to the output port for explicitly indicating acceptance of the grant.

21. The device of claims 19 or 20, wherein receiving the grant message comprises receiving a plurality of grant messages from at least two output ports of the plurality of output ports, and further comprising selecting one output port from the at least two output ports, wherein the substance instance of the request is sent to the selected one output port, and data is forwarded to the selected one output port.

22. The device of any of claims 19-21, wherein the input port is matched to the output port and unmatched to other output ports, and the output port is matched to the input port and unmatched to other input ports, and data is forward from the input port only to the matched output port.

23. The device of any of claims 19-22, wherein the input port is associated with a queue of network packets with destination addresses of different output ports, and the plurality of output ports to which the request messages are sent have addresses matching the destination addresses of the network packets.

24. A device (316) including an output port (304) for establishing a communication channel with one of a plurality of input ports (302), comprising: a processor (310) in communication with the output port, configured for: in an initial iteration: receiving a plurality of first instances of request messages each including an identifier of an input port of a plurality of input ports that sent the respective request message; selecting one of the plurality of input ports; sending a grant message to the selected input port; storing the identifier of the selected input port included in the request message; in each respective iteration of one or more iterations: receiving a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message; checking that the identifier in the subsequent instance of the request message matches the stored identifier; in response to termination of the iterations: receiving data from the input port.

25. The device of claim 24, wherein the input port that sent the subsequent instance of the request message is identified as the selected input port when the identifier in the subsequent instance of the request message matches the stored identifier.

26. The device of claim 24 or claim 25, further comprising: in response to the subsequent instance of the request message matching the stored identifier, ignoring additional request messages received from other input ports.

27. A computer implemented method for establishing a plurality of communication channels, comprising: in an initial iteration: sending by the plurality of input ports, a plurality of first instances of a request message to the plurality of output ports, each respective request message including an identifier of the respective input port (402); sending by each output port that selected an input port, a respective grant message to the selected input port, and storing the identifier of the selected input port (404); in each respective iteration of one or more iterations (410): sending, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier of the input port (406); checking by each corresponding output port that received the subsequent instance of the request message, that the identifier of the input port included in the subsequent request message matches the stored identifier (408); and in response to termination of the iterations: forwarding by each input port, data destined for the corresponding output port (412).

28. A computer implemented method for establishing a communication channel with one of a plurality of output ports, comprising: in an initial iteration: sending to each one of a plurality of output ports, a first instance of a request message, each respective request message including an identifier of the input port (502); receiving a grant message from an output port of the plurality of output ports (504); in each respective iteration of one or more iterations (510): in response to receiving the grant message in a preceding iteration, sending a subsequent instance of the request messages that includes the identifier, to the output port (506); in response to not receiving the grant message in the preceding iteration, sending a plurality of subsequent instances of the request message to the plurality of output ports (508); and in response to termination of the iterations: forwarding data to the output port (512).

29. A computer implemented method for establishing a communication channel with one of a plurality of input ports, comprising: in an initial iteration: receiving a plurality of first instances of request messages each including an identifier of an input port of a plurality of input ports that sent the respective request message (602); selecting one of the plurality of input ports; sending a grant message to the selected input port (604); storing the identifier of the selected input port included in the request message; in each respective iteration of one or more iterations (610): receiving a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message (606); checking that the identifier in the subsequent instance of the request message matches the stored identifier (608); in response to termination of the iterations: receiving data from the input port (612).

30. A computer program for establishing a plurality of communication channels, the computer program comprising program instructions which, when executed by at least one processor, cause the at least one processor to: in an initial iteration: send by the plurality of input ports, a plurality of first instances of a request message to the plurality of output ports, each respective request message including an identifier of the respective input port; send by each output port that selected an input port, a respective grant message to the selected input port, and storing the identifier of the selected input port; in each respective iteration of one or more iterations: send, by each input port that received the grant message in a preceding iteration to the corresponding output port that sent the grant message, a subsequent instance of the request message that includes the identifier of the input port; check by each corresponding output port that received the subsequent instance of the request message, that the identifier of the input port included in the subsequent request message matches the stored identifier; and in response to termination of the iterations: forward by each input port, data destined for the corresponding output port.

31. A computer program for establishing a communication channel with one of a plurality of output ports, the computer program comprising program instructions which, when executed by at least one processor, cause the at least one processor to: in an initial iteration: send to each one of a plurality of output ports, a first instance of a request message, each respective request message including an identifier of the input port; receive a grant message from an output port of the plurality of output ports; in each respective iteration of one or more iterations: in response to receiving the grant message in a preceding iteration, send a subsequent instance of the request messages that includes the identifier, to the output port; in response to not receiving the grant message in the preceding iteration, send a plurality of subsequent instances of the request message to the plurality of output ports; and in response to termination of the iterations: forward data to the output port.

32. A computer program for establishing a communication channel with one of a plurality of input ports, the computer program comprising program instructions which, when executed by at least one processor, cause the at least one processor to: in an initial iteration: receive a plurality of first instances of request messages each including an identifier of an input port of a plurality of input ports that sent the respective request message; select one of the plurality of input ports; send a grant message to the selected input port; store the identifier of the selected input port included in the request message; in each respective iteration of one or more iterations: receive a subsequent instance of the request message including an identifier of the input port that sent the subsequent instance of the request message; check that the identifier in the subsequent instance of the request message matches the stored identifier; in response to termination of the iterations: receive data from the input port.