FIELD OF THE INVENTION

The present invention relates to a method of transmitting and/or receiving both foreground data packets and background data packets as a signal stream on a link between a first network interface and a second network interface, to a network adapter configured to perform aspects of the method, to a network node comprising such a network adapter, to a switch for performing the method, to a foreground data packet for use in the method, and to a computer program product storing computer executable instructions for implementing the method.

BACKGROUND TO THE INVENTION

Digital voice telephony was originally carried on Time Division Multiplexed

(TDM) networks, in which a communications link was formatted into a fixed number of "channels" each carrying 8000 bytes per second. The link carried a "frame" every 8000th of a second, containing one byte for each channel. The byte belonging to a particular channel was identified by its position in the frame. The system was "connection-oriented", with a call being connected by finding an appropriate route through the network and choosing a free channel on each link, and setting up each switch through which it passed to forward the bytes from the chosen channel on the incoming link to the chosen channel on the outgoing link. This work would be done once, when the call was connected, and the switches would then continue to pass the data through the system until the call was disconnected.

A switch therefore consisted of two distinct parts, a computer which ran software that handled the finding of routes and setting up of calls, and hardware (the switching fabric) which forwarded the bytes according to values in a routing table written by the computer.

ARPANET, the ancestor of the Internet, was developed to carry data messages between computers. The technology used for voice calls was inappropriate for this application because the data flow was intermittent, for instance a server would typically send several hundred bytes in reply to a request and then nothing until the next request had been received. Messages were carried in "packets", with each packet containing all the information needed to identify its destination and to establish the context on arrival. Routing of the packets was done by software in the computers; a computer receiving a packet would check whether it was addressed to one of its own processes and if not pass it on to another computer.

In this "connectionless" system there was no formal separation between the finding of a route and the forwarding of the data along that route. There were several reasons why that was more appropriate to the applications for which the first packet networks were used: forwarding of packets was done directly by the computer that ran the route-finding algorithms rather than by separate hardware; it was thought that often a packet would be an isolated piece of information rather than part of a conversation; and the memory required to keep information on individual calls was significant in the context of the very small amounts of memory in computers at that time. Note that the number of calls passing over a link in a TDM network is limited to the number of bytes that can be transmitted in one 8000th of a second, which in turn limits the amount of information the switch has to store, whereas there would be no such limit to the number of calls that could pass over a link on a packet network.

The above two technologies were referred to respectively as Synchronous

Transfer Mode (because the data rate on each call had to be synchronised with the frame rate in the network) and Packet Transfer Mode. In the late 1980s, the telecommunications industry began to standardise a new system which they called Asynchronous Transfer Mode (ATM), to carry both continuous media and packet data. This system uses the same connection-oriented switching model as TDM, but with the data being carried in "cells" consisting of 48 bytes of payload plus a small header, and the channel being identified by a number in the cell header instead of by its position in a frame. This frees the sender from the requirement to transmit 8000 bytes per second for as long as the call is connected, and cells can be transmitted at any rate, which is why it is described as "asynchronous".

The fixed cell size simplifies the design of the hardware that forwards the cells in a switch and also reduces the size of the header by removing the need to signal the size of the payload. However, several drawbacks have become apparent. Data packets must be divided into small pieces for transmission and reassembled at the receiving end, with up to 47 bytes of additional overhead being added to bring the size up to a whole number of cells. In the case of voice calls, the sender must collect enough samples to fill a cell before it can transmit, so there is an additional delay of about 6 milliseconds.

A major feature of ATM is the ability to negotiate Quality of Service (QoS) separately for each call. QoS is a measure of the service provided by the network, particularly (a) the rate at which data can be sent, (b) the maximum and minimum time for the data to get from the sender to the receiver, and (c) whether data might be discarded for lack of buffer space in the switches. On a TDM network, the data rate and propagation time are fixed and data will not be discarded; this is an appropriate service for voice calls. Packet networks provide a "best effort" service in which the sender can send data as fast as its link into the network will allow but no guarantees are made as to the propagation time because each packet has to queue for the output link at each switch and if the queue becomes too large the packet may be discarded; this is the kind of service for which the protocols such as TCP that are used for data transfer across packet networks are designed.

ATM networks offer several different types of service, including Constant Bit Rate (CBR) which provides similar QoS to TDM networks and Unspecified Bit Rate

(UBR) which provides a "best effort" service. For a CBR call the network allocates enough capacity to carry data at the requested rate, but if it is sent at a lower rate then, unlike a TDM network, the unused capacity can be used for other traffic. In practice, ATM switches are usually designed such that cells for all the different types of service queue for output links in the same way as packets on a packet network, but the queuing time for CBR cells is kept short by limiting the capacity allocated to

CBR cells (typically to about 80% of the capacity of each link) and giving CBR cells priority over other cells. With this regime, CBR cells on circuits with a high data rate also have to have priority over those on circuits with lower data rates, because the allowable queuing delay in a switch is approximately equal to the interval between cells on the circuit; this adds complexity to the switching fabric.

Initially, most access to the Internet was for file transfer and sending and receiving e-mails, which are the same applications for which ARPANET was developed; from the early 1990s it was also used for downloading web pages, which - A - is a similar process. Internet Protocol (IP) was therefore appropriate and became established as the protocol underlying the Internet (although often running on top of ATM) and also in "local area" networks (LANs), with equipment for the latter becoming commodity and therefore cheap.

Gradually, IP networks began to be used for other services such as radio, voice telephony (VoIP), CCTV, and television. These are services that need QoS, and various schemes to add QoS to IP, such as RSVP and MPLS, have been standardised but none has been widely deployed in the Internet. Moreover, for many of these services the requirement to include all the necessary addressing information in every packet results in very high overheads.

The connection-oriented model is more appropriate for such services, as it provides a simple way for guaranteed QoS to be negotiated. Media streams are often set up using Session Initiation Protocol (SIP), which is very similar to the call management processes in a connection-oriented network.

Much of the other Internet traffic would also benefit from the connection- oriented model; many of the data transfer protocols used in the Internet, including HTTP which is used to access web pages, run over TCP, which is a connection- oriented protocol, and the connection-oriented model offers a simple way of setting up a session between a client and a server.

The first local area network (LAN) technologies were mostly shared-media systems in which all of the traffic on a network "segment" reached all of the interfaces attached to it, and each interface selected the packets addressed to it and ignored the rest. A small network would be a single segment; larger networks would consist of several segments linked by bridges or routers. The most widely-deployed examples were probably Ethernet (IEEE 802.3) over co-axial cable and Token Ring (IEEE 802.5), but other technologies were also used, including buffer insertion rings in which the interfaces were connected in a loop, with a separate cable from each interface to the next, with packets arriving on one cable that were addressed to an interface further round the loop being forwarded (i.e. retransmitted) on the other. If an interface was in the middle of transmitting a packet of its own when a packet that needed forwarding arrived, the incoming packet was held in a FIFO buffer until the outgoing link became free; hence the buffer was "inserted" into the loop. For as long as there was anything in the buffer, the interface was not allowed to start transmitting another packet of its own.

More recently the dominant form for a wired LAN has been Ethernet over twisted pair, in which each interface has a separate connection to a hub or switch. Often the connection is by structured wiring, so the number of different pieces of equipment that can be connected to the network in a particular area is limited to the number of sockets that have been installed in that area. This limitation is likely to become more important as home networks become more common and users find they want to put several items of network-connected equipment in a room with only one or two outlets.

GB 2 162 022 A discloses a TDM data transmission system in which both circuit-switched and packet-switched connections can be set up. TDM channels are allocated to circuit-switched connections in the normal way, and the space in the frame that corresponds to unallocated channels is used to carry packet data. The problems with this are that the circuit-switched connections are fixed-bandwidth byte streams, and that the space occupied by channels which are connected but not carrying useful data is not available for packet data.

WO 2008/025620 Al discloses a system in which queues of packets of different priorities are multiplexed over a TDD point-to-point radio link, and lower- priority packets are fragmented to limit the extent to which they impede the higher- priority packets. In particular, the lower-priority packets are fragmented based on a current data capacity of the radio link. In this way, when the capacity is low, higher- priority data is not delayed by large packets of lower-priority data, and when the capacity is high, the lower priority packets are not fragmented unnecessarily. However, in this system, each and every fragment of a low-priority packet has a header which identifies its type and destination, irrespective of how many fragments are generated according to the current data capacity of the link.

Therefore it still remains a problem that the capacity of a link is not used as efficiently as possible. SUMMARY OF THE INVENTION

Certain aspects of the present invention are based on the insight that more efficient use can be made of available bandwidth on a link by utilising that part of the bandwidth that has been reserved for so-called foreground traffic but which is not being used at that moment in time for whatever reason. Thus foreground traffic uses its reserved bandwidth as needed, whilst so-called background traffic can be inserted into the reserved part of the signal stream when it is not being used. Background traffic may be fragmented without regard to the size of the spacing between foreground traffic, and there is no need to add a fragment header to a background data packet when it is interrupted by a foreground data packet.

In some embodiments the present invention relates to a method and apparatus for transmitting foreground traffic (e.g. time-critical data such as audio and/or video) on a link with guaranteed latency and throughput and making all remaining capacity available for background traffic (e.g. best-effort). The foreground traffic is connection-oriented, with resources allocated at call set-up time, and foreground packets are routed synchronously although the transmitter does not need to be synchronised with the network. Headers of foreground packets contain virtually no information other than the packet length, thus keeping overheads to a minimum and simplifying switching apparatus by removing the requirement to look up labels or addresses. Background traffic may be either connection-oriented or connectionless.

Interfaces may be chained together to form a linear segment along which data are passed with minimal delay per hop, and a segment may be connected to the network at both ends for added resilience.

According to at least some embodiments the present invention relates to a method of transmitting both foreground data packets and background data packets as a signal stream on a link between a first network interface and a second network interface, said foreground data packets having a higher priority than said background data packets, which method comprises the steps of:

(a) when foreground data packets are to be sent, assigning or allocating a point or points in said signal stream, each of which will serve as a starting point for a foreground data packet, said points being defined by their position relative to framing symbols; and

(b) said first network interface sending at least one foreground data packet with a header comprising an indication of the length of that foreground packet in said signal stream (which may be different in different packets of the same flow); and (c) all available space in said signal stream not occupied by foreground data packets or framing symbols being occupied by background data packets or, if there is no background data to be sent, idle data such as bytes or symbols; whereby said points are able to be allocated in said signal stream for transmission of said foreground data packets without regard to the position of said background data packets in said signal stream, and said first network interface is able to transmit said background data packets without adding fragment headers where they are interrupted by said foreground data packets. In certain aspects, foreground data is carried in packets which may be of any size, and virtually all space not used by foreground packets is available to background packets. Furthermore, in some aspects foreground packets are identified by their position in the data stream, thus avoiding the overhead of identifying the destination in the header, and background packets do not require fragment headers when interrupted by foreground data packets, thus further reducing the overheads.

In certain embodiments the first network interface sends each and every foreground data packet with a header as described in step (b). In other embodiments the first network interface sends fixed-length foreground packets (e.g. of a small size such as one, two and four bytes in length), which may have no header, in addition to at least one foreground data packet with a header. The lengths of such header-less packets would be specified in the same way as their starting points.

In some embodiments it may not be possible for the background data packets to use all space not allocated to foreground data packets or framing symbols. Also, the lengths of foreground packets may be constrained, for instance they may be required to be padded to a multiple of a certain number of bytes, or to be a fixed length. However, for most applications such a system will still make more efficient use of the capacity of the fibre than the currently-available alternatives.

Framing symbols may be symbols which serve as a reference point in the signal stream, or which are used within the process of conveying the signal stream on the link; examples are the non-data symbols which appear at the start and end of an Ethernet packet.

In certain embodiments the method further comprises the step of transmitting background data packets in space in said signal stream that is allocated to but not used by said foreground data packets. In this way, it is possible to use all of the spare available space in the signal stream, even if notionally it is reserved for foreground data packets, and up to 100% of the capacity of the link may be reserved for foreground data packets. Thus it is efficient to use the foreground data service for applications which on an ATM network would use the variable bit rate (VBR) service, as well as those that would use CBR; this reduces the complexity of the system.

The foreground data packets may comprise any data that has been assigned higher priority over any other data, the latter being carried by the background data packets. By way of example only, the foreground data packets may comprise time- critical media such as audio, video or VoIP data, and the background data packets may comprise data associated with web-browsing sessions, e-mail or ftp. However, it is to be noted that the division of what is foreground data and what is background data is entirely implementation specific, and the terms 'foreground' and 'background' are used herein to distinguish between data of different priorities.

It is envisaged that the step of assigning or allocating a point in the signal stream to serve as a starting point for each foreground data packet may be accomplished in various different ways. These ways include, but are not limited to: (i) agreement between the first and second network interfaces; and (ii) assignment by a remote control computer whose task it is to allocate the points (in other words to configure "slots maps") for some or all of the interfaces within a particular subnetwork, network or domain. In (i), the agreement may be either sender or receiver initiated, and in either case, 'agreement' may mean that there is negotiation between the two interfaces or that one interface simply declares the point or points in the signal stream to the other interface. In (ii), the remote control computer may perform a foreground call admission function for any foreground data packets that are to be sent by one or more interface within its domain. The control computer may maintain a central database of the or each slots map in use by each interface in its domain. When a network interface requests admission of a new foreground call, the remote control computer decides if the call is admissible and, if so, assigns the point(s) or slot(s) in the signal stream for foreground data packets of that call and informs the requesting interface and interfaces en route accordingly. Additionally or alternatively, there may be negotiation between the remote control computer and the requesting interface to decide the point(s) or slot(s) in the signal stream that is to be used.

The first and second network interfaces may be used in a wide variety of computing equipment. For example either of the first and second network interfaces may be part of a device such as a switch, or may be a single network interface on a piece of audiovisual or computing equipment.

In some embodiments the link is a point-to-point Ethernet link according to IEEE 802.3 and the signal stream is carried as MAC client data in Ethernet MAC frames according to 3.1 or 3.5 of IEEE 802.3. In other embodiments the link is a point-to-point Ethernet link according to IEEE 802.3 and the signal stream is carried in "jumbo" Ethernet frames. In yet other embodiments, the link is a stream of packets on an Ethernet network. In any such embodiments the Ethernet link may use twistedpair cable or fibre optic cable for example, and the Ethernet link may be a transparent point-to-point service on a metropolitan or wide-area network (MAN or WAN) for example.

In some embodiments the signal stream may be carried over SDH/SONET or NG-SDH.

In other embodiments the signal stream may be carried over a fibre optic link.

In certain aspects step (b) comprises coding said length with a number of bits in said header, said number being variable such that a number of bits is used that is sufficient to indicate said length, whereby the length of said header is proportional to said length of said foreground data packet. It should be noted that by coding with bits the length of the header is not linearly proportional to the length of the foreground data packet; rather it is proportional to the logarithm of that length. In certain aspects this is achieved by coding the length with a small header (e.g. one byte) that has a number of bits (e.g. four) available to code the length. If the foreground data packet is longer than can be coded with one header, one or more extra header is used until just enough bits are available to code the length. It will be appreciated that the number of bits available per header to code length will determine how many headers, and therefore how many bits are sufficient.

One particular advantage of this is that the overhead caused by headers varies with the length of each foreground data packet. In the extreme, when the foreground packet length is zero (for whatever reason) whilst resources are still reserved for that connection, only one small header (e.g. one byte) is needed to signal this along the route even though the sender may have previously been transmitting foreground data packets of the maximum agreed length which could require two, three, four or more headers to code. In this way extra capacity is freed when the foreground data packets are not using the maximum packet size that was agreed during set up of the connection.

In some embodiments, the foreground packet header format provides support for a 1-byte header for packets up to 15 bytes long, 2-byte up to 255 bytes long, and 3-byte up to 4095 bytes long, so the overhead is small even for very short packets. Usually the number of slots or points allocated will be slightly more than the number of packets to be sent, and a zero-length packet (occupying just one byte) is sent when the source has no data available.

In certain embodiments, said first network interface stores foreground data packets awaiting transmission in a foreground buffer and background data packets awaiting transmission in a background buffer, the method further comprising the step of upon transmission of said header associated with said foreground data packet, creating a gap in said signal stream before transmitting the remainder of said foreground data packet, whereby said gap provides time for said first network interface to read the length of said foreground packet from said header to determine whether to read data from said foreground buffer or said background buffer for transmission in the remainder of the space allocated to said foreground data packet. In this way the foreground data packets can be of variable length, and as their length varies, any space reserved for them that is not used can be utilised to send background data packets. For example, there may be no data available to transmit in foreground packets, even though resources remain reserved all the way along the route; the foreground header enables each network interface to realise this and the gap allows time for the background buffer to be read and any waiting data to be sent in the space reserved for that foreground packet. In certain embodiments the foreground buffer comprises a circular buffer and the background buffer comprises a FIFO buffer.

In other aspects the method further comprises the step of using said gap to transmit data of a different foreground packet or data of a background data packet. In this way the capacity of the link can be fully utilised whilst processing data efficiently within the network interface.

In some embodiments, step (a) takes place as part of establishment of a connection between said first and second network interfaces for transmission of said foreground data packets, the method further comprising the step of said second network interface storing in memory a receive map representing the or each point in the signal stream where the start of each foreground data packet will be found, and as said signal stream is received using said receive map to locate the start of each foreground data packet.

In certain embodiments, the method further comprises the step of storing, in said receive map, locations in said signal stream that are not a start of a foreground data packet. In this way the second network interface is able to identify the background data packets upon receipt.

In some embodiments, the method further comprises the step of storing an indicator associated with each entry in said receive map, which indicator determines whether data arriving with each foreground data packet is to be written to a receive buffer, a forwarding buffer or both. This increases the speed of processing the incoming signal stream.

In certain aspects said second network interface is part of a network node for which data may arrive in said signal stream, the method further comprising the steps of storing and configuring a routing table associated with said receive map, which routing table comprises a list of entries having an order that matches an order of entries in said receive map, and when data intended for said network node arrives at said second network interface in the nth point in said signal stream, looking up the nth entry in said routing table to determine a call identifier associated with that data. A significant advantage of this is that the second network interface does not have to read any header to obtain a channel identifier such as an ATM VCI.

In certain aspects said first network interface stores a transmit map in which the or each point in said signal stream is identified, the method further comprising the step of said first network node constructing said signal stream according to said transmit map. This helps the network interface to construct the outgoing signal stream efficiently.

In certain embodiments, the method further comprises the step of storing an indicator associated with each entry in said transmit map, which indicator determines whether data to be transmitted is to be obtained from a forwarding buffer or a transmit buffer.

In certain aspects the present invention provides a network which supports connection-oriented Reserved Bit Rate (RBR) data streams with guaranteed QoS at any data rate; such data streams are herein referred to as 'foreground' data streams, or traffic, that comprise foreground packets. The network also supports both connection- oriented and connectionless background packet transfer. As used herein 'background' packets are those that have been assigned a lower priority than the foreground packets; such background packets may include best-effort packets such as IP datagrams. The background packets can use all of the capacity of a link that is not required for foreground traffic, including capacity that has been reserved but is not used.

The packet size for the RBR service is variable, unlike ATM's fixed-size cells. This allows low-bit-rate media (such as voice) to be sent more frequently, and therefore with lower delay, in smaller packets, while also reducing overheads for high-bit-rate media such as video which can be sent in larger packets. It also simplifies the encapsulation of traffic such as uncompressed PCM audio by conveying one sample per packet independent of bit depth, number of channels, etc, whereas over ATM (as specified in AES47 and IEC 62365) compromises have to be made to fit the data into 48-byte cells. Each RBR call is allocated one or more periodic "slot" or "point" in the signal stream in which to transmit foreground packets. The signal stream (which may comprise bits, bytes or symbols) on each link is divided into "allocation periods", and a slot occurs at the same point in each allocation period. The size of the slot defines the maximum size of the foreground packet which can be transmitted in it; in each slot the application may transmit a foreground packet of any size, from zero up to the maximum for the slot. Where the packet is smaller than the slot, the remaining bytes are available for background packets, in addition to all bytes that are not part of a slot.

An application requesting transmission of data in the foreground specifies the maximum size of packets and the number of packets per second, and the network allocates one or more slots of the requested size. In certain embodiments, allocation periods are nominally 124.96μs long and the system allows for the media clock to be up to 0.032% faster than the network clock, so an application requesting a call that can carry up to 8000 packets per second will have one slot reserved for it, one requesting 8001 to 16000 will have two slots reserved, and so on. Where more than one slot is reserved, the network aims to distribute them evenly across the allocation period, subject to the requirement to fit round slots that have already been allocated. Existing slots can be moved if the space available has become too fragmented to accommodate the new slots.

Latency through the network and requirements for buffer space for foreground packets will be reduced, and routing simplified, if all links use the same size allocation period and the phase relationship between any two allocation periods is constant. However, foreground packets can still be forwarded between links that are not synchronised, including those with different-sized allocation periods, by implementing in local memory a FIFO for each foreground call large enough to hold four packets of the maximum size for that call.

In certain aspects cut-through routing of foreground data packets is used to reduce latency.

In some embodiments said signal stream forms an outgoing stream from said first network node, and said first network interface has an incoming stream from another network interface, the method further comprising the steps of:

(a) storing in said forwarding buffer those foreground data packets of said incoming stream that are to be forwarded in said outgoing stream, said transmit map comprising a pointer to a location in said forwarding buffer for each foreground packet that is to be forwarded as part of said outgoing stream; and

(b) using said transmit map to lookup the location of each foreground data packet, read the data and insert it in said outgoing stream at a position defined by said transmit map.

In certain aspects, during step (a) said foreground data packets are stored at an address in said forwarding buffer that is dependent upon the position of each foreground data packet in said incoming stream.

In some embodiments the method further comprises the steps of assigning an address to each foreground data packet in a pre-determined order and writing each foreground data packet to said address in said foreground buffer such that each foreground data packet has a minimum lifetime in said forwarding buffer before it can be overwritten by another foreground data packet. The lifetime provides a window for said first network interface to forward said foreground data packet in said outgoing stream.

In some embodiments said outgoing stream comprises allocation periods, each foreground data packet occurring at the same point in each allocation period, the method further comprising the steps of synchronising said outgoing stream to said incoming stream, for example by adjusting the total number of bits, bytes, or symbols in each allocation period. Several advantages of this include: no need for the header of the foreground packet to carry any kind of channel identification, no need for the second network interface to perform a table look-up before forwarding the data, and no need to implement queues for outgoing foreground traffic. Thus the foreground packet header can be kept very small (e.g. 1 byte), reducing overhead on the network. In some embodiments, the buffer to which incoming foreground packets are written is a circular buffer. In this way the oldest data is overwritten first by incoming data.

On each link, "framing" is used to show where each allocation period starts. The nature of the framing depends on the technology used for the link, for instance when using an Ethernet physical layer an allocation period will consist of several Ethernet packets, one of which carries a "start of allocation period" indication. Certain payload bytes (identified by their position in the allocation period, in the same way as TDM channels) are declared by the sender to be "slot start" bytes, and a foreground packet begins at each slot start. The specification of which bytes in a period are slot starts is an "allocation". In a switch where the allocation periods on all the links have a defined phase relationship, the foreground packet to be transmitted for each slot is defined to be the packet that arrived in a specified slot on a specified input. There is thus no need for the header to carry any kind of channel identification, and no need for the switching fabric to perform a table look-up before forwarding the packet, nor to implement queues for outgoing traffic. The data rate on the incoming and outgoing links is known, likewise the transit times into and out of the buffer memory and the timing relationship between the two links, and the maximum packet length is specified; thus the software which allocates slots on the outgoing link can identify the earliest position for the slot start such that each byte of the packet will have been written to the buffer by the time it is read, and the latest such that none will have been overwritten before it is read, and can fix the position of the slot start at a suitable position within this window. The transit time through the interface is then known precisely, apart from tolerance in the synchronisation between the two links.

The format on the link includes an indication of which of two allocations will be used in each allocation period; in the preferred embodiments this indication is included in the framing at the beginning of the previous period. When a channel is connected or cleared down, the sender makes a new allocation and sends a message to its link partner (usually in a background packet) specifying the new allocation; when it receives the link partner's acknowledgement that it is ready for the change, it can switch to the new allocation. The old allocation is then no longer required, and can be re-used for the next change.

Connection-oriented background packets are divided into fragments in the same way as in ATM AAL5, but the fragments are larger than ATM cells and the last fragment is variable-length so no padding is required. Unlike foreground packets, background fragments are not forwarded until they have been completely received, because the incoming fragment may be interrupted by foreground packets in a way that is not easy to predict. Fragmentation allows forwarding of large packets to begin sooner, and avoids the need to specify a maximum packet size. The fragment size in the preferred embodiments is 240 bytes, so switching equipment can use 256-byte fixed-size buffers and store-and-forward delays are only 20μs plus queuing time at 100Mb/s, 2μs plus queuing time at lGb/s, while the overheads for a long packet are only one-fifth of those for ATM.

Background fragments do not have slots allocated to them, so the header contains a "flow number" which is an index into the routing information, similar to an ATM VPI/VCI, and fragments are routed in a similar way to UBR cells in ATM.

Because only one traffic class is routed in this way, only one queue is needed at each output.

Connectionless background packets, such as Internet Protocol datagrams, may be carried over background calls connected in a similar way to those used for IP over

ATM (RFC 2225). They can also be carried directly in the background stream, in which case, because they are not routed in the same way as connection-oriented packets, they can use larger fragments.

Both connection-oriented and connectionless background data packets are fragmented without regard to the space between foreground data packets (which may well change between allocation periods). Furthermore, because the length of each foreground data packet is either indicated in the corresponding header or is a known fixed length, no further fragmentation of the background data packets is required if any are interrupted by foreground data packets.

In some embodiments the method further comprises the step of storing background data packets arriving on said incoming link in a FIFO buffer and retransmitting said background data packets from said FIFO buffer on said outgoing link. In certain embodiments, the FIFO buffer and the circular buffer mentioned above are implemented in a single RAM block.

In certain aspects the method further comprises the step of deciding whether or not to place said background data packets in said FIFO buffer according to a forwarding count field present in a header associated with each background data packet, said forwarding count being decremented on each retransmission of the background data packet.

In other embodiments, the method further comprises the steps of said first network interface transmitting to said other network interface, which other network interface generates said incoming stream to said first network interface, an indication of the state of said FIFO buffer, and said other network interface using said indication to determine whether to send any background data packets to said first network interface.

In certain aspects the method further comprises the step of dividing said signal stream into a plurality of allocation periods, each agreed point for the start of a foreground data packet occurring at the same position in each allocation period.

According to other aspects of the present invention there is provided a network adaptor comprising an integrated circuit having logic adapted to cause the network adaptor to perform the first network interface steps set out above.

According to other aspects of the present invention there is provided a network adaptor comprising an integrated circuit having logic adapted to cause the network adaptor to perform the second network interface steps set out above.

According to other aspects of the present invention there is provided a network adaptor comprising an integrated circuit having logic adapted to cause the network adaptor to perform the first and second network interface steps set out above.

According to yet another aspect of the present invention there is provided a network node comprising a network adaptor as set out above.

According to another aspect of the present invention there is provided a switch comprising a plurality of network interfaces, at least one of which comprises a network adaptor as set out above.

According to another aspect of the present invention there is provided for use in a method as set out above, a foreground data packet comprising a header that indicates its length.

According to some embodiments of the present invention there is provided a method of transmitting both foreground data packets and background data packets as a signal stream on a link between a first network interface and a second network interface, said foreground data packets having a higher priority than said background data packets, which method comprises the steps of:

(a) when foreground data packets are to be sent, assigning a point in said signal stream that will serve as a starting point for each foreground data packet; and (b) said first network interface sending each foreground data packet with a header comprising an indication of the length of that foreground packet in said signal stream; whereby said first network interface is able to use all available space in said signal stream not used by foreground data packets for transmission of background data packets.

BRIEF DESCRIPTION OF THE FIGURES

For a better understanding of the present invention reference will now be made, by way of example only, to the accompanying drawings in which:

Fig. 1 is a schematic block diagram of a network interface according to the present invention;

Fig. 2 is a schematic block diagram of hardware components of the network interface of Fig. 1; Fig. 3 is a schematic block diagram illustrating how packets and fragments are routed inside the network interface of Fig. 1;

Fig. 4 is a diagram of the structure of a frame on a link that uses an Ethernet physical layer;

Fig. 5 is a diagram of a header part of the frame of Fig. 4; Fig. 6 is a diagram of part of a byte stream illustrating how bytes are assigned to different layers;

Fig. 7 is a diagram showing the format of foreground packets of different lengths;

Fig. 8 is a diagram of a header part of one of the foreground packets in Fig. 7; Fig. 9 is a diagram of the format on a segment of the header of a background fragment which is not the last of a packet;

Fig. 10 is a diagram of the format on a segment of the header of a background fragment which is the last of a packet;

Fig. 11 is a schematic block diagram illustrating various ways network interfaces according to the invention can be connected together to form segments;

Fig. 12 is a schematic block diagram of a switch according to the present invention;

Fig. 13 is a schematic block diagram of hardware components of the switch of Fig. 12; Fig. 14 is a diagram of the format on a direct link of the header of a background fragment which is not the last of a packet;

Fig. 15 is a diagram of the format on a direct link of the header of a background fragment which is the last of a packet; and

FIG. 16 shows how an IP datagram is carried on a direct link.

DETAILED DECRIPTION OF THE PREFERRED EMBODIMENTS

Two embodiments of the invention are described below.

The first embodiment is a network interface which provides a connection to a network for a piece of audiovisual or computing equipment. Examples of such equipment include, but are not limited to: personal computers, consumer electronic equipment, CCTV cameras, equipment in broadcasting and recording studios, and components of public address and sound reinforcement systems. The network interface comprises two network ports so that equipment can be chained together, allowing several units to share a single switch port and allowing a small network to be built without a switch. In this configuration the network interface is similar in functionality to an add-drop multiplexer for foreground packets and to an interface to a buffer-insertion network for background traffic.

It is envisaged that the network interface may comprise a single network port. With such network interfaces it is possible to build a star-connected network, for example.

The second embodiment is a network node in the form of a switch. In use a signal stream is carried over a point-to-point Ethernet link (using twisted-pair or fibre optic cable) between network interfaces. It will be noted that the cable does not form part of the network interface or switch, and that the cable is only required when the two embodiments are put to use. Implementations over other physical layers, such as wireless, will be functionally similar. In these two particular embodiments, the signal stream comprises a byte stream. However, it is possible for the signal stream to comprise other streams, such as bits or symbols.

Each embodiment can be divided into two parts. One is a control computer, which comprises a processor, RAM, and non- volatile memory; it runs software that implements the various control and management protocols and in particular participates in the process of choosing how calls will be routed through the system. The other part is the switching fabric which comprises sequential logic that copies incoming data to the outputs. It is controlled by tables held in local RAM that are written by the control computer.

Software, including FPGA logic and configuration data, is stored in nonvolatile in-system-programmable memory such as flash EPROM. When the unit is switched on, bootstrap code is run in the control computer to load programmable logic and perform other initialisation; the bootstrap code may be pre-programmed into the EPROM or loaded into it via other means such as JTAG or stored in a separate ROM. During software development the bootstrap code may be run from an in-circuit emulator. New software can be loaded during normal operation, for instance by the procedure specified in subclause 5.2 of Part 1 of IEC 62379 and outlined in the description of Fig. 2 below. It can also be loaded by the bootstrap code, typically via an RS232 serial interface.

Referring to Fig. 1 a network interface generally identified by reference numeral 10 comprises two Ethernet ports 1, 2 which are identical insofar as that it does not matter which one a network cable (not shown) is plugged into. Either one or both of the Ethernet ports 1, 2 may comprise a wireless interface instead of a wired port. The function of the network interface 10 is to receive data on each of the

Ethernet ports 1 , 2 and either pass the data up to higher layers if it is intended for the network node of which the network interface is a part, or to forward the data via the other of the two Ethernet ports 1, 2 if the data is not intended for that network node.

The network interface 10 also comprises a switching fabric formed from two MAC layer routing blocks 3, 4, which are described in greater detail below in conjunction with Fig. 3. Local media interfaces 6 copy data to and from FIFO buffers 7. For uncompressed digital audio, the FIFO buffers 7 and received-media buffers in sdRAM 5 store 32-bit audio subframes in a similar format to that specified in AES47- 2006. For compressed media they store the compressed bit stream, for example as 188-byte MPEG transport stream packets. The process of copying between external interfaces (not shown) and the local media interfaces 6 may include format conversion, for instance between analogue and digital, or between compressed and uncompressed formats. The external interfaces may include analogue and digital audio and video standards, and also more general-purpose computer interfaces such as USB.

A control computer 8 interfaces with the MAC layer routing blocks 3, 4 and with the sdRAM 5. As mentioned above, the control computer 8 runs software that implements the various control and management protocols and in particular participates in the process of choosing how calls will be routed through the system. The control computer 8 is also responsible for configuring the MAC layer routing blocks 3, 4 by writing their routing tables. Optionally, low-data-rate local interfaces 9, such as RS232, are also connected via this computer.

Fig. 2 shows further details of the hardware of the network interface 10 (some of this hardware has already by shown in Fig 1; like reference numerals in Fig. 2 indicate like parts). A Field Programmable Gate Array (FPGA) integrated circuit 120, is programmed to bring about the functionality of the MAC layer routing blocks 3, 4 and the FIFO buffers 7 described herein. In this embodiment the FPGA 120 comprises a XILINX® XC3S1000. FPGAs with more RAM blocks such as the XC5VLX30 in the XILINX® Virtex 5 series would allow larger internal tables 12,

16 to be used, supporting finer-grain allocation of capacity to foreground traffic. The design makes extensive use of the "distributed RAM" facility whereby the look-up tables in the FPGA logic elements can be used as small RAMs or shift registers, so an

FPGA that did not have this facility would be unsuitable. The synchronous dRAM 5 holds buffers for incoming data and also data and working-space for the software; it is 32 bits wide and clocked at 125 MHz, thus giving a bandwidth of 4Gb/s. A lower bandwidth (narrower interface or slower clock) would restrict the amount of data that can be handled; a higher bandwidth would be needed to support some more extreme applications such as conveying data at wire speed between an IP network and a system using the present invention. In this embodiment the size of the RAM is 16 megabytes (128 megabits). This is sufficient for most applications and allows incoming data to be buffered for several tens of milliseconds; larger sizes would allow incoming data to be buffered for longer. Other forms of interface to the sdRAM 5 could be used, such as separated I/O, which uses separate data paths for reading and writing, and double data rate (DDR) which transfers two words per clock cycle. Static RAM could be used, though with current technology multiple ICs would be required to build a large enough memory.

The software runs on an 80 MIPS 16-bit Digital Signal Processor IC 121, although any kind of processor with similar or greater processing capacity could be used. For initial software development, the in-circuit emulator interface 122 is used to load the "bootstrap" code which can then program flash memory 123 with data received via the serial interface 9 and, once the flash is programmed, load and run software from the flash memory 123. The flash memory 123 in units coming off a production line can be programmed from the FPGA via its JTAG interface 124. The in-circuit emulator 122 is therefore not required for commercial products that incorporate the network interface 10.

Once there is software in the flash memory, it can be updated via either the network or the serial interface, using the procedures specified in 5.2 of Part 1 of IEC 62379. These procedures allow a management terminal, which may be part of a control system, to upload new software to the network interface 10, including a mechanism for ensuring that the previous software cannot be deleted until the new software has been completely uploaded and verified. The management terminal does not need to understand the software it is uploading, merely copying it from a file as a string of bytes. The procedures specify how the appropriate files can be identified.

As an alternative to the DSP 121, a processor could be implemented within the FPGA 120, in which case the DSP 121 could be replaced with a small microprocessor which handled initialisation, including programming the FPGA 120 with data from the flash memory 123.

For the purposes of understanding the present embodiment an example will be described that explains the carriage of uncompressed digital audio and high-quality compressed digital video between studios of a radio or television station. In a typical scenario, the local media interfaces 6 are AES3 for digital audio, and MPEG

Transport Stream packets carried on DVB-ASI for video. Foreground traffic uses reserved bandwidth, and is connected and disconnected by the interface units in response to commands from a control system using messages such as those specified in IEC62379.

The maximum packet size and the number of packets per second to be sent by the network interface 10 depend on the media format. For stereo audio sampled at 48kHz there will typically be 48000 packets per second each 9 bytes long (32 bits per channel plus 1 byte to carry timing information). For HD video at 24Mb/s there might be 16000 packets each carrying one MPEG transport stream packet and so 188 bytes long. In this example each packet will be either the maximum length or (if there is no audio sample ready or, in the case of video, no TS packet ready) zero length. In other circumstances packets might be variable length, for instance in the video case if each packet carries as many bytes as have arrived on the ASI interface since the last packet, rather than either a whole TS packet or nothing. The control computer 8 in the network interface 10 might decide the media format based on the incoming AES3 or ASI signal, or it might be instructed by an external control system (not shown) to use a particular format. For example, a control system in a radio station will be a computer or network of computers which the operators in the control room use to set up the audio connections between studios, links from other sites, and transmitters. The control system does that by sending commands to the various items of equipment that actually make the connection, using either a standard such as IEC62379 or a proprietary format peculiar to the particular piece of equipment.

An application running in the control system may generate an instruction to transmit the audio and video data to a remote destination unit (not shown), for example another network node in another studio accessible via a network such as a LAN or WAN. Since the audio and video data is time-critical, i.e. the application needs to know the shortest and longest time it can take to traverse the network and may not be able to function properly if these times are outside certain limits, the application will seek to send the data with a guaranteed QoS along a route to the destination node. In this embodiment packets of data traversing a link under a guaranteed QoS are referred to as foreground packets; any other data not sent as foreground packets are referred to as background packets. It is to be noted that any kind of data may be sent in foreground packets - the use of the invention is not restricted to the sending of time-critical media in the foreground packets. For example, it would be possible to send IP datagrams in the foreground packets, the IP datagrams being differentiated from those sent by best-effort by the level of service that the user has purchased from an ISP to guarantee a certain bandwidth for example. Before sending foreground packets the network interface 10 must reserve the resources along the route for the call, and such a call in which foreground packets will be sent is referred to herein as a "reserved bitrate" call or RBR call.

The main requirement before foreground packets can be sent in an RBR call is that the sender (in this case the network interface 10) is sure that the receiver (e.g. another network interface or switch) knows at which points or "slots" to find the foreground packets in the signal stream.

The signal stream on a link is divided into allocation periods, and the framing layer defines where each allocation period begins. The framing layer includes link- specific encapsulation which may take several forms, and is in general different for different physical layers. Further detail of such encapsulation is described below in conjunction with Figs. 4 and 5.

In this embodiment the allocation period is 124.96μs long, which is 1562 bytes at 100Mb/s and 15620 bytes at lGb/s. Table 1 below shows appropriate formats for use with an allocation period of this length. In the table/is the number of frames per allocation period, p the number of payload octets per frame if admin records are present, a the number of admin records per frame if present, and g the nominal number of gap octets between frames. The number of octets in each gap may be varied by ±1 (128 parts per million for lGb/s reduced format, more for others). The number of framing octets per packet, excluding the gap octets and the admin records, is 36 for the full format and 11 for the reduced format. The last two columns show the data rate of the payload string if the same packet sizes are used with a 125μs allocation period; the last is for the case where there is no admin record so there are p+a payload octets per frame.

Table 1

A slot is a part of the payload of a frame in which a foreground data packet may be located, and comprises a slot start (on a slot start layer) and a contiguous set of bytes within the remainder of the payload (excluding the slot start layer), beginning at a fixed offset or gap from the slot start. This offset is part of the specification of the format on the link, and is described in greater detail below in conjunction with Fig. 6.

Slots should be allocated in such a way that the parts not on the slot start layer do not overlap each other, and the whole slot fits within an allocation period. An allocation specifies, for each slot: the position of its start; its length; and the flow to which a packet in the slot belongs. The length is not necessarily signalled to the other end of the link, but the remaining information must be, because it defines which payload octets are on the slot start layer and how foreground packets are to be routed.

A foreground packet begins in its slot start and continues in the remainder of the slot, being aligned at the beginning of it. It may be any length provided it fills the slot start but is not longer than the slot.

There are envisaged various possibilities for guaranteeing that both sender and receiver know the assignment of slots, including configuration of the RBR call by the sender or by the receiver. In the following, configuration of the RBR call by the sender will be described primarily. When instructed to connect an RBR call, the network interface 10 constructs a FindRoute request message which it sends on both of the Ethernet ports 1, 2. This message is similar to a Q.2931 SETUP message in that it has a fixed- format header which includes the message type and an identifier for the call followed by "information elements" in a tag- length- value format which detail various aspects of the call, although details of the information elements are different, as they include information which is not supported by ATM networks, including slot allocations and items such as service name and privilege level which are specified in IEC62379, and the way in which items such as addresses and data formats are represented is more flexible. As with Q.2931, some of the information in this message is for the network and some is for the destination unit i.e. the intended recipient of the audio and video data as distinct from the intermediate receivers en route. The information for the network includes the size of slot required and the number of slots per second; before sending the FindRoute request for an RBR call the software may check that enough capacity is available and return a "line busy" error if not. However, a preferred alternative is for the capacity check to performed at a later stage during the call setup procedure. This simplifies the procedure as resources do not need to be reserved first and then allocated later. As the FindRoute message propagates through the network on different routes, information is collected on how busy each route is so that if several routes are found the least busy can be chosen.

The information for the destination unit includes the format of the data contained in the packets. Note that there is a clear distinction between the process of conveying the packets (by the network) and that of interpreting the data contained within them (by the end unit). The data format is private to the application and does not need to be understood by the network.

Another network interface receiving a FindRoute request simply considers whether the RBR call is addressed to it, and retransmits the message on its other port if not. If the FindRoute request arrives at a switch, the switch uses its knowledge of the topology of the network, and of the current load on each of its links, to decide on which port(s) to offer the call, in a similar way to ATM or IP routing. A unit which can accept the call responds with an "offer", and the calling unit (which may receive several offers, in some cases from different units that can offer the requested service but more usually from a specific destination unit by different routes) sends a confirmation message for the chosen offer. These messages include details of the slots that will be allocated to the call when it is connected, as described in the "link management" section below.

Note that the application does not need to know the size of an allocation period, nor the size of a packet header on the link; for example, for audio it requests a connection able to carry 48000 packets each containing up to 9 data bytes. The link management protocol stack which runs in the interface unit's control computer translates this into a requirement for 6 slots of size 10 bytes each (1 byte header + 9 bytes data; see Fig. 7 described below). Similarly for video 2 slots of size 190 bytes (2 bytes header + 188 bytes data) will be allocated.

Each node en route must be synchronised before any RBR calls can be connected (i.e. foreground data packets sent) on a segment. Once the link comes up, nodes may begin to synchronise as follows. Following synchronisation, RBR calls can be connected as needed.

In each node, the transmit logic 15 selects the number of gap bytes between frames such that the average deviation from the number in table 1 is equal to a parameter which is a fixed-point fractional number in the range -1 to +1, set by a phase control algorithm which runs in the control computer 8. The logic in the FPGA

120 stores where the start of the most recent incoming frame in each direction occurred relative to the outgoing frame in each direction (a total of 4 numbers for a network interface with two ports).

There are two potential inputs to the phase control algorithm: the phase relationship with the incoming stream on the other port (so-called through synchronisation) and on the same port (so-called loopback synchronisation towards the tail of the segment in the direction of transmission). On an isolated segment or a ring, through synchronisation is used; there is no loopback synchronisation, and the two directions are not synchronised to each other.

On a singly-connected segment (72 to 76 in Fig. 11; see associated description), every node applies through synchronisation in the direction away from the switch, and loopback synchronisation towards the switch, so that all streams into and out of a switch have the same allocation period and a stable phase relationship. At the end node loopback synchronisation serves to frequency- lock the stream towards the switch to the stream in the opposite direction. At the intermediate nodes it serves to limit the phase difference between those two streams, which on a long segment at 1 or 2 octets per node could otherwise accumulate substantially.

On a doubly-connected segment (81 to 88 or 91 to 94 in Fig. 11) one of the switch ports is chosen as sync master and loopback synchronisation is applied in the direction towards that port. The other port must tolerate a much wider variation in the phase relationships.

The priorities for the phase control algorithm are as follows. Firstly, it must keep the phase relationship between incoming and outgoing streams within the range assumed by the slot allocation software; failure to do so will corrupt foreground packets. Secondly, it should attenuate jitter in the control parameters to a sufficient extent that the frequency on a ring is stable. Thirdly, it must keep the phase relationship between incoming and outgoing streams close to the value it had immediately before synchronisation was enabled.

Thus there should be a region towards each edge of the range for through synchronisation which the phase control algorithm tries to avoid. Within the part between those regions, it controls to stay close to the centre of the range for the selected synchronisation, with a long time constant so that any jitter in the incoming allocation periods will be heavily attenuated.

Once nodes en route are synchronised, and the RBR call has been established, data bytes for outgoing foreground packets are taken directly from the FIFO buffers 7, while incoming data on the Ethernet ports 1, 2 proceeds via larger buffers in the sdRAM 5 so that presentation time can be delayed to synchronise with other media or to allow for variations in arrival time when data have travelled over networks that cannot guarantee QoS.

With each AES3 digital audio input is associated one of the FIFO buffers 7, and audio sub frames are written to it as they arrive. Each outgoing slot associated with that input will contain a packet carrying a pair of subframes from that FIFO, or an empty packet if the FIFO is empty. Each AES3 digital output (i.e. one of the local media interfaces 6) sends at a rate which is fine-tuned to synchronise it with either a local "sync" signal or the rate at which samples arrive on the network. The output subframes are taken from one of the FIFO buffers 7; the logic keeps this FIFO topped up by copying from the buffer in the sdRAM 5 to which received samples from the appropriate call are routed.

Background (best-effort) data packets are stored in linked lists in the sdRAM 5 which are administered by the control computer 8; each element in a list can hold two fragments, and there is no limit to the number of fragments in a packet other than the total amount of space allocated to the list. The control computer 8 examines all incoming packets and each one is either processed locally, queued for retransmission (possibly with a different header), or discarded.

Fig. 3 shows further details of the MAC layer blocks 3, 4. An incoming signal stream is analysed into five layers by receive logic 11 (which is implemented in the FPGA 120). The five layers are: framing, admin, slot starts, foreground, and background; further details of the format are given below. As explained above, the framing bytes provide a reference point relative to which the locations of slot starts can be specified, and admin bytes provide other information which is detailed below. The position of the framing and admin bytes is fixed for each format, and in the case of an Ethernet link the details of the format to be used are negotiated when the link is established. Normally, allocation periods occupy the whole of the capacity of the link, but where appropriate a format could be used in which there is time between them for other traffic, though in that case calls that require multiple slots could not have the slots distributed evenly in time.

A receive slots map 12 is associated with the receive logic 11 and identifies which bytes in the signal stream are slot starts, and for each one whether the foreground packet is to be written to a receive buffer 13 or a forwarding buffer 14 or both. The forwarding buffer 14 comprises a foreground circular buffer 14a and a background FIFO 14b. Addressing in the foreground circular buffer 14a is as if the whole payload string were written to it, but only foreground data packets are actually written. This allows a single RAM block to be used for both buffers 14a and 14b. It also allows foreground data packets received on a 1 Gb/s link to stay in the foreground circular buffer 14a long enough to be forwarded on a 100 Mb/s link for example. Further details of how this is achieved are described below.

The forwarding buffer 14 is always enabled so the network interface 10 can always carry background flows, including management messages. However, foreground flows cannot be set up until synchronisation is enabled (as described above). Note that background flows need no setting-up on the part of nodes through which they pass, whereas foreground flows need slots to be allocated.

The position of the start of a foreground data packet is defined in the receive slots map 12 as an offset from the start of a frame. To indicate where each foreground packet is to be written, the receive slots map 12 has a 2-bit indicator for each byte in an allocation that has an even address. The "address" of a byte defines where it appears in the allocation period; in this embodiment only those bytes with even addresses can be slot starts, which halves the size of the slots map 12. It is to be noted, however, that use of only even addresses is not essential. For example, all addresses could be used or only odd numbered addresses. The binary value of the 2- bit indicator is 00 if the byte is not a slot start, 01 if the packet in the slot is to be copied to the receive buffer 13, 10 if it is to be copied to the foreground circular buffer 14a, and 11 if it is to be copied to both. When an RBR call is set up, the receiving network interface configures its receive slots map 12 with the appropriate binary values for those bytes of the signal stream that have been assigned to the RBR call; further details of the process are in the "link management" section below. For example, if the receiving network interface is not the destination for the foreground packet data, the corresponding entry in the receive slots map 12 would be given a value 10. For the duration of the RBR call, each time this slot arrives in the signal stream, the receive slots map 12 indicates that the foreground packet in the slot is to be copied to the foreground circular buffer 14a ready to be sent on through the other Ethernet port.

As mentioned above, each byte in an allocation period that is not on the framing or admin layer is designated by an address, which is a binary number. In this embodiment, the address increases strictly monotonically throughout the period, so that the address of each byte is greater than the addresses of bytes that precede it in the allocation period and less than the addresses of bytes that follow it in the allocation period. There are 15508 bytes that have addresses in each allocation period and the addresses are 14-bit numbers excluding those for which the least significant 10 bits would hold a value in the range 0 to 51. Thus there are 16 x (1024 - 52) = 16 x 972 = 15552 possible addresses of which all but the last 44 are used, so the addresses are 52 to 1023, 1076 to 2047, ..., 14388 to 15359, and 15412 to 16339.

The address to which each byte of a foreground packet is written in the foreground circular buffer 14a is the least significant 10 bits of its address in the allocation period. The byte will not be overwritten until the next one with the same value in the least significant 10 bits of its address arrives; for bytes with addresses less than 15360 this will not be until after a further 971 bytes, plus at least 3 bytes on the admin layer, so each such byte will be in the buffer for at least 974 byte times after its arrival. For bytes with addresses 15412 upwards it will not be until after a further 927 bytes plus 3 admin bytes plus 22 framing bytes, i.e. 952 byte times. Depending on how accurately the outgoing and incoming allocation periods are synchronised, and how sophisticated the algorithm that assigns slots is in taking account of the positions of framing and admin bytes, there will be a lifetime of some 800 bytes within which the slot in the outgoing allocation can be allocated. A larger buffer, using more of the address bits, would allow the outgoing slots to be later, but using the extra allowance would cause a significant increase in the delay between reception and retransmission.

For each entry with a 1 in the second bit of the 2-bit indicator in the receive slots map 12 (i.e. indicating that data arriving in that slot is intended for that node) there is an entry in the routing table 12 showing to which RBR call the packet belongs and thus controlling to which buffer in sdRAM 5 copy logic 18 (which copies incoming traffic from the FIFOs 13 to the sdRAM 5) will write it. In particular, the routing table comprises a list of call identifiers (e.g. virtual channel numbers) and the order of the list matches the order of slots in the receive slots map

12. In that way, for the nth entry in the receive slots map 12 that contains a 1 in the second bit, the copy logic 18 reads the nth entry in the routing table to identify the call with which that data is associated and then writes both the data and the call identifier to the appropriate buffer. The first byte of each foreground packet is in a slot start byte, and the rest are on the foreground layer; the value in the slot start byte shows whether there is anything on the foreground layer, and if so either the length or that it is at least 16 bytes long (this is described in greater detail below). Accordingly, if the header of the foreground data packet indicates that there is no foreground data following it, the copy logic 18 need not perform a lookup in the routing table and that step is skipped.

All bytes that are not on any of the other layers are background bytes, and carry background fragments in the format detailed below. Fragments with a nonzero forwarding count are written to the forwarding buffer 14b; fragments which have a zero forwarding count or are marked as broadcasts are written to the receive buffer

13. Thus broadcasts with a non-zero forwarding count are written to both buffers.

The copy logic 18 copies the incoming data (both foreground and background) to the sdRAM 5. In the case of a foreground packet, the call identifier from the routing table 12, which the receive logic 11 puts in a foreground FIFO part of the receive buffer 13 along with the packet, shows to which media buffer it should be written as explained above.

Background fragments are written in buffers in the sdRAM 5 taken from a "free list" administered by the control computer 8; there is a separate free list for each Ethernet port 1, 2, so that a storm of incoming packets on one port will not prevent packets from being received on the other. Packets are reassembled separately for each "flow" (see below), but all completed packets are put on a single queue for processing by the control computer 8.

Transmit logic 15 in the FPGA 120 constructs the outgoing signal stream. Framing, admin, and payload bytes are generated in the appropriate sequence, and the software in the control computer 8 fine tunes the framing, as described earlier, to keep the phase relationship to the incoming byte stream within limits such that foreground packets will be present in the forwarding buffer 14a when expected. A transmit slots map 16 identifies which payload bytes are slot starts, and whether the packet comes from the forwarding buffer 14a or a transmit buffer 17. In the latter case copy logic 20 reads ahead in the routing table and, for the nth entry in the transmit slots map 16, reads the nth entry in the routing table to discover the call identifier. Using the call identifier, the copy logic 20 can then read data for the appropriate call in the local interface FIFOs. In this way the copy logic 20 ensures that there is a foreground packet for the call identifier (e.g. virtual channel number) indicated in the transmit slots map 16 in the foreground half of the transmit buffer 17 i.e. that data is placed in an order in the foreground part of the transmit buffer 17 that matches the order of the transmit slots map 16.

In the former case, the transmit slots map 16 comprises a pointer to the address in the foreground circular buffer 14a where the start of the foreground data packet to be forwarded can be found. Through the byte addressing method described above, the transmit logic 15 need only be pointed to the correct location in memory where to find the data of the foreground data packet. This is a considerable advantage since there is no requirement for the header of the foreground data packet to carry a VCI as per ATM for example. Instead the channel information is preserved by storing incoming foreground data packets to be forwarded in certain locations in memory which are known to the transmit slots map in advance. This configuration of the transmit slots map 16 is performed during RBR call set up.

Any slot that takes a packet from the forwarding buffer 14 must be timed such that the incoming packet will be available. Where the incoming link is slower than the outgoing (for instance, 100 Mb/s in and 1 Gb/s out), this means not beginning the outgoing slot too soon, so that the last byte of a maximum- length packet will be available by the time it is required for output.

Where the incoming link is faster (for instance, 1 Gb/s in and 100 Mb/s out), an incoming packet will only be in the buffer for one tenth of the time that it would have been at 100 Mb/s. However, the lifetime in the forwarding buffer 14a can be extended by ensuring that the part that is one buffer-length beyond it is unallocated. The upstream node needs to know that the following link is slower, so that it can allocate slots appropriately.

Allocation of slots is made easier by noting that the maximum delay through a node is determined by the size of the foreground part of the forwarding buffer 14a, and not (as in ATM CBR) by the rate at which packets are transmitted.

Similarly to the receive side, all bytes that are not on any of the other layers are on the background layer, and carry background fragments taken from either the forwarding buffer 14b or the transmit buffer 17. Whichever buffer the transmit logic 15 is pointed to by the transmit slots map 16, the first byte of the foreground data packet indicates whether there is any further data on the foreground layer. If not, the transmit logic reads either one of the background FIFOs (assisted by provision of a gap between the first byte of a foreground packet and the remaining bytes, as described in greater detail below). If both FIFOs have a fragment ready for transmission, the logic may always choose the forwarding buffer 14b, which is the regime used in buffer insertion networks, or it may adopt a "fairness" strategy such as giving the transmit buffer 17 priority for every nth fragment. An "idle" byte (or symbol) is transmitted at the point where a new fragment would otherwise start if neither FIFO has a fragment ready for transmission, also if the state of the FIFO in the downstream network interface's forwarding buffer (which is signalled in admin bytes in the opposite direction) shows that sending another fragment might cause it to overflow.

In particular, an admin record comprises one byte having 3 bits of CRC and 5 bits available to indicate how much space there is available in the forwarding buffer of the downstream network interface. The 5 bits indicate the number of free bytes in the FIFO divided by 64 and rounded down, or 31 if that is less. Thus 0 means less than 64 octets, 1 means 64 to 127 octets, and 31 means at least 1984 octets. The information carried in admin bytes will be out-of-date by an amount equal to the round trip time on the link, which can be measured using the AES51 timing field and is unlikely to exceed 192 bytes, and the recipient must allow for background data sent during that time. The remainder after making those deductions is the maximum number of background bytes that should be sent until another admin record has been received. Note that background fragments cannot be interrupted (except by data on higher layers), so a fragment cannot be started unless the space remaining is at least as great as its length.

Copy logic 19 copies background fragments from a list of packets in the sdRAM 5, administered by the control computer 8, to the FIFO which is the background half of the transmit buffer 17. Packets on the list may be originated by the control computer 8, for example segment management or call management messages or replies to requests from management terminals, or they may be from elsewhere, including via the RS232 serial interface 9.

If there is no link established on an Ethernet port 1, 2, the receive logic 11 and transmit logic 15 for that port (one of which will be in MAC layer routing block 3 and the other in MAC layer routing block 4) are disabled. When a link is first established, the port sends and receives Ethernet packets via the background FIFOs in the buffers 17 and 13 respectively; it attempts to negotiate use of the protocols described here with the link partner, using AES51 negotiation packets, including deciding details of the exact format to be used, and if successful switches to the use of the agreed format, otherwise uses IP over Ethernet. The forwarding buffer 14 is only used if both ports are operating in accordance with the invention.

When one of the Ethernet ports 1, 2 is using IP over Ethernet and the other is operating in accordance with the invention, the control computer 8 can cause an IP datagram received on one port to be retransmitted on the other, changing the packet header as required, without needing to move or examine the body of the packet in the sdRAM 5 buffer.

Fig. 4 shows the structure of a frame on an Ethernet link, and Fig. 5 shows the detail of a header 22 of the frame. Two kinds of frame can be used: "full-format" frames are Ethernet packets conforming to IEEE 802.3, and also ATM-E extension packets conforming to AES51, while "reduced- format" frames contain the minimum overhead required for a point-to-point link. On a 100 Mb/s link an allocation period consists of a single frame; on a 1 Gb/s link it consists of 10 full- format or 2 reduced- format frames. These last are "jumbo" frames which present-day Ethernet integrated circuits support although they exceed the maximum length specified in IEEE 802.3.

Referring to both Figs. 4 and 5 a full-format frame begins with 8 bytes of preamble and Start-of-Frame Delimiter (SFD) 21, 6 bytes of destination address 31, 6 bytes of source address 32, 4 bytes of VLAN tag 33, and 2 bytes of Length/Type 34 all as specified in subclause 3.5 of IEEE 802.3. The Length/Type field 34 and the first byte 35 of MAC client data are coded with respective hexadecimal values 88DD and 02, as specified in AES51, to indicate that the rest of the packet is coded in accordance with AES51. The next byte is the AES51 "type and format" code 36 which includes a flag marking the first frame of an allocation period and flags informing the recipient which of two allocations will be used in the following period and when pre-agreed changes in the synchronisation of the byte stream occur. The last four header bytes 37 are the timing word specified in AES51, and the frame ends with a Frame Check Sequence 25 as specified in IEEE 802.3. There is then a gap before the next frame; the size of this gap can be adjusted by the transmit logic 15 to maintain synchrony with incoming frames.

In a reduced- format frame, the preamble and SFD 21 is reduced to 2 bytes, and in the header the destination address to AES Ethernet protocol identifier inclusive 31-35 are omitted. Also, the gap between frames is the minimum required to meet the specification in IEEE 802.3 whereas the gap between full-format frames is about twice the minimum because a maximum- length packet is slightly less than one allocation period at 100 Mb/s, but not by enough to make it worth using two frames.

Note that whereas in point-to-point links the preamble 21 can be shorter than specified by IEEE 802.3 the minimum inter-packet gap must be observed because Ethernet interface integrated circuits expect to be able to use it to adjust FIFOs that cross clock domains.

In both formats, the byte immediately after the header and every 256th byte thereafter are admin bytes 23 which report the state of the background FIFO in the forwarding buffer 14 for the opposite direction (as explained in greater detail above), allowing the network interface 10 to avoid transmitting background fragments that would be discarded. The remaining bytes are payload bytes 24.

Fig. 6 shows a typical sequence of bytes in the middle of the payload part of a frame (therefore no bytes on the framing layer are visible), arranged to show the layer to which each belongs. One admin byte 23 is shown, and is on the admin layer.

Three slot start bytes 42, 44, 46 are shown. The sender of the frame will have stored the locations of these bytes within the allocation period in its transmit slot map 16 and notified them to the recipient during call setup; the recipient will have similarly stored them in its receive slot map 12 and acknowledged to the sender that it has done so. As mentioned previously, an alternative is for the receiver to decide locations of slot starts for the call and to inform the sender. The slot start byte contains the first byte of a foreground packet.

The format of variable-length foreground packets is shown in more detail in Fig. 7 and Fig. 8. Referring to Fig. 8 the primary function of the packet header is to code the length of the data following the header. The length is coded as the number of data bytes using 4 bits per header byte 56, using the minimum number of header bytes. So the maximum number of data bytes that can be coded by a one-byte packet header is 15; where the foreground data is longer than this, extra packet header bytes 52 are used to code the longer length as shown in Fig. 7. In that case, the most significant bits of the length are in the first packet header byte 51 and so on (moving left to right in Fig. 7). The remainder of each packet header byte 51 or 52 contains a continuation flag 57 which is 0 in the last header byte, and a CRC 58 on the other 5 bits. The first header byte 51 is on the slot start layer, while the remainder of the packet, consisting of the remainder of the header bytes 52, if any, and the data 53, is on the foreground layer.

Implementation of the transmit logic 15, and to some extent also the receive logic 11, is easier if it knows in advance which layer each byte will be on. Bytes on the framing and admin layers are in fixed locations relative to the SFD 21, and the locations of those on the slot start layer are in the slots map 16, 12 in which the logic can read ahead. However, whether each of the remaining bytes is on the foreground or background layer depends on the lengths of foreground packets; in particular, the value of the length field 56 in the first packet header byte 51, which is on the slot start layer, controls whether there is anything at all on the foreground layer for that packet, i.e. whether the byte that would hold the second byte of the packet is foreground or background.

Therefore, there is a gap between the slot start (i.e. the first packet header byte of the foreground packet) and the remainder of the packet; the size of this gap is fixed for each link format and in the implementations described is 1 byte, although it could be more than this. This gives the transmit logic 15 more notice of whether it needs to read from the foreground or background half of the buffer 14, 17. Note that there is no need for a gap after subsequent header bytes 52 because when they are present there will always be at least 16 further bytes on the foreground layer. In other implementations a longer gap may be appropriate. For instance, in a network where switching takes place in the optical domain controlled by comparatively slow electronics, more time will be needed to decode the slot start and then set the routing appropriately. In such systems it may not be possible for the background layer to use every byte not allocated to the other layers; for instance if the data rate is 160Gb/s and switching takes Ins then the first 160 bits (20 bytes) of a part of the data stream which is on the background layer may not be usable, similarly the last 20 bytes. Also, the lengths of foreground packets may be constrained, for instance they may be required to be padded to a multiple of a certain number of bytes, or to be a fixed length. However, for most applications such a system will still make more efficient use of the capacity of the fibre than the currently-available alternatives.

Returning to Fig. 6, the first slot shown contains a foreground packet ml; the slot start byte 42 shows that it is nonempty (the length 56 is non-zero; if the continuation flag 57 is set to 0 this is the number of bytes on the foreground layer, otherwise there will be at least 17 bytes - one header byte and 16 data bytes - on the foreground layer), so there are further bytes 43 on the foreground layer. The second slot start similarly contains the start of another foreground packet m2 44, 45. Foreground packet ml is the maximum length allocated to it during RBR call setup, and its data 43 ends immediately before the part of m2 that is on the foreground layer

45; the software that allocates slots and configures the copy logic 20 must ensure that packets cannot exceed their allocated length. Note that although ml 43 does not conflict with the part of m2 45 that is on the foreground layer it does extend beyond its slot start 44; this allows foreground packets to use 100% of the capacity of the link if required without wasting the aforementioned gap after each slot start. The third slot's packet, e 46, is empty.

All remaining bytes 41 are on the background layer, which carries background packets and idle bytes. Background packets may be fragmented, as per

ATM AAL5 for example, to allow forwarding of large packets to begin sooner and to avoid the need to specify a maximum packet size. However, since the signal stream has assigned points where foreground data packets can start, and because each foreground data packet comprises an indication of its length, fragmentation can be performed without regard to the spacing between foreground data packets, which may vary between allocation periods in any event. Accordingly, background fragments can be of a fixed size (e.g. 240 bytes) and no additional fragment headers are needed when a background fragment is interrupted in the signal stream by a foreground data packet or other administrative bytes.

A fragment which is not the last of a background packet consists of a header as in Fig. 9 (detailed below) followed by 240 data bytes. A fragment which is the last of a packet consists of a header as in Fig. 10 followed by the number of data bytes signalled in the length byte 66 of the header. Any background bytes not required for background fragments (i.e. when both background FIFOs in the forwarding buffer 14b and transmit buffer 17 are empty, or the admin byte in the other direction shows that there is congestion downstream) are idle bytes and are coded with all-ones (value 255). On link formats that supported it, they could instead be coded with a non-data symbol.

Fig. 9 and Fig. 10 show the background fragment header format. The first byte is the forwarding count 61, which is decremented by the transmit logic 15 when the fragment is transmitted. As described above, fragments are forwarded (via the buffer 14) until the count reaches zero, so the count when the fragment is placed in the transmit buffer 17 is the number of hops to reach its destination. The number of hops must be in the range 1 to 255 inclusive, so the forwarding count as transmitted will be in the range 0 to 254 and thus different from an idle byte.

The high bits of the second byte are three flags. The "s" flag 62 is 1 for the first fragment in a packet ("start of packet"), 0 otherwise; this is, strictly, redundant information, because the recipient should always know whether it has an unfinished packet, but it provides a consistency check on the packet stream and makes recovery from errors easier. The "e" flag 63 is 1 for the last fragment in a packet ("end of packet"), 0 otherwise. The "u" flag 64 is 1 for a packet that is only to be received by its destination ("unicast"), 0 for a "broadcast" that is to be received by all interfaces it reaches.

The remainder of the second byte, together with all of the third byte, is the flow number 65, which is similar to an ATM Virtual Channel Identifier (VCI). Note that, as with ATM, packets on different flows may be interleaved. In the case of broadcast packets, the flow number will be the same for all recipients (unlike the VCI in an ATM point-to -multipoint call), so must be allocated in a way that ensures uniqueness. Broadcast background packets are only used for segment management.

The fourth byte in the case of the last fragment of a packet (one with e=l) is the number of data bytes 66, which must be in the range 4 to 244 inclusive. For fragments with e=0 this byte is omitted and the number of data bytes is always 240. Usually the last four data bytes in a fragment with e=l will be a CRC, calculated in the same way as an Ethernet Frame Check Sequence, so the number of bytes of user data will be 0 to 240.

The last byte of the header is the Header Error Check 67, which is calculated in the same way as the HEC in the header of an ATM cell.

It would be possible to carry connectionless packets such as IP datagrams directly without fragmenting them or assigning a flow number to them, in a similar way to direct links (see Fig. 16 and description below), for instance by using 254 (OxFE) as the value for the IP flag 112 and restricting forwarding count values to the range 0 to 253, but this would require either a larger forwarding buffer 14b or buffering all IP packets in the dRAM of every node they pass.

Fig. 11 shows how a number of nodes, each comprising a network interface like the network interface 10, may be connected together to form network segments.

The rectangles represent switches, which are assumed to be connected to a larger network through additional links not shown in the diagram, and each circle represents a node.

Five nodes 72 to 76 form a "singly-connected" segment which is connected to a switch 71 at one end; this configuration might occur where five pieces of equipment share a structured wiring outlet, or where five sets of public address loudspeakers or CCTV cameras are distributed along a space such as a railway platform. The link between switch 71 and node 72 carries all the traffic between any of the nodes and the rest of the network (not shown), but not any of the traffic between two of the nodes. In all five nodes 72 to 76, both outgoing signal streams (i.e. to the left and to the right in Fig. 11) are synchronised to the incoming stream in the direction from the switch 71 (i.e. from the left). Thus all streams get their timing from the switch 71; in the direction away from the switch (i.e. left to right in Fig. 11), each node synchronises its outgoing stream directly to the incoming stream, while in the opposite direction the incoming stream from the right is synchronised by the upstream node to the outgoing stream to the right, which has the same timing as the outgoing stream to the left. Hence, at each node and in both directions, there is a defined phase relationship between the incoming and outgoing allocation periods.

As an example of how background fragments are addressed, a fragment being sent from node 72 to node 75 would be placed in the background FIFO of the transmit buffer 17 in node 72 for the direction towards node 73, with forwarding count 3. The transmit logic 15 decrements the count so the fragment sent on the link has forwarding count 2. In node 73, the fragment is received by the receive logic 11 and, because it has a nonzero forwarding count, is written to the FIFO in the forwarding buffer 14b; the transmit logic 15 decrements the count and sends it with forwarding count 1. The same happens in node 74, except that the forwarding count is 1 less. In node 75, the receive logic 11 finds that the forwarding count is zero, so puts the fragment in the background FIFO in the receive buffer 13 and not in the forwarding buffer 14b. The fragment is therefore forwarded by nodes 73 and 74 and received by node 75, and not seen at all by node 76.

Eight nodes 81 to 88 form a "doubly-connected" segment which is connected to the switch 71 at both ends; this might occur where eight pieces of equipment share a pair of structured wiring outlets, or to connect eight sets of public address loudspeakers or CCTV cameras. Traffic between the nodes and the rest of the network is shared between the two links to the switch 71 from nodes 81 and 88. If any one link fails, all the nodes still have access to the larger network; similarly, if any one node fails, all the remaining nodes still have access to the larger network.

When a failure occurs, all nodes are notified immediately and can re-connect media streams that will have been interrupted. In the case of important media streams, two copies can be sent by different routes so that in the event of a failure there will be no interruption. The switch 71 chooses one of the ports, say the one to which node 81 is connected, as the source of synchronisation, and the nodes synchronise their outgoing signal streams to the signal stream from that port in the same way as on a singly- connected segment. Thus node 88 is still synchronised to the switch 71, but not as tightly as node 81, in fact with about 8 times as much tolerance in the phase relationship, which must be allowed for when allocating slots in which foreground packets received on the link between node 88 and the switch 71 will be forwarded.

Four nodes 91 to 94 form a segment which is connected to the switch 71 at one end and a different switch 95 at the other end. This provides added resilience because the nodes will still have access to the larger network if one of the switches fails. The switches negotiate (using best effort packets passed along the link; note that best effort traffic can be forwarded even if the links are not synchronised) which will be the source of synchronisation for the segment and how they are synchronised to each other or to a common reference, as follows. Each switch informs the other of its ultimate timing reference and how accurately it can synchronise to the reference, which will depend on how many intermediaries there are between it and the reference and how well each of them synchronises to the next. If they have different references, a protocol can be followed which will change one to match the other, for instance if one of them is on an isolated subnetwork that is using a local clock for lack of any better reference, it can switch to being synchronised (via the new segment) to the other switch's reference. This allows an upper bound to the tolerance in the phase relationship on the link to the other switch to be calculated.

The diagram also shows a direct link 96 between the two switches 71 and 95.

This link may use the same format (described above) as the other links, or the switches may negotiate the use of a more appropriate format, detailed below.

Like network interfaces, switches provide one-to-many routing of media packets and one-to-one routing of background fragments. Broadcasting of background fragments is not supported; in the network interface 10 it is only used for segment management messages.

Fig. 12 shows the switching fabric of a switch in accordance with the present invention. The switch comprises a control computer (not shown) which is responsible for implementing the management protocols and configuring the various tables 102, 106, 108 which control the switching fabric accordingly. In addition to the physical (external) ports, there is an internal "port" implemented in the background buffer memory 105 which connects the control computer to the switching fabric so that it can exchange protocol messages with other equipment on the network.

The control computer handles all the setting up and clearing down of calls through the switch, but does not take any active part in the forwarding of foreground or background packets on links that use the present invention. It can therefore be similar to the control computer 8 in the network interface 10, as shown in Fig. 13, although it could also be more like a conventional PC motherboard. The sdRAM 136 does not include any media buffers, so has more space for the additional information that will be needed to support connections on the increased number of ports. Which FPGA IC 130 is appropriate will depend on whether it includes some or all of the logic for the switching fabric, which would otherwise be implemented in a separate FPGA. The control computer sends and receives packets via the background buffer memory 105 shown in Fig.12; it does not need an RBR service so does not have a connection to the foreground buffer memory 103.

There is receive logic 101 for each port, which is similar to that in the network interface 10 except as noted in the rest of this paragraph. No routing table is required for the foreground data (since all foreground data will be forwarded through one of the switch's other ports); all incoming foreground packets are written to the foreground buffer memory 103, which has an area for each input. As with the network interface 10, the address to which each byte is written reflects its position in the allocation period. The slots map entry for each slot start is only 1 bit long being 1 if the byte is a slot start and 0 else. Background fragments are written to a FIFO 104 from which each fragment is copied to the background buffer memory 105; copying does not begin until the whole fragment has been received. The background buffer memory 105 contains a FIFO for each output, including the internal "output" to the control computer. A background routing table 106, indexed by the flow number from the packet header (like an ATM routing table), shows to which port's FIFO to write it and what flow number should be in the header when it is output.

The transmit logic 107 for each port is also similar to that in the network interface 10. The transmit slots map and routing table 108 shows where each slot begins and where in the foreground buffer 103 to look for the packet that will go in it. No routing decisions are required for background fragments, which are simply copied from the port's FIFO in the background buffer memory 105.

In the simplest implementation, any port that is not operating according to the invention copies all Ethernet packets it receives to the control computer's FIFO in the background buffer 105 via its FIFO 104. Its own FIFO in the background buffer 105 holds Ethernet packets, which can only be written there by the control computer. This allows the control computer to negotiate details of the format to be used with the link partner (using AES51 negotiation packets, which are standard Ethernet packets) when the link first comes up, and also allows it to route Ethernet packets or IP datagrams including over background circuits in which the encapsulation may be similar to that specified in RFC2684 (multi-protocol over ATM AAL5) and the method of setting up the connections similar to RFC2225 (classical IP and ARP over ATM). However, the rate at which such packets could be forwarded would be limited because the entire packet has to be copied from the control computer's FIFO in the background buffer memory 105 to the destination port's FIFO in the same memory. In a more sophisticated implementation, the receive logic 101 and routing table 106 could be configurable such that most Ethernet packets and IP datagrams would be routed directly to the output port's FIFO in the same way as background fragments, or a separate IP routing engine could be included, either connected via the background buffer 105 in the same way as the control computer or connected (in parallel with the background buffer) directly to the busses serving the input FIFOs 104 and the transmit logics 107.

On a direct link between switches, such as 96 (see Fig. 11), the use of a different format than that used on segments may be negotiated.

In this embodiment the transmit logic 107 does not use admin bytes 23, although it is possible that they could be used. They are required on a segment because the background FIFO in the forwarding buffer 14 of the network interface 10 may be quite small, perhaps only IK bytes, so could quickly overflow if the downstream node is transmitting a significant amount of foreground traffic or the onward link is at a lower speed. (Note that this case does not arise in a conventional buffer insertion ring where all links are at the same speed and forwarded traffic can always use the whole of the outgoing link.) In the case of an input to a switch, provided the internal path from the FIFOs 104 to the buffer memory 105 has enough capacity, the FIFO 104 cannot overfill, and if one of the (much larger) FIFOs in the buffer memory 105 fills up this must not stop traffic destined for other ports, as it would if fragments for the overloaded output were held in the FIFO 104.

Figs. 14 and 15 show the format of best effort fragments. This is similar to the format on a segment (described above in conjunction with Figs. 9 and 10), but the forwarding count 61 and u flag 64 are omitted and the flow number 65 is larger. The size of the flow number is negotiated when the link is established; for 14-bit flow numbers the second byte 111 is omitted, while for 30-bit flow numbers there are two such bytes. The flow number may be partitioned as in ATM networks, with the high part being a VPI and the low part a VCI. In all cases, the most significant 6 bits of the flow number 65 must not be all-ones.

The carriage of IP datagrams on the background layer, without fragmenting them or assigning a flow number to them, may also be negotiated at link establishment. The negotiation includes choosing which versions of IP are supported. Fig. 16 shows the format of the start of an IP datagram; the first byte 112 contains the value 3F (hex), which is different from an idle byte and also cannot be the first byte of a fragment. The IP datagram then follows immediately; the most significant 4 bits of the first byte 113 show the IP version, which must be a value the link partner has signalled that it supports. The length is encoded in the header of the IP datagram; for version 4 it is in the third and fourth bytes, as specified in RFC 791, while for version 6 it is 40 more than the value in the fifth and sixth bytes, as specified in RFC 2460.

Other kinds of connectionless packet, such as Ethernet packets, could be encapsulated in a similar way to IP datagrams. In all cases, connectionless packets and datagrams are routed in the same way as packets received on links that are not operating in accordance with the invention.

Link management

In both embodiments, the transmit/receive slots maps and routing tables 12, 16; 102, 106, 108 for each link are written by the control computer and co-ordinated with the unit (e.g. switch or network interface) at the other end of the link by the exchange of signalling messages which are carried in background data packets on flow number 1 (which is reserved for them). Alternatively, there may be a central control computer that performs a foreground call admission function on behalf of network interfaces and/or switches in its domain. When a new foreground call is requested by an application, the network interface in the host may request admission of the call by the central control computer. The central control computer stores records of all calls admitted, routes of those calls across its domain and the slots assigned to the call at each network interface. In response to a new request the central control computer uses its records to determine if the request is admissible (e.g. by checking whether or not there is sufficient bandwidth along any route across its domain), and, if so, decides which route is to be used and the slot(s) that are allocated to that foreground call at each network interface. The central control computer then informs the requesting network interface accordingly, and also informs all interfaces along the chosen route of the assigned slot(s). Network interfaces receiving such signalling messages from the central control computer configure their transmit and/or receive slots map accordingly.

Call connection and routing is similar to ATM signalling (ITU-T

Recommendation Q.2931), including the way in which flow numbers for background data are chosen.

Administration of slots is as follows when call setup is negotiated by network interfaces. Note that the or each downstream node must always know where the slot starts are, even for flows it will not be forwarding or receiving, in order to parse the incoming stream correctly.

In each network interface en route, slots need to be added to the receive and (for all except the destination) the transmit slots map when a route is set up for a foreground flow, and removed when it is cleared down. They may also need to be moved, for instance to de-fragment the space occupied in order to allow a large slot to be allocated.

The basic procedure is as follows: (a) upstream node sends message detailing changes required;

(b) downstream node loads the new allocation into its logic;

(c) downstream node sends message showing that it is ready for the change; (d) upstream node switches its logic to use the new allocation; and

(e) downstream node sees the allocation number in the type and format field 36 of the frame header change in incoming frames.

A "change" will be one of: (i) add slots for a new flow;

(ii) add duplicate slots for an existing flow;

(iii) remove original slots (leaving the duplicated ones) for a flow; or

(iv) remove all slots for a flow.

The messages are a ChangeAllocation request in step (a) and its acknowledgement in step (c). The request can specify (ii) and (iii) directly, and invoke "pending" requests previously specified as part of the call set-up process for (i) or the call clearing process for (iv).

During call set-up, a FindRoute response or confirmation which refers to a foreground flow in the same direction as the message specifies the slots the flow will occupy; the recipient is expected to remember this information until the allocation has been removed, and initially it forms a "pending" addition to the allocation. In other embodiments the recipient informs the sender which slots can be used for the foreground packets of the call.

A request to clear down a call is a "pending" removal of the allocation for all foreground flows in either direction that are part of the call.

If the recipient of a ChangeAllocation request does not recognise the pending change to which the message refers, it sends a negative acknowledgement indicating that the allocation used on the link should be left unchanged; the most likely cause is that an earlier message was lost and the time-out for its repetition (the acknowledgement not having been received) has not yet expired. ChangeAllocation request

The message begins with 1 octet containing a serial number, which is 1 for the first request sent after the link is established and incremented for each new request thereafter. The low bit of the serial number is the allocation number for the new allocation; in some cases (e.g. where a change has been refused) the increment may need to be 2 rather than 1.

The message may contain any number of Information Elements each specifying one of the changes (i) to (iv) listed above for a particular flow.

Note that there may be pending changes that are not mentioned, in which case they remain pending. For instance, slots may have been allocated to a new call which overlap existing slots, in which case the new call's allocation remains pending until the existing slots have been moved out of the way.

ChangeAllocation acknowledgement

The acknowledgement message contains the same serial number as in the request. A positive acknowledgement does not contain any other information. A negative acknowledgement contains a code indicating the reason why the downstream node does not accept the request.

. — o— 0— o- —

The invention is particularly useful for, but not limited to, applications in which a network carries both time-critical traffic, such as live audio or video or telemetry data which is part of a control loop, and also best-effort data such as file transfers and transaction data and access to web pages.

Application areas include, but are not limited to: carriage of audio and video in and between broadcast studios and recording studios; distribution of radio and TV signals to broadcast transmitters and direct to consumers via telecommunications networks; distribution of audio and video around the home and around hotels, cruise ships, aeroplanes, etc; voice telephony; sound reinforcement; public address; CCTV; and control systems which cover large areas, such as for power generation.

Although the embodiments described herein have used an FGPA to implement the logic, it will be appreciated that the invention can be implemented in other ways. For example, the invention could be implemented in the form of an

ASIC. Another alternative is for the invention to be implemented in one or more bespoke silicon integrated circuits.

As used herein and as shown in the drawings the terms "receive" logic, "transmit" logic and "copy" logic are purely terms of convenience to aid understanding of the invention. In reality there is likely to be just one piece of logic stored and operated by an integrated circuit; this one piece of logic would incorporate the functionality of these various parts.

Although the embodiments of the invention described with reference to the drawings comprise computer apparatus and methods performed in computer apparatus, the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate between source and object code such as in partially compiled form, or in any other form suitable for use in the implementation of the methods according to the invention. The carrier may be any entity or device capable of carrying the program. For example, the carrier may comprise a storage medium, such as a ROM, for example a CD ROM or a semiconductor ROM or EPROM, or a magnetic recording medium, for example a floppy disc or hard disk. Further, the carrier may be a transmissible carrier such as an electrical or optical signal that may be conveyed via electrical or optical cable or by radio or other means.

When the program is embodied in a signal that may be conveyed directly by a cable or other device or means, the carrier may be constituted by such cable or other device or means. Alternatively, the carrier may be an integrated circuit in which the program is embedded, the integrated circuit being adapted for performing, or for use in the performance of, the relevant methods.