ROUTING METHOD FOR FAST PACKET SWITCHING SYSTEMS

    公开(公告)号:CA1326284C

    公开(公告)日:1994-01-18

    申请号:CA600310

    申请日:1989-05-19

    Inventor: MELEN RICCARDO

    Abstract: A fast packet switching system includes an interconnection network with a distributed control structure composed of multiple processing units which manage routing of calls at a virtual call level. Some of the processing units, each associated with a group of network inputs or outputs, store bandwidth occupancy data relevant to links between stages accessible from or to the inputs or outputs of the group and between those inputs or outputs and a central network stage providing a maximum number of alternative paths, the data being updated whenever a new call has been routed. When the routing of a new call is to be decided, the processing units associated with the input and output involved in the connection evaluate each possible routing, on the basis of the updated data which they store as to bandwidth occupancy, and according to the bandwidth requirements of the new call, so as to provide a partial cost function of the portion of each possible routing through the links in respect of which they hold bandwidth occupancy data. One of the units involved combines the partial cost functions for each complete routing, selects that providing the minimum cost function, and forwards the call on that routing.

    SWITCHING ELEMENT FOR SELF-ROUTING MULTISTAGE PACKET- SWITCHING INTERCONNECTION NETWORKS

    公开(公告)号:CA1280497C

    公开(公告)日:1991-02-19

    申请号:CA551920

    申请日:1987-11-16

    Abstract: A switching element for self-routing, multistage, packet-switching, interconnection networks which comprise: an input unit, composed of as many sections ( IMA, IMB) as there are elements inputs, each section comprising a FIFO memory (FIFA, FIFB) for packet buffering; a switch (SW) associated with a control unit (SCU) which, for each packet to be forwarded, sets up a requested connection for that packet between one input and one or more outputs of the element (ECP), based on a routing tag associated with each packet and comprising a first and a second portion relative to normal routing and to broadcasting in the different stages of the network (RC), and solves possible routing conflicts between packets simultaneously arriving at different inputs; and an output unit, composed of as many sections (RUO, RUl) as there are element outputs and performing the functions necessary for correct packet forwarding toward a destination. The control unit (SCU) of the switch (SW) is arranged to handle broadcasting of a packet independently of all other elements (ECP) in the same stage, to allow broadcasting to a number of destinations, not limited to a power of 2, (for an element with two inputs and two outputs) and cooperates with the memory (FIF) storing the packet to be broadcast in such a way that broadcasting does not give rise to internal blocking in the network (RC). The control unit (SCU) moreover solves routing conflicts to set an upper bound to packet residence time within the network.

Patent Agency Ranking