Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-11-24
2003-11-04
Marcelo, Melvin (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S400000
Reexamination Certificate
active
06643287
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to techniques for forwarding data packets on networks and is more particularly related to a technique for forwarding encapsulated data packets on a network in which network nodes are in general connected by multiple parallel links.
BACKGROUND OF THE INVENTION
In digital computer networks such as the Internet, collections of data, referred to as “datagrams,” are typically transferred from node to node over the network in packets. Each packet of data typically includes a header portion and a data portion. In accordance with the common Internet protocol (IP), the header portion typically includes a 32-bit source identifying portion which identifies the source node that originated the packet and a 32-bit destination identifying portion which identifies the destination node to which the packet is ultimately to be transferred.
At each node, a router is used to forward the packet to the next node in the path toward the destination node. When a router receives a packet, it examines the destination address in the packet header. It then searches its locally stored routing table to determine the next node to which the packet should be transferred in order to ensure that it will reach its destination, typically along the shortest possible path. The router then forwards the packet to the next node identified in the routing table. This process continues at each successive node until the destination node is reached.
In many cases, in such a datagram IP network, when forwarding an IP packet, there are situations in which there are two or more choices for the next step or “hop” that the packet can take.
FIG. 1
contains a schematic block diagram of a conventional IP packet forwarding network
10
. The network
10
includes multiple nodes
12
connected by links
13
. Referring to
FIG. 1
, the case in which IP packets are forwarded from node A to node F, for example, is considered. In this situation, node A will forward the packet to node B. Node B will then have a choice; it can forward the packet via either node C or node D.
In general, multiple hosts
14
are coupled to each node A and F. A host
14
coupled to node A may have a sequence of multiple IP packets destined for another host
14
attached to node F. It is desirable to keep the packets associated with any one host-to-host flow in order. This is important to improve the efficiency of communication. For example, in many cases, the hosts
14
may be running Internet applications over the Transmission Control Protocol (TCP), and TCP may make use of “slow start.” When applications are making use of TCP slow start, if packets are delivered out of order, the TCP implementation assumes that the misordering of packets is caused by congestion in the network. In response, the rate of traffic transmitted may be reduced. If in fact there is no congestion in the network, then this will result in less efficient use of the network.
Typically, IP routers solve this problem by choosing between multiple equal-cost choices for the next hop for a particular packet. The router typically performs an analysis of the packet header contents to assign each packet to a link. Usually, this involves a hash function of the five-tuple of fields in the IP header (source IP address, destination IP address, protocol, source port number, destination port number) or a subset of these fields, such as source IP address and destination IP address. A hash function is designed to perform a computation on one or more data words and return a unique data word of shorter length. For example, a hash function performed on two 32-bit IP addresses may divide the combined 64-bit word by a constant and return as a result the value of the reminder in fewer bits, e.g., five. Other hash procedures include the use of a cyclic redundancy check (CRC) and/or the use of a checksum.
Each time a hash procedure is performed on the same initial values, the same result is obtained. This ensures that packets associated with any one source/destination pair always take the same path, while simultaneously allowing different packets to take different paths. As noted above, sometimes additional fields may be used for the hash. It is noted that any packets belonging to the same flow of packets, i.e., packets which should be kept in order, will also contain the same protocol field in the IP header. Packets which contain a different value in the protocol field may therefore be safely transmitted on a different path. Similiarly, if the protocol field indicates that the next higher level protocol is TCP, then packets which contain different TCP port numbers can be routed on different paths. For these reasons, it is common for the hash to also take account of the protocol and port fields.
Thus, referring to
FIG. 1
, in general, multiple hosts
14
attached to node A send IP packets to multiple hosts
14
attached to router F. Under the technique described above, packets from any one source/destination pair will always be transmitted over the same path, i.e., via either router C or router D. However, the packets averaged over all of the source/destination pairs will be split, with some being sent via node C and some being sent via node D. This allows more efficient loading of the network
10
by splitting traffic among multiple available paths.
As the demand for data network services increases, it is becoming increasingly common for the interconnection between any two nodes to include multiple parallel links. Using multiple links increases the total bandwidth available for data transmission. Also, using multiple links allows for the possibility that if one link fails, there will still be a path through the network between any two nodes.
FIG. 2
is a schematic block diagram of a network
100
which includes multiple links
113
between nodes
112
. Specifically, the nodes B, C, D and E in the core of the network
100
are shown interconnected using two links
113
rather than a single link.
In this case, the same technique as described above for forwarding packets can be used. In particular, node B can perform a hash on the IP source and destination addresses. In this case, node B has four choices for possible links to use in forwarding a packet toward node F. Node B can therefore use a hash function with four possible output values. Each of the four links is considered a possible choice for the next hop. In this case, as in the previous case, packets for any single source/destination pair will always go via the same link, i.e., via either one of the two links to C or one of the two links to D. However, the packets averaged over all of the source/destination pairs will be split, with some being sent via each of the four links. This allows for more efficient loading of the network by splitting traffic among multiple available links in addition to multiple available paths.
Traffic engineering refers to the issue of distributing traffic throughout a network to ensure efficient use of network resources. Typically, this implies making choices of paths used by traffic to make careful and intentional tradeoffs between taking the minimum distance path and using lightly loaded links. There are two main issues to be considered in traffic engineering. First, it should be determined which set of paths are available between any ingress node n
i
and egress node n
e
in the network. Also, for any particular packet between ingress node n
i
and egress node n
e
, it should be determined which of the available paths to take.
Traffic engineering methods can be divided into two classes: connection-oriented methods and connectionless methods. Connection-oriented methods make use of some sort of connection set-up to determine which path is used between the ingress node n
i
and the egress node n
e
. Connectionless methods make use of some other method to determine which path is used between the ingress node n
i
and the egress node n
e
, such as, for example, adjusting the metrics assigned to each link as used in the route computation.
Where connection-oriented methods a
Callon Ross W.
Renwick John K.
Boys Donald R.
Central Coast Patent Agency Inc.
Do Nhat
Marcelo Melvin
Pluris, Inc.
LandOfFree
Apparatus and method for forwarding encapsulated data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for forwarding encapsulated data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for forwarding encapsulated data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3165198