Fast scaleable methods and devices for layer four switching

Details Fast scaleable methods and devices for layer four switching Fast scaleable methods and devices for layer four switching

1998-07-15

2001-04-03

Olms, Douglas (Department: 2732)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S238000

Reexamination Certificate

active

06212184

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to the field of electronic digital communication, and more specifically, to devices and methods for routing data packets.
2. Description of Related Art
With everyone building Web Sites, Internet usage has been expanding at a rate more commonly associated with nuclear reactions. Internet traffic is exploding because of a growing number of users as well as a growing demand for bandwidth intensive data. Multimedia applications, for instance, can easily consume megabytes of bandwidth. To keep up with increased traffic, link speeds in the Internet core have been increased to 622 Mbps, and a number of vendors are providing faster routers.
A traditional router performs two major tasks in forwarding a packet: looking up the packet's destination address in the router database, and switching the packet from an incoming link to one of the outgoing links. With recent advances such as those discussed in N. McKeown et al., “The Tiny Tera: A Packet Switch Core,”
IEEE Micro,
January/February 1997, pp. 26-33, and J. Turner, “Design of a Gigabit ATM Switch,”
Proc. SIGCOMM
97, October, 1997, the task of switching is well understood, and most vendors use fast buses or crossbar switches. Several new algorithms have been developed recently for address lookup as well. See, for example, DegerMark et al., “Small Forwarding Tables for Fast Routing Lookups,”
Computer Communication Review,
October, 1997; M. Waldvogel et al., “Scalable High Speed IP Routing Lookups,”
Proc SIGCOMM
97, October 1997; S. Nilsson et al., “Fast Address Look-Up for Internet Routers,”
Proceedings of IEEE Broadband Communications
98, April, 1998; and V. Srinivasan et al., “Faster IP Lookups using Controlled Prefix Expansion,”
Proc. ACM Sigmetrics
98, June 1998. Thus it would appear that there is no inherent impediment to building Gigabit routers for traditional data forwarding in the Internet.
Increasingly, however, users are demanding, and some router vendors are providing, a more discriminating form of router forwarding. This new vision of forwarding is called Layer 4 Forwarding because routing decisions can be based on headers available at Layer 4 or higher in the OSI architecture. Layer 4 Switching offers increased flexibility: it gives a router the capability to block traffic from a dangerous external site, to reserve bandwidth for traffic between two company sites, and to give preferential treatment to one kind of traffic (e.g., online database transactions) over other kinds (e.g., Web browsing). Layer 4 switching is sometimes referred to in the vendor literature by the phrase “service differentiation”. Traditional routers do not provide service differentiation because they treat all traffic going to a particular Internet address in the same way. Layer 4 Switching allows service differentiation because the router can distinguish traffic based on origin (source address) and application type (e.g., web traffic vs. file transfer).
Layer 4 Switching, however, does not come without some difficulties. First, a change in higher layer headers will require reengineering the routers, which is why routers have traditionally used only Layer 3 headers. Second, when data is encrypted for security, it is not clear how routers can get access to higher layer headers.
Despite these difficulties, several variants of the Layer 4 switching have already evolved in the industry. First, many routers implement firewalls (see W. Cheswick et al., “Firewalls and Internet Security,” Addison-Wesley, 1995) at trust boundaries, such as the entry and exit points of a corporate network. A firewall database consists of a series of packet filters that implement security policies. A typical policy may be to allow remote login from within the corporation, but to disallow it from outside the corporation. Second, the need for predictable and guaranteed service has led to proposals for reservation protocols like RSVP (L. Zhang et al., “RSVP: A New Resource Reservation Protocol,
IEEE Networks Magazine,
September 1993) that reserve bandwidth between a source and a destination. Third, the cries for routing based on traffic type have become more strident recently—for instance, the need to route web traffic between Site
1
and Site
2
on say Route A and other traffic on say Route B.
FIGS. 1A and 1B
illustrate some of these examples.
These figures schematically illustrate filters that provide traffic sensitive routing, a firewall rule, and resource reservation. The first filter 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 filter blocks traffic from an experimental site S
2
from accidentally leaving the site. The third filter 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; here X and Y are prefixes.
Once users have gotten used to the flexibility and features provided by firewalls, traffic reservations, and QoS (Quality of Service) routing, it is hard to believe that future routers can ignore these issues. On the other hand, it seems clear that the ad hoc solutions currently being deployed are not the best, and cleaner and more general techniques are possible. For example, a cleaner solution to the traffic sensitive routing and reservation problem would be to push some form of “traffic classifier” into the routing header to determine application requirements without inspecting higher layer headers. But whatever the final solutions will be, it seems clear that future routers will need to forward at least some traffic based on a combination of destination address, source address and some other classifier fields, whether they are in the routing (Layer 3) or higher layer (Layers 4 and up) headers.
A typical database today contains only a few (10-100 typically) filters. However, if we consider that typical backbone routers now have 40,000 prefixes, and if we qualify each destination prefix with even a few port numbers (e.g., for QoS routing) or source prefixes (e.g., for resource reservation between sites in a Virtual Private Network), it is not hard to imagine the need for several hundred thousand filters. Today, even firewall processing with 10-100 filters is generally slow because of linear search through the filter set, but is considered an acceptable price to pay for “security”. Thus the problem of finding the best matching filter for up to 100K filters at Gigabit speeds is an important challenge.
In traditional message forwarding in an Internet router, each router maintains a forwarding database, which is consulted by the router to determine the outgoing link on which the message is forwarded. The computational problem of determining the outgoing link based on the message's address is called the address lookup problem.
Consider a hypothetical fragment of the Internet linking users in Europe with users in the United States. If a user in Paris, named Source, as shown on the left in
FIG. 2
, wants to send an email message to another user in San Francisco, then Source will send its message to a router R
1
, say, in Paris. The Paris router may send this message on the communication link L
4
to router R in London. The London Router R may then send the message on link L
2
to router R
3
in San Francisco, and finally R
3
sends the message to the destination user.
Thus, a message travels from source to destination alternating between communication links and routers, just like a postal letter travels from post office to post office using a communication channel (such as airplanes). The important question is: How does each post office decide where to forward the letter? The post offices make these forwarding decisions using the destination addresses on the letters. In the same way, routers make their forwarding decisions based on the Internet destination address that is placed in an easily accessible portion of the message called a header. Each route

Affiliated with

Also associated with

Rating

Fast scaleable methods and devices for layer four switching 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 scaleable methods and devices for layer four switching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast scaleable methods and devices for layer four switching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2458772