Classifications

• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L45/00—Routing or path finding of packets in data switching networks
  • H04L45/74—Address processing for routing
  • H04L45/742—Route cache; Operation thereof
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L45/00—Routing or path finding of packets in data switching networks
• • H—ELECTRICITY
  • H04—ELECTRIC COMMUNICATION TECHNIQUE
  • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
  • H04L45/00—Routing or path finding of packets in data switching networks
  • H04L45/40—Wormhole routing

Definitions

• This invention relates to routers. In particular, it relates to routers for routing Internet traffic.
• This invention primarily relates to routers provided in the vicinity of an end terminal or local area network for routing traffic either to a local terminal, or to another node in the local area network or onward to external Internet addresses.
• the bandwidth or speed of an Internet connection is usually determined by the size of the connection bandwidth but the actual bandwidth achieved is dependent upon, inter alia, the speed of the various components of the network.
• One of the components that does tend to introduce delays, and therefore limit bandwidth, is a router.
• a router for a local area network, or at a users terminal, receives data packets from the Internet and forwards them on to a users' terminal (generally a personal computer, PDA, interactive TN, mobile telephone and so on) the data is not intended for that address, it routes them onto another node in a local area network if the terminal is part of a local area network or onto another Internet node for onward distribution ultimately to another address on the Internet.
• the router also directs outgoing signals from a terminal to nodes on the local area network or wider afield.
• a typical TCP/IP data packet transmitted by an electronic system such as the Internet comprises several parts, transmitted serially.
• the first part 1 (as received, from right to left in the figure) provides the IP address of the target, ie the address where the packet is destined for.
• an IP address comprises four parts in the form A.B.C.D, where A, B, C or D may be any value between 0 and 255. This represents the unique address of the device or terminal and is generally geographical.
• the subsequent part of the TCP/IP packet represents the originating address or 'from' address 2. This is then followed by the binary data itself 3 which is typically up to 65 Kb and this then followed by various error correction information 4.
• router designs require an entire packet to be received by the router, which can take time in itself.
• the router analyses the entire packet to determine the target address and uses various techniques to determine whether the data is intended for a local terminal, a local node or for onward transmission.
• the packet is then reassembled and transmitted onwards accordingly. All of this takes time and is complex. Whilst it is adequate for slower bandwidth systems, it begins to become a problem if a higher bandwidth system are required.
• very high bandwidth may be obtained of 600 Mb/s or more and it is particularly important in these very high bandwidth systems that the router does not introduce bottlenecks or delays.
• the present invention arose in an attempt to provide an improved router, particularly for high bandwidth systems.
• a router comprising means for receiving data packets; means for sampling an address portion of the data packet before the packet enters the router; hardware look-up means for comparing the address with a look-up table while the packet is being entered into the router and means for establishing an onward transmission path to a local terminal or other node depending upon the results of the look ⁇
• a router comprising means for inputting a data packet; means for sampling and/or separating an addressed portion of the packet before it enters the router; means for establishing the next destination for the packet before or whilst the data packet is being loaded into the router and means for onwardly transmitting the packet, with address data, accordingly.
• the invention comprises at least one means for receiving a data packet; means for extracting an address from the packet; memory means for storing and subsequently transmitting the packet to a programmable logic device; means for receiving the sample for simultaneously receiving the sampled address data and comparing this with previously stored address data indicative of local and other transmission nodes; means for determining an onward transmission address for the data packet depending upon the results of the look-up, and two or more transmission ports, to which the packet is subsequently transmitted depending upon the look-up result.
• the temporary memory means comprises first in first out (FIFO) means.
• FIFO first in first out
• the look-up table preferably comprises IP address information. If the sampled address differed in other than a local part, then the packet is automatically transferred to a suitable output port where it can be ultimately transferred outwards to the Internet.
• the programmable logic device may alternatively comprise a plurality of selected memories, where subsequent ones of subsequent packets of data are applied to each memory in turn whilst the address data for that packet is analysed.
• the invention further provides a router including means for extracting a target address of a data packet, comparing it to a local address, selecting an onward path based on the comparison, and routing the packet to an output in accordance with the selection.
• a router including a plurality of memories into which data packets are temporarily stored.
• Figure 1 shows a router
• Figure 2 shows a packet of data
• Figure 3 shows an alternative router
• Figure 4 shows a mesh network of nodes
• FIG. 5 is an explanatory diagram
• Figure 6 shows a look-up means
• Figure 1 shows a router arrangement at or in the vicinity of an end user who has a terminal 10 and a data output 11 (such as a modem, Ethernet port, etc) and input 12 for receiving data from the Internet.
• a routing arrangement comprises a router 13 in the form of a programmable logic device and receiving inputs from the output 11 from the computer and also from at least one data receiver 14, 15. These are adapted to receive signals over telephone lines or wirelessly, or may be optical receivers for optical network or optical mesh networks, as described in a co-pending patent application of the applicant.
• three inputs 11, 14 and 15 are shown to the router but more or less than this may be used.
• Each of the inputs are connected to the router by means of a first respective device 16, 17 or 18 which serves to copy, or sample (i.e. extract), the initial target address part of a data packet.
• a data packet on the Internet has a first part which represents the target address in IP format.
• the signal is passed to a respective temporary memory 19, 20, 21, preferably in the form of respective FIFO devices which receive each packet and then transmits them, in the order received, to the router 13.
• the PLD 13 includes a RAM 22 into which received data is stored and transmits data to a selected one of two or more transmitters 23, 24 and 12. Note that transmitter 12 is actually the input to the local terminal so that a data packet intended for the local terminal is 'transmitted' to that terminal.
• Each transmitter is connected through a respective FIFO RAM 26, 27, 28.
• the sample or separated address data is supplied to a programmable logic device 29 which receives data from a look-up table stored in a RAM 30.
• the target address part of it is copied at 16 and transmitted to the PLD.
• the remainder of the packet is then passed to the FIFO.
• the PLD 29 compares the received address (which is in IP format A.B.C.D.) with local address data stored in the RAM.
• each part of the address Ai.Bi.Ci.Di. is compared with the local address A -B L -C -D .
• the local address is 10.53.6.259
• the target address is 10.53.6.231
• the different value of the Target Address 231 is then sent to the RAM 30.
• the RAM includes a look-up table which provides a code, typically an eight bit digital number, in response to an inputted number. For example, the number, in response to entered address 231, is 10110010. As shown in the figure, each pair of digits of this number represents routing information for a difference in a different one of the groups A, B, C and D of the four part IP address A.B.C.D.
• the PLD knowing that the difference is in part D (generally, the most local part), therefore uses the last two digits, 10, of the eight bit number N. It contains data that maps binary 10 with an outport Port 2, eg Tx23.
• the value 231 would again be sent to the RAM 30.
• the same eight bit number would be output but the digits used by the PLD 29 to determine the routing information would be
• part of the local Target Address is analysed, each part at a time, first at part A. If different, then the 'A' address is transmitted to the RAM, and no further comparison need be done on the address. If the 'A' part is the same, then the 'B' address is compared. If different, then the 'B' value is forwarded to the RAM. If the same, then the 'C part is compared, and so on. If all parts are the same, then the Target Address is the local address and the data packet can be routed directly to the local terminal.
• a local network or mesh is shown and in this example eight nodes are shown, having addresses from 00000001 to 00001000 and node 00001000 has a direct connection to the Internet. If a data packet arrives at node 110 and, after the comparison, the address at parts A, B and C of the TCP/IP routing address structure differ, then the packet is deemed to be intended for a further destination on the Internet and so is routed to a transmitter which is directly connected to the Internet, this may be for example transmitter 24 in Figure 1.
• the group D value is compared with the PLD and RAM are used as above and the PLD is provided with routing information representative of the respective transmitter 23 or 24, representative of paths Pi and P 2 from node A in the figure. So, if the address at node A is 00000100 and the destination address is 0000011 l(node B), then the PLD and look-up tabLe provides information that the packet must be passed to the relevant transmitter that transmits over path PI (note that the routing system described is particularly useful for optical mesh systems having a plurality of transmitters and receivers as described in the applicant's co-pending application no .).
• the look-up table includes information that this must be sent on a different transmission path, P2. If the destination address is 00000100, ie node D, then the quickest transmission path from node A to node D is via node B. The look-up table therefore contains information that the message must be routed on path PI to node B. At node B, a different look-up table is provided. The PLD and look-up table knows that the packet must be passed on path P3.
• the RAM 22 may be 24 bit or 32 bit, for example.
• FIG. 3 shows an alternative embodiment of a router.
• the RAM within the router is divided into four (or more) units, RAM A, RAM B, RAM C and RAM D.
• each data packet arrives its address can be separated off as before and analysed at the PLD 39.
• This has an associated RAM 40 which again includes a look- up table as before.
• Each data packet is then stored in a respect one of the different rams, RAM A to RAM D.
• Two flags are associated with each separate RAM module. These operate as follows.
• flag A essentially represents that RAM has data stored in it and flag B represents processing of that data.
• the flags are used to determine which RAM a subsequent packet of data from any receiver 41, 42 or 43 may use so that as data is being processed in one RAM it can be stored into the next RAM. In effect, therefore, 01 loading for any RAM, flag section, represents 'a state' , 11 represents 'loaded', 10 represents 'unloading' and 00 represents empty. Other means of representing different states may be used. Instead of the address part being separated before the router, an arrangement as shown in Figure 3 may be used in which the address part is extracted after a packet end is loaded into each RAM.
• the CPLD then chooses a memory area and after the data is loaded into the memory area, or while the packet is being loaded therein (since it is a FIFO device the beginning of a message can be extracted whilst the end is still being stored) the CPLD extracts the address and analyses it for the best route as described. The CPLD then forwards a (typically 8 bit) location word to an output part of the router which determines the best output for transmitting.
• QoS quality of service
• PLD 39 data representative of this is included in the packet and this is analysed by PLD 39. This may then be transmitted directly to a faster transmitter, or if several packets are being received, the one with the higher QoS may be transmitted onward before the one with lower QoS. This can involved deliberately delaying the slower one by retaining it in its separate RAM longer. Many other factors may be analysed.

Landscapes

• Engineering & Computer Science (AREA)
• Computer Networks & Wireless Communication (AREA)
• Signal Processing (AREA)
• Data Exchanges In Wide-Area Networks (AREA)

Applications Claiming Priority (3)

Publications (1)

Family

ID=9953462

Family Applications (1)

Country Status (3)

Families Citing this family (3)

Family Cites Families (3)

• 2003
  • 2003-02-22 GB GB0304044A patent/GB2398700A/en not_active Withdrawn
• 2004
  • 2004-02-18 WO PCT/GB2004/000657 patent/WO2004075490A1/en not_active Ceased
  • 2004-02-18 EP EP04712100A patent/EP1595366A1/de not_active Withdrawn

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events