WO2002093843A1

WO2002093843A1 - Router

Info

Publication number: WO2002093843A1
Application number: PCT/GB2001/002155
Authority: WO
Inventors: Robert Walter Alister Scarr; Trevor James Hall; Martin H. George; Timothy David Wilkinson; Michael Anthony Hands; Richard Hoptroff; William Arden Crossland
Original assignee: Opera Systems Limited
Priority date: 2001-05-14
Filing date: 2001-05-14
Publication date: 2002-11-21

Abstract

The invention discloses a packet routing architecture consisting of an input packet handler, a core switch and an output packet handler. The input packet handler translates the incoming address format into a form suitable for the fast operation of the core switch and segments the packet to a length suited to the core switch. The core switch consists of three main parts; an input alignment part, an optical interconnect and an electrical fan-out. The optical interconnect may involve optical fan-out or a one-to-one array of connections. The output packet handler reconstitutes the packet into its original (incoming) format. The efficient operation of the electrical fan-in part is achieved by phasing the start of the incoming packets and the electrical fan-in part contains the storage means to provide the necessary queuing for outgoing packets. The novel and inventive features of this are the architecture as a whole, the method of phasing packets, the organisation of the electrical fan-in circuits, and the use of Sectorised Orthogonal Transfer (SOT).

Description

NETWORK ROUTER WITH OPTICAL CORE SWITCH INTRODUCTION

This invention is concerned with routers, especially those for use in digital communication networks.

Digital communication networks, for example the Internet, consist of a many data channels interconnected by "routers". These routers route incoming data packets to their destination according to the "address header" attached to the data packet. Routing many packets between a large number of channels at high speed is difficult and expensive. This invention relates to a design for a packet router and in particular the "core switch" part of the router (see Figure 1) that enables higher throughput of data at lower cost than with existing technology. Moreover, the invention allows the core switches as described here to be interconnected to produce larger size routers.

In the past, the need for faster routers has been tackled by purely electronic means. However, this makes the router difficult to scale, since the connection of N inputs to N possible outputs requires an N² matrix of cross-points or cross-connections which, because of unwanted coupling between unconnected points (i.e. crosstalk), becomes more difficult to achieve as N increases. The invention deals with the problem in quite a different way by making use of the fact that there is no cross coupling between light beams in free space or any other suitable optical medium. More specifically, the router's required ability to cross- connect is achieved by converting the N electrical signals to light signals. These light signals are divided into F groups, called "sectors" and fanned-out F times. The N outputs from each set of F sectors is transmitted, optically to F receiving sectors each of which contains N detectors and hence may receive the totality of the input information. This information which is transmitted serially is in the form of packets and these packets are phased so that only the start of one of the N possible packets is received by the appropriate detector at any one time. Circuitry associated with each detector reads the header and retains or discards the packet according to whether its address corresponds to the address of the receiving sector. The phasing of the packets ensures that the electrical processing that takes place on their receipt is more evenly spaced in time than would be in the case if their starts were sent simultaneously or at random. The retained packets are then stored and sent through to the output channel to which it is addressed when that channel becomes free.

SUMMARY OF THE INVENTION

According to one aspect of the present invention there is provided a method of routing data in a packetised form between a plurality of incoming links and a plurality of outgoing links, including the conversion of the address data in the packet headers into a reduced form suited to the fast connection of packets by a core switch. Whereby all incoming data is available for a selected output link and including the segmentation of packets into sub-packets of a length suited to the fast transfer of packets by the core switch. The core switch includes means to phase the packets such that the start of a sub-packet is allocated a specific time slot in a multiplex and the reduced form of address is added to the sub-packet to facilitate its routing through the core switch. The optical transfer of the sub-packet is in serial form to optical detectors coupled to an electronic output unit. The electronic output unit contains means for converting the sub-packets from serial form to parallel form and transferring them to a memory store. The sub-packets are held in the memory store until the outgoing link for which they are destined is free of traffic. When this is so, the memory store is read out and the sub-packets are transformed back to serial form. The reduced header is removed and complete packets are reassembled before transmission on an outgoing link.

According to another aspect of the present invention there is provided an apparatus in which there are N replications of the electronic output units each unit being called a sector and providing output to only l/F th of the output links. Optical transfer means are provided by an F- fold replication of the complete input data to each of the F sectors, each off which said sectors ignores the data not wanted by it .

According to a third aspect of the present invention there is provided an apparatus in which there are F replications or sectors of an electronic input unit and F replications or sectors of an electronic output unit, each input and output unit being divided into F sub-sectors with optical or electrical means for orthogonally connecting sub-sectors of input units to sub-sectors of output units, such that a sub-sector of an input unit with coordinates a,b is connected to an output unit sub-sector b,a wherein the first coordinate refers to the sector and the second to the sub-sector. The means for disregarding at each input unit sub-sector packets which are not intended for the output sub-sector to which it is connected and means for storing within one output sector all the packets received by its own sub-sectors until such time as the output link to which they are addressed is free to transmit them.

According to a fourth aspect of the present invention there is provided a packet router in which a multiplicity of core switches are interconnected as modules to make a larger router, means for carrying the reduced form of addressing and sub-packeting over several apparatus as in claims 1,2 and 3 in cascade. BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the invention are now described, though by way of illustration only, with reference to the accompanying diagrammatic drawings in which:

Figure 1 shows a packet router of the invention;

Figure 2 shows a block schematic of the fan-out version of the core switch of the router of Figure 1;

Figure 3 shows a block schematic of the sectorised orthogonal transfer (SOT) version of the router of Figure

1;

Figure 4 shows the principle of the use of straight optical fan-out (SOFO) with electrical fan-in;

Figure 5 shows the principle of the use of the alternative sectorised orthogonal transfer (SOT) ;

Figure 6 shows a phasing diagram for serial packet transmission through a cross connect;

Figure 7 shows a schematic view of optical fan-out, with multiple image function;

Figure 8 fan-out and multiple imaging using a diffraction grating;

Figure 9 shows optical fan-out based on a Fresnel hologram;

Figure 10 shows optical fan-out effected using a beam- splitter; Figure 11 shows a functional block diagram of the output electronics; and,

Figure 12 shows a schematic of per sector electrical fan-in circuitry.

DESCRIPTION OF PARTICULAR EMBODIMENT

Figure 1 shows a block schematic of the module design. It consists of an input packer handler, a core switch and output packet handler. The input packet handler performs two main functions:

(a) It receives packets routed according to any one of a number of standard protocols (e.g. IP (Internet Protocol) , Ethernet, ATM (Asynchronous Transfer Mode) or frame relay) . Associated with these packet handlers are look-up tables which translate the packet header information into a local address in the form of a header. This address contains fields that identify the route to be taken though the core switch. Compared with the packet header, these address fields are very short, making for fast route determination.

(b) The packet is then segmented into a number of octets, PS, which are chosen for optimal core switch size/performance. The value of PS will be much less than the maximum IP packet length and might be of the same order as an ATM packet (i.e. PS = 53 octets) .

There are number of possible architectures for the core switch, only two of which are described here. They all have the same overall functionality but differ in the detail of the design. The switch is based on a "broadcast" or "the generalised knockout principle" (see M.J Carol & M.G. Hluchy. "The knockout switch principles and performance." Proc. 12th Conference on Local computing networks, October 1987. pp 16-22). Figure 2 shows one of the embodiments based on straight optical fan-out (SOFO) and Figure 3 shows the other based on sectorised orthogonal transfer (SOT) .

The principle of Figure 2 is amplified in Figure 4 for a particular example of 64 inputs and an optical fan-out of 4. In general the inputs are copied F times to F output sectors. F is the fan-out which is best achieved optically avoiding the cross coupling problems associated with an all electronic solution. Each of the F sectors receives the complete set of input packets but ignores/discards those not intended for it . Those that are wanted are written to a per sector store which stores packet segments and is organised to act as a queue that holds those packet segments until their destination ports are free. For example with N = 64 (Figure 4) , a fan-out of 4 with 4 sectors each having 16 output ports, the electronics are then performing a fan-in of 64 to 16, i.e. a fan-in of 4.

With sectorised orthogonal transfer (SOT) , Figure 3 and as amplified in Figure 5, the input is first divided into sectors and then sub-sectors. The input for one sector is broadcast to all sub-sectors but is only selected by a given sub-sector if that sub-sector is "opposite" the relevant output sub-sector. Sub-sectors are arranged in an orthogonal array and there is a direct optical connection, or flip-chip bonding, between sub-sectors on the input and output planes with common storage per sector on the output plane. SOT needs less inter-plane connections than SOFO but is more sensitive to traffic patterns and hence may lose more packets. The concept of orthogonal transfer as described here has been shown in previous embodiments although not perhaps recognized as such. In US Patent No. 4,470,139 (E.A. Munter) "Switching networks for use in time division multiplex systems" and in a Canadian Patent (E. Beshai & E.A. Munter) "Rotating Access ATM-STM Packet Switch."; the input is connected to the output via sub- sectors and stored there as described above but there is only one path per sub-sector (i.e. the is no traffic grouping with the consequent advantage of common sector storage) and the crossover problem between input and output connections is not solved as it is here by the use of an optical connection or flip chip bonding. With SOT the number of optical transfer paths between sub-sectors will generally be greater than the number of input ports divided by the number of sub-sectors. This is known as "spatial speed-up" and prevents switch blocking.

If the incoming data rate per packet is g bit/s then the incoming clock interval is 1/g = ti sees. Each of the N incoming packets is allocated a time slot modulo N and of duration ti - this is done to avoid store contention problems on fan-in. Many packets are transferred in parallel but for a specific incoming packet transfer is only allowed to start transfer when its time slot occurs. Hence the input packet assembly buffers must be at least N bits per packet to achieve the desired phasing (see Figure

6) . Further segmentation into sub-segments of T = 8*PS

(l+OH)/W bits takes place at this point, for the definition of W see the discussion on electrical fan-in below and OH represents the local addressing over head plus stuffing bits. T is called the "tranche size". The local address is added to the first of the sub-segments and one or more stuffing bits are added between each sub-segment. If a packet is present on a given input, its first sub-segment will start transmission in its time slot in serial form from the optical transmitter to the input detectors of the fan-in block.

There are a number of existing technologies for providing the optical interconnection and described hereunder are some of them; they form part of an overall architecture which is believed to be novel. Figure 7 provides a no -technology dependent view of the function of an optical fan-out architecture. The plane labelled Optical Input Plane (OPI) contains point sources organised as a one or two dimensional array and could be either;

(a) An image of spots transported to that plane from non-local emitters via an optical system which reduces the spatial lateral distance between the individual emitters.

(b) A number of spatially distributed optical emitters, which could be organised is a one or two dimensional array.

The SOFO design fits into the optical fan-out section of the core switch (Figure 2) and requires that the array of point sources in the (OIP) are copied to multiple copies of the array displaced spatially and non-overlapping at the Optical Receiver Plane (ORP) , as labelled in Figure 8. The construction of each copied array may be magnified positively or negatively in comparison to the OIP in order that the size of the point sources matches the size of the individual detectors in the ORP. It is possible that the copied images may be copied without maintaining the same orientation as the process of fan-out may cause each copy to be "flipped" round its local axis. This would result in points PI..4 being ordered as P4..1, etc. This factor is an artefact of the optical system design and results as a consequence of different Optical paths for a split image. It is not claimed that the points within an individual copy are re-ordered amongst themselves other than through this flipping process, thus, a point in the array will maintain its neighbourhood.

There are a number of processes by which the light from each source in the array can be split into multiple copies of itself, including free-space optical components such as beam splitters, diffraction gratings, thin and thick holographic components. For low orders of fan-out F (less than eight in one-dimensional fan-out and less that sixty four in two dimensional fan-out) , it may be feasible to use waveguide light splitting devices. The latter includes passive waveguide structures that split the light propagating along the input waveguide into more than one output waveguide such as those constructed in integrated passive waveguide or optical fibre technologies. A fibre splitter implemented by Grimes et al (see "Polymer waveguide photonic switch" Optical Engineering, V.31, No. 10, October 1992, pp 2218-2224) allows the transfer of light from a large core diameter (1 mm) multi-mode plastic fibre to a bundle of fibres with a 200 micrometer diameter core. A perfluorinated ethylene propylene sheath is used to fix the multi-mode fibre and the fibre bundle in position.

The optical design of the waveguide based optical fan- out system would require additional optics in order to control the beam divergence and spot size of each of the point sources propagating from the OIP. The optics could be as simple as a single microlens designed to couple the light from one point source into one waveguide input channel. The waveguide would then confine the light to propagate along its channel and split according to the construction and placement of the waveguide splitter technology.

In the case of the holographic free space systems, it is adequate to image the points using a common-to-all microlens such that the resolvable points in the OIP plane are imaged to an overlapping point which illuminates a sufficient extent of the diffractive/holographic component (Figure 9) . This component is designed to control the splitting of the light into the multiple images and may require a lens to be used to image the multiple images to the ORP (as shown in Figure 9) . Alternatively, the diffractive/holographic component may itself incorporate an imaging function and image the light to the ORP (as shown in Figure 10) .

In the case of a beam splitter (BS) based fan-out system, each BS will split the light of the array into two identical arrays, in terms of their spatial/angular light distributions, but not necessarily in terms of the optical power split. A cascade of BS components (which may not be identical in their power splitting behaviour) will define the optical paths between the OIP and the ORP. Each copy of the OIP will follow one particular optical path through the BS network. As an example, consider Figure 10 where the sources at the OIP are imaged through a lens and travel as parallel beams through the BS network. The initial beam splitter (BS 1) splits the light into two paths such that 33% of the optical power travels straight through the beam splitter and out towards the ORP. The remaining 66% of the power is deflected to upwards and into BS2 which splits this light into two paths with 50% of the power travelling in each direction. One path leads directly to the ORP whilst the other first reflects from a mirror, which reflects all of the light on towards the ORP. The optical design shown here uses microlenses to collimate the light from the points in the OIP and it uses microlenses to image the beams through the beam splitter network. This example illustrates that BS can be used to perform multiple imaging and that, if desired, the optical power splitting performed by the beams splitters can be designed to allow an approximately even sharing of the optical power between copies of the input image .

It is not necessarily the aim of the multiple imaging optics to split the optical energy of a source in the OIP array evenly between its fanned-out points at the ORP. In all cases, the process used to control the multiple imaging of the OIP array to the ORP should aim to communicate the optical energy from a point source in the OIP to its corresponding receivers in the output plane. Any optical energy which is imaged to the OIP which does not arrive at its correct receiver area will be seen as optical crosstalk between channels in the switch. The spot size of each of the fan-out spots must be controlled by the optical system in order that the major proportion of its light will impinge on a single optical detector in the ORP.

The general organisation of the electrical fan-in is shown in Figures 11 and 12 and is described in the context of SOFO. (The operation for SOT is very similar except that the unwanted packet segments have been previously discarded.) For a specific sector the packet segments are detected by the optical receivers (Figure 2) and are loaded serially into shift registers and the local header examined. If "not for me" the packet is ignored and drops off the end of the shift register. The shift register length is W bits which is also the width of the sector queue store. When W bits are received these are transferred in parallel to the queue store. To cope with N incoming time slots, the sector store write time needs to be W/Ng sees. If this write time is not achievable an auxiliary fast buffer (Figure 11) can be added to provide a retiming function but can result in packets being discarded on the "knock-out" principle (Figure 12 does not contain this function) . Hence W can be chosen to match the speed capability of the storage technology. The purpose of the inter sub-segment stuffing bits is to allow the serial shifting to stop without loss of information while parallel read-out takes place from a shift register into the queue store. Part of the local address is the destination port number of the output and at each output port there is a queue of pointers. At the start of a new packet, the address of the queue store location assigned to it is put on the relevant pointer queue. The number of locations in the queue store per packet is T, the tranche size. Segment size, tranche size and W can be adjusted within limits to match the capability of the core switch - in particular the speed/size performance of the queue store can be optimised. Each output stream is assigned a time slot modulo N/F with read time available of N WF/Ng sees. The output process is the converse off the input, i.e. parallel read-out from the queue store with parallel read-in into a shift register, one per port. The stuffing bits are reinserted and serial read out takes place from the shift registers.

For a stand alone module, output can be into a packet re-assembler, which involves stripping off the stuffing and local address bits and reconstituting the full packet from packet segments in the form appropriate to its outgoing network protocol . When a module forms part of a larger switch and the output of a first stage module is the required input for a similar second stage module, then the local header can be designed to embrace multistage operation and no stripping is necessary at that point.

There are many ways in which core switches might be cascaded to make a larger router and any of the standard switch topologies e.g. delta, Clos, Benes networks can be used. A two-stage switching network based on an orthogonal transformation is shown in Figure 6 of "Highly parallel optics in ATM switching networks" (RWA Scarr, JR Collington, WA Crossland and MP Dames) IEE Proc. Optoeleotronics Vol 144, No2, April 1997 and may be of particular relevance in the current context.

Claims

Claim 1. A method of routing data in a packetised form between a plurality of incoming links and a plurality of outgoing links, including the conversion of the address data in the packet headers into a reduced form suited to the fast switching of packets by a core switch whereby all incoming data are available for selected output links and including the segmentation of packets into sub-packets of a length suited to the fast transfer of packets by the core switch, the said core switch including means to phase the packets such that the start of a sub-packet is allocated a specific time slot in a multiplex and means to add the reduced form of address to the sub-packet to facilitate its routing through the core switch, means for the optical transfer of the said sub-packet in serial form to optical detectors coupled to an electronic output unit, said electronic output unit containing means for converting the sub-packets from serial form to parallel form and transferring them to a memory store, means for holding sub- packets in the memory store until the outgoing link for which they are destined is free of traffic, means for reading out the memory store and transforming the sub- packets back to serial form, means for the removal of the reduced header and the reassembly of complete packets before transmission on an outgoing link.

Claim 2. A packet switching apparatus as in Claim 1, in which there are N input ports, M output ports (N less than, equal to, or greater than M) and F replications of the electronic output units each unit being a called a sector and providing output to only M/F of the output links, with optical transfer means providing an F-fold replication of the N input data streams to each of the F sectors^* each of which said sectors discards the data not destined for it, means for storing within said output sectors all the packets destined for the said sectors until such time as the output links to which they are addressed are free to transmit the said packets.

Claim 3. A packet switching apparatus as in claim 1, in which there are N input ports, M output ports (N less than, equal to, or greater than M) and F replications or sectors of an electronic input unit and F replications or sectors of an electronic output unit, each input and, output unit being divided into F sub-sectors, optical or electrical means for orthogonally connecting sub-sectors of input units to sub-sectors of output units such that a sub- sector of an input unit with coordinates a,b is connected to an output unit sub-sector b,a wherein the first coordinate refers to the sector and the second to the sub- sector, means for disregarding at each input unit sub- sector packets which are not intended, for the output sub- sector to which it is connected and means for storing within one output sector all the packets received by its own sub-sectors until such time as the output link to which the said packets are addressed is free to transmit the said packets .

Claim 4. A packet switching apparatus as in claim 3, in which the number of connections between input electronic units and output electronic units is greater than or equal to N the number of input ports.

Claim 5. A packet router in which a multiplicity of packet switches as in claims 1,2 and 3 are interconnected as modules to make a larger router, means for carrying the reduced form of addressing and packet segmentation as in Claim 1 over several apparatus as in Claims 1,2,3 and 4 in cascade.

Claim 6. A packet switching apparatus with two blocks of P, say, switches as in claims 2 or 3 and 4 with the first block having P output ports connected to P input ports of the second block wherein the connection means is an optical or electrical orthogonal transpose wherein the connections obey the rule that output port number h say on block j say of the first block of core switches is connected to input port number j on the on block h of the second block wherein h and j are any numbers in the range 1 to P.

Claim 7. Apparatus as in claims 2,3 and 4, in which the means of connection between the electronic input units and electronic output units are optical transmitters in the form of Vertical Cavity Semiconductor Lasers (VCSELs) connected, by any optical means to photo-receivers forming an integral part of a CMOS VLSI circuit .

Claim 8. Apparatus as in claim 3 and 4, in which flip chip bonding is the means of connection between the input electronic units and the output electronic units forming the input and output sectors respectively, means of realising said input and output electronic units singly or in combination in the form of semiconductor chips.

Claim 9. Apparatus using the method of Claim 1 and the packet switching apparatus of claim 2, in which for a specific sector the photo-receiver's outputs are read serially into shift registers where packet segments not addressed to the said specific sector are discarded, means in the relevant time slot of a multiplex for parallel read out of the content of said shift registers directly or indirectly into a memory store means for holding said packet segments in the said memory store until such time as they are free to be read out to the destination port of the packet switch.

Claim 10. Apparatus using the method of Claim 1 and the apparatus of claim 3, in which for a specific sub- sector the photo-receiver's outputs are read serially into shift registers, means for combining the outputs of sub- sectors into a combined, output for the sector, means in the relevant time slot of a multiplex for parallel read out of the content of said shift registers directly or indirectly into a memory store, and means for holding segments in the said memory store until such time as they are free to be read out to the destination port of the packet switch.