Fast level four switching using crossproducting

Details Fast level four switching using crossproducting Fast level four switching using crossproducting

1998-05-07

2002-09-10

Chin, Wellington (Department: 2664)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S351000

Reexamination Certificate

active

06449256

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to devices and methods for routing digital communications, and more particularly to devices and methods utilizing crossproducting as an efficient caching strategy.
2. Description of the Prior Art
Internet traffic is exploding both because of a growing number of users and an increasing demand for bandwidth intensive data. While email only contributes small change, big-ticket items such as video and images can easily require megabytes of data to be transferred. To keep up with increased traffic, the speed of links in the Internet core has been increased from 45 MBPS to 155 MBPS, and established vendors as well as many startups are working to build faster routers that can handle Gigabit (1000 million bits per second) links. Thus there is a major market opportunity for high performance routers.
A traditional router that forwards a message has two major tasks: first, looking up of the message's destination address in the router database; and second, internally transferring the message to one of many possible output links. The second task is well understood with most vendors using fast busses or crossbar switches. In the last year, several new solutions have appeared to the message lookup problem as well. Thus there appears to be no impediment to building and selling gigabit routers for data forwarding in the Internet.
Increasingly, however, users are demanding, and some router vendors are providing, a more discriminating form of forwarding called “layer 4 forwarding” in which routing decisions can be based on higher level headers. In traditional terminology, link headers are called “layer 2 headers” and routing headers are called “layer 3 headers.” The protocols that ensure reliable delivery use what are known as “layer 4 headers,” while applications such as email use what are known as “layer 5 headers” and higher-numbered headers. Traditional routers only look at layer 3 headers in a message; the new breed of routers will, by contrast, base their forwarding decision on layer 3, layer 4, and even higher layer headers.
Layer 4 switching offers increased flexibility for customers. It allows traffic from dangerous external sites to be blocked, allows bandwidth to be reserved for traffic flowing between two company sites in different parts of the country, and it allows important traffic (e.g., database lookups) to be given preferential treatment when compared to less important traffic (e.g., Web browsing). Layer 4 switching allows service differentiation because traffic from a host S
1
to destination H can be given better treatment when compared to another traffic host S
2
to H. Similarly, web traffic to H can be treated differently from, for example, file transfer to H. Traditional routing does not provide service differentiation because all traffic going to a given Internet address H is treated identically.
While providing these advantages, however, layer 4 switching introduces a number of architectural complications. First, a change in higher layer headers will require reengineering of routers that have traditionally looked at only layer 3 headers. Second, with encrypted higher layer headers for security, it is not clear how routers can get access to higher layer headers.
Despite these problems, various species that fall under the genus of layer 4 switching have already evolved in the industry. First, many routers at trust boundaries, such as the entry and exit points of corporations, implement so-called “firewalls”. A firewall database consists of a series of filters on packet headers that implement security policies. A typical policy may be to allow remote login that originates within the corporation but to disallow remote login that originates outside the corporation. Second, the need for predictable and guaranteed service has lead to proposals for filters, for instance, to reserve certain bandwidth between a source and destination networks. Third, the cries for routing based on traffic type have become more strident recently (e.g., route web traffic between site
1
and site
2
on route A and other traffic on route
2
). These examples are illustrated in
FIG. 1
, which schematically illustrates a network that provides traffic sensitive routing, a firewall rule, and a resource reservation, all of which are implemented in router R. A typical set of rules for router R is shown in tabular form in FIG.
2
.
In
FIG. 2
, the first rule in the table routes video traffic from S
1
to D via L
1
; not shown is the default routing to D which is via L
2
. The second rule blocks traffic from an experimental site S
2
from accidentally leaving the site. The third rule reserves 50 MBPS of traffic from an internal network X to an external network Y, implemented perhaps by forwarding such traffic to a special outbound queue that receives special scheduling guarantees. In
FIG. 2
, X and Y are “prefixes,” as defined below.
The major problem that traditional routers face in forwarding an Internet message relates to the process of “address lookup.”
FIG. 3
is a block diagram of a hypothetical fragment of the Internet linking users in Europe with users in the United States. Consider a source user “Source” in Paris. If this user wishes to send, for example, an email message to San Francisco, the user will send its message to a router R
1
which is, for example, in Paris. The Paris router may send this message on the communication link L
4
to router R, which may be in London. The London router R may then send the message on link L
2
to router R
3
in San Francisco; router R
3
then sends the message to the destination.
This example shows that a message travels from source to destination alternating between communication links and routers in a manner analogous to the way a postal letter travels from post office to post office using some transportation channel (e.g., an airplane). In the case of a postal letter, each post office decides where to forward the letter in accordance with the destination address that is placed on the envelope containing the letter. In a similar manner, routers must decide to forward a message based on a “destination address” that is placed in an easily accessible portion of the message called a header.
Let us now consider how a traditional router forwards an incoming message by referring to the router R shown in FIG.
3
. We show a schematic description of router R in FIG.
4
. When a message arrives on link L
4
, for example, the message carries its destination address SanFrancisco in its message header. Router R is a special computer whose job is to forward all messages that are sent to it towards their final destinations. To do so, router R consults a “forwarding table” (sometimes also called a “forwarding database”). This is a table in the memory of R, which could list each possible destination and the corresponding output link. Thus, when a message to San Francisco arrives on link L
4
, router R looks up the destination address SanFrancisco in its forwarding table. Since the table says “L2,” the router then switches the entire message to the output link L
2
. It then proceeds to service the next arriving message.
Address lookup and message switching must both be done at very high speeds. The problem of message switching has become very well understood in recent years because of advances in ATM Switching Technology. On the other hand, the problem of address lookup remains difficult because Internet routers store address prefixes in their forwarding tables to reduce the size of their tables. For example, instead of storing every possible address in the United States in a table, router R of
FIG. 4
could be configured to store a smaller number of prefix entries, such as USA.CA.SanFrancisco->L
2
, USA.CA.*->L
3
, and USA.*->L
1
, if these were the only rules needed for a particular router. (For readability, routing rules such as those of this example are sometimes presented symbolically in this specification.) However, the use of address prefixes such as USA.CA.* and USA.* mak

Affiliated with

Also associated with

Rating

Fast level four switching using crossproducting does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast level four switching using crossproducting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast level four switching using crossproducting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2906720