Router with virtual channel allocation

Details Router with virtual channel allocation Router with virtual channel allocation

1998-08-19

2003-05-13

Patel, Ajit (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S412000, C370S389000

Reexamination Certificate

active

06563831

ABSTRACT:

BACKGROUND OF THE INVENTION
Data communication between computer systems for applications such as web browsing, electronic mail, file transfer, and electronic commerce is often performed using a family of protocols known as IP (internet protocol) or sometimes TCP/IP. As applications that use extensive data communication become more popular, the traffic demands on the backbone IP network are increasing exponentially. It is expected that IP routers with several hundred ports operating with aggregate bandwidth of Terabits per second will be needed over the next few years to sustain growth in backbone demand.
As illustrated in
FIG. 1
, the Internet is arranged as a hierarchy of networks. A typical end-user has a workstation
22
connected to a local-area network or LAN
24
. To allow users on the LAN to access the rest of the internet, the LAN is connected via a router R to a regional network
26
that is maintained and operated by a Regional Network Provider or RNP. The connection is often made through an Internet Service Provider or ISP. To access other regions, the regional network connects to the backbone network
28
at a Network Access Point (NAP). The NAPs are usually located only in major cities.
The network is made up of links and routers. In the network backbone, the links are usually fiber optic communication channels operating using the SONET (synchronous optical network) protocol. SONET links operate at a variety of data rates ranging from OC-3 (155 Mb/s) to OC-192 (9.9 Gb/s). These links, sometimes called trunks, move data from one point to another, often over considerable distances.
Routers connect a group of links together and perform two functions: forwarding and routing. A data packet arriving on one link of a router is forwarded by sending it out on a different link depending on its eventual destination and the state of the output links. To compute the output link for a given packet, the router participates in a routing protocol where all of the routers on the Internet exchange information about the connectivity of the network and compute routing tables based on this information.
Most prior art Internet routers are based on a common bus (
FIG. 2
) or a crossbar switch (FIG.
3
). In the bus-based switch of
FIG. 2
, for example, a given SONET link
30
is connected to a line-interface module
32
. This module extracts the packets from the incoming SONET stream. For each incoming packet, the line interface reads the packet header, and using this information, determines the output port (or ports) to which the packet is to be forwarded. To forward the packet, the line interface module arbitrates for the common bus
34
. When the bus is granted, the packet is transmitted over the bus to the output line interface module. The module subsequently transmits the packet on an outgoing SONET link
30
to the next hop on the route to its destination.
Bus-based routers have limited bandwidth and scalability. The central bus becomes a bottleneck through which all traffic must flow. A very fast bus, for example, operates a 128-bit wide datapath at 50 MHz giving an aggregate bandwidth of 6.4 Gb/s, far short of the Terabits per second needed by a backbone switch. Also, the fan-out limitations of the bus interfaces limit the number of ports on a bus-based switch to typically no more than 32.
The bandwidth limitation of a bus may be overcome by using a crossbar switch as illustrated in FIG.
3
. For N line interfaces
36
, the switch contains N(N−1) crosspoints, each denoted by a circle. Each line interface can select any of the other line interfaces as its input by connecting the two lines that meet at the appropriate crosspoint
38
. To forward a packet with this organization, a line interface arbitrates for the required output line interface. When the request is granted, the appropriate crosspoint is closed and data is transmitted from the input module to the output module. Because the crossbar can simultaneously connect many inputs to many outputs, this organization provides many times the bandwidth of a bus-based switch.
Despite their increased bandwidth, crossbar-based routers still lack the scalability and bandwidth needed for an IP backbone router. The fan-out and fan-in required by the crossbar connection, where every input is connected to every output, limits the number of ports to typically no more than 32. This limited scalability also results in limited bandwidth. For example, a state-of-the-art crossbar might operate 32 32-bit channels simultaneously at 200 MHz giving a peak bandwidth of 200 Gb/s. This is still short of the bandwidth demanded by a backbone IP router.
SUMMARY OF THE INVENTION
Prior U.S. patent application Ser. No. 08/918,556 discloses and claims an internet router which itself comprises a fabric of fabric routers. In the primary implementation, to assure continued flow of data packets despite congestion to some destinations, each destination node was assigned a virtual network comprising a unique virtual channel in each router. Any data packet destined to a particular output was stored in a data buffer corresponding to a unique virtual channel for that destination, so congestion which blocked one data packet would not necessarily block another.
That approach is costly in buffer space and has limited scalability. In accordance with the present invention, which may be applied to any router without limitation to fabric routers, virtual networks are constructed with overlapping buffer assignments by sharing virtual channels. However, to prevent congestion in one virtual network from blocking transmissions in another virtual network, virtual networks share less than all virtual channels.
In accordance with the present invention, a router for routing data packets comprises input physical channels, output physical channels and data buffers, coupled with the input and output physical channels, for storing at least portions of the data packets. Control circuitry coupled to the input and output physical channels and the data buffers generates assignments of data packets to virtual channels which are multiplexed onto physical channels. A first data packet has access to a first set of virtual channels of size C
1
, and a second data packet has access to a second set of virtual channels of size C
2
. There is an intersection of the first and second sets of size S where 0<S<C
1
and S<C
2
. As a result, data packets may share access to multiple virtual channels to which other data packets have access, a first data packet sharing some but not all virtual channels with a second data packet.
Preferably, substantially all of the data packets route over a plurality of virtual networks, each virtual network i using a subset of size C
i
of the virtual channels. Virtual channel subsets of plural virtual networks overlap, sharing no more than S<C
i
virtual channels.
In a preferred router, the first packet routes on a first virtual network and the second packet routes on a second virtual network. All packets routed on the first virtual network share the first set of virtual channels and all packets routed on the second virtual network share the second set of virtual channels.
Preferably, each virtual network carries packets destined for a particular set of destination nodes such as a pair of nodes opposite one another in a network. At least one of the virtual channels in each set of virtual channels can be determined by a destination node address, specifically by a dimensional coordinate of the destination node.
To prevent interdimension deadlock, specific turns may be disallowed in each virtual network. In one embodiment, two virtual networks are assigned to each set of destination nodes and different turns are disallowed in each of the two virtual networks. In another embodiment, a single virtual network is assigned to each set of destination nodes. Multiple turns may be disallowed in that single virtual network.
In a preferred embodiment, the control circuitry includes output controllers that correspond to the output physical channels. Each output con

Affiliated with

Also associated with

Rating

Router with virtual channel allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Router with virtual channel allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Router with virtual channel allocation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3018295