Routing over large clouds

Details Routing over large clouds Routing over large clouds

1999-07-06

2004-03-23

Patel, Ajit (Department: 2664)

Multiplex communications

Pathfinding or routing

C370S401000

Reexamination Certificate

active

06711152

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to a method and apparatus for establishing communication over a telecommunications network and, more particularly, to a network comprising fast switches operating at the datalink layer and interconnecting network layer routers.
BACKGROUND OF THE INVENTION
As communication networks grow in both size and scale, the speed at which packets need to be forwarded becomes higher and higher. The traditional approach to achieve higher switching speeds has been to build fast switches that operate at the datalink layer (otherwise known in the art as layer
2
of the seven-layer OSI model). A more recent trend, spurred on by the dramatic growth of the Internet, has been to build faster network layer (layer
3
) routers that have more and more forwarding capacity. Despite the tremendous amount of investment today into fabricating higher speed routers, there are several advantages to combining layer
2
switching and layer
3
forwarding. These include the ability to exploit efficient layer
2
switching, the reduction in router capacity requirements, the ability to provision and manage layer
2
and layer
3
capacity separately, and the ability to share resources with other services. The Internet Protocol (IP) utilized by routers emphasizes efficient transport of best-effort flows and support for large-scale networks. The simpler the model for forwarding in IP, the more likely it is to scale in speed and the number of routes. On the other hand, services that require stringent quality-of-service may want to take advantage of a layer
2
infrastructure that has the ability to support per-flow queuing and scheduling mechanisms, as well as packet forwarding capability.
Asynchronous Transfer Mode (ATM) networks, for example, have become the technology of choice for the Internet backbone because of its ability to support various levels of quality/class of service and because of its speed and scalability over distance. ATM is a connection-oriented layer
2
protocol which utilizes fast cell switching to provide data rates that scale from 25 Mbps up to 622 Mbps and greater. ATM switches store state information to manage a virtual circuit between the source and the destination. The use of connection-oriented virtual circuits allows packets to be divided into smaller, fixed length cells, which minimizes the delay in forwarding data and provides high performance operation.
The incentive to operate IP over an ATM backbone, however, has been complicated by various internetworking issues arising between IP and ATM. The simple approach of having all of the routers connected to the ATM cloud peer with each other resulting in N
2
adjacencies, does not scale as the size of the routing tables and the routing overhead grow unreasonably large for network sizes of interest. During the past few years, these issues have been addressed by the Internet Engineering Task Force (IETF), ATM Forum, ITU-T and many industry leaders. See, e.g., Cole et al., “IP over ATM: A Framework Document,” Internet Draft (draft-ietf-ipatm-framework-doc-08.txt), Feb. 23, 1996. As a result, a variety of approaches have been proposed to employ ATM in an Internet backbone.
In particular, the IETF is currently studying an address resolution protocol known as the Next Hop Resolution Protocol (NHRP). See Katz et al., “NBMA Next Hop Resolution Protocol (NHRP),” Internet Draft (draft-ietf-rolc-nhrp-04.txt), May 1995. This protocol maps IP addresses to the corresponding ATM addresses that are located across subnetwork boundaries so that paths across distinct ATM clouds may be realized. NHRP, however, raises a number of concerns that motivate the present invention. The NHRP address resolution process adds latency to packet forwarding. In addition, the NHRP model employs servers to process NHRP messages and which must maintain state associated with each NHRP reply that it generates. These servers represent a potential bottleneck, as well as raise issues with regard to scaling and reliability. Furthermore, under certain conditions, NHRP can introduce the possibility of stable routing loops when used between two routers.
Other proposals for combining layer
2
switching with layer
3
routing include Ipsilon's IP switching, Toshiba's Cell Switch Routing (CSR), Aggregate Route-based IP switching (ARIS), and the emerging Multi-Protocol Label Switching (MPLS). In each of these proposals, every switch participates in IP routing, although each of the proposals use different variations in the way in which switched paths are established and used. A concern with these approaches is that they fail to maintain architectural independence between the layer
2
and layer
3
networks. This coupling between layers is undesirable, particularly in a large provider network where the layer
2
network may be designed for multiple services and is not necessarily optimized to meet the needs of the IP layer. The above approaches also limit deployment flexibility in that, for example, the scope of the layer
2
and layer
3
networks may necessitate hierarchical approaches to routing. Hybrid switches require support for both ATM and MPLS protocols on every switch, which introduces both architectural and management complexity.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide an architecture that combines layer
2
switching with layer
3
forwarding and which scales to large autonomous systems.
It is another object of the present invention to retain architectural independence between the layer
2
switched network and layer
3
connectionless networks in order to allow for independent design and evolution of the networks.
It is another object of the present invention to avoid the overhead typically associated with address resolution, which can introduce latency and exacerbate the problems of out-of-order delivery of packets in the network.
It is another object of the present invention to provide an architecture that ensures connectivity among the routers and allows for the possibility of shortcut setup failure given that virtual circuit connection resources are limited.
It is another object of the present invention to keep the protocol, storage, and computational overhead to a minimum and to build on existing tested routing protocols allowing the present invention to work with existing router hardware.
It is another object of the present invention to provide for incremental deployment and ease of migration.
The present invention achieves these objectives by providing a robust and efficient architecture for routing in a very large autonomous system where many of the layer
3
routers are attached to a common connection-oriented layer
2
subnetwork, such as an ATM network. In a preferred embodiment of the invention, a permanent topology of routers coupled to the subnetwork is connected by permanent virtual circuits. The mesh of virtual circuits can be as sparse as a spanning tree, but will normally consist of a denser set of connections for reliability. The routers use extensions to OSPF (Open Shortest Path First) mechanisms to calculate optimal paths in the permanent topology. The routers can further take advantage of both intra-area and inter-area shortcuts through the layer
2
network to improve network performance. The routers pre-calculate shortcuts using information from link state packets broadcast by other routers and store the shortcuts to a given destination in a forwarding table, along with corresponding entries for a next hop along the permanent topology. The present invention allows the network to continue to operate correctly if layer
2
resource limitations preclude the setup of additional shortcuts, if for example the necessary connection capacity is temporarily in use. Packets can still make use of the virtual circuits in the permanent topology if a shortcut cannot be setup.


REFERENCES:
patent: 5408469 (1995-04-01), Opher et al.
patent: 5497368 (1996-03-01), Reijnierse et al.
patent: 5583862 (1996-12-01), Callon
patent: 5699347 (1997-12-01), Cal

Affiliated with

Also associated with

Rating

Routing over large clouds does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Routing over large clouds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing over large clouds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3219409