Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-10-21
2002-06-18
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395520
Reexamination Certificate
active
06408001
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of Internet Protocol Networks, and more particularly to methods for providing increased efficiency while utilizing label switching capabilities at Label Switching Routers within a Multi-Protocol Label Switching Network.
BACKGROUND OF THE INVENTION
The explosive growth of the Internet and private Intranets has resulted in a large and growing network infrastructure of Internet Protocol (IP) routers. The Internet is a packet-switched network, meaning that the data transmitted over the network is segmented and conveyed in packets. Unlike circuit-switched networks such as the public switched telephone network (PSTN), a packet-switched network is connectionless; that is, a dedicated end-to-end path does not need to be established for each transmission. Rather, each router calculates a preferred routing for a packet given current traffic patterns, and sends the packet to the next router. Thus, even two packets from the same message may not travel the same physical path through the network. This method is a type of layer three forwarding known as dynamic routing.
An IP packet is comprised of a packet data portion and an IP header. The IP header is comprised of a variety of header fields, including a source address and a destination address. The IP header, and therefore those fields which comprise the IP header, represent a transmission overhead since header bits are transported along with the actual data bits for each packet. Additionally, since IP routers forward IP packets based on each packet's destination address, each IP packet header must be parsed at a controlling microprocessor in each router through which a packet is forwarded. The destination address associated with each respective packet is accessed by the microprocessor and a forwarding lookup table is utilized to forward each packet to a next router. Despite advances associated with processor speeds, the performance of forwarding algorithms and functions at each IP router utilizes precious router processing capacity and consequently limits the forwarding capacity of the routers.
A recently developed approach for improving the capacity at an IP router is through the use of label switching. Label switching is efficiently utilized in Multi-Protocol Label Switching networks incorporating a plurality of Label Switching Routers. A Label Switching Router is a router operable to forward IP packets conventionally via layer three forwarding, and additionally, is operable to perform layer two switching if a switching label is appended to the IP packet. Label switching is initiated by first identifying, at a Label Switching Router, a plurality of IP packets with a common destination address and a common source address. If the quantity of identified packets is greater than a predetermined threshold value, then a label is issued and communicated between router peers. Subsequently, all IP packets having that same common destination address and common source address have a label appended. The label is used to define a layer two switched-packet flow through one or more Label Switching Routers. Layer two switching can significantly increase the forwarding speed when compared to layer three forwarding. This is because the router microprocessor is relieved of the tasks of parsing each packet's IP header, calculating the next hop address, and forwarding the packet.
The current approach utilized to identify opportunities to define a label, and consequently a switched-packet flow between neighboring Label Switching Routers, is to quantify the packet transport density between neighboring Label Switching Routers for each source/destination node pair. The quantified packet transport density for each new source/destination node pair is compared to a packet transport density threshold value. If the corresponding packet transport density is greater than the packet transport density threshold value, then a new label is created, issued, and conveyed to neighboring Label Switching Routers, and is utilized to transport the switched-packet flow. Thus a new label is created for each newly identified source/destination node pair, even if a label currently in use for an previously established switched-packet flow having a common switched path through two or more neighboring routers may exist. Such a scheme utilizes a large quantity of labels, resulting in a correspondingly high switching cost for each separately established and identified switched-packet flow.
SUMMARY OF THE INVENTION
Switching costs are reduced and packet transport efficiencies are increased by using a multiple packet transport density threshold values method for determining packet label assignments at a router. A router, utilizing the method of the present invention in a destination based merging approach, first detects a plurality of unlabeled packets having a common destination address. The router then determines the quantity of unlabeled packets conveyed through the router, and having the common destination address, over a given period of time. The resulting quantity is called the packet transport density. The router maintains at least two packet transport density threshold values with which to compare the calculated packet transport density. If the calculated packet transport density is greater than the larger of these two threshold values, then the packet transport density is considered so great that an independent label is issued to establish a dedicated high volume packet flow link for a labeled switching path with a dedicated label used by no other packet flows. If the calculated packet transport density is less than the smaller of the two threshold values, then the packet transport density is considered so insignificant that the most efficient method of conveying the corresponding packets is via conventional layer three forwarding.
However, if the calculated packet transport density value is between either threshold value, or is equal to either threshold value, then the packet transport density value is considered sufficiently large to warrant establishing a switched-packet flow. In accordance with one embodiment of the present invention, the router first searches for an existing label associated with an established layer two packet flow having a common downstream destination. If no such label exists, then a new label is issued to support layer two switching of the corresponding packets. If such a label does exist, then an opportunity to merge two switched-packet flows over neighboring routers was found. The two corresponding switched-packet flows may be merged without further inquiry, or in an alternative embodiment, the router may investigate the quality of service guarantees, if any, associated with the respective switched-packet flows. If the quality of service guarantees are not equivalent, then the router may optionally issue a additional label for the newly identified switched-packet flow opportunity, thus not merging the two switched-packet flows in deference to their disparate service guarantees.
Advantageously, the multiple packet transport density threshold value scheme, in accordance with the present invention, allows routers to use and maintain a smaller quantity of total labels. Using and maintaining fewer labels at network routers has at least the following beneficial aspects: (i) reduced packet processing time at each switching router since routers maintain and access fewer labels, (ii) lower switching costs as a result of fewer required label swaps at routers, and (iii) reduced overhead since the number of bits necessary to uniquely describe a smaller total number of labels is correspondingly smaller as well.
REFERENCES:
patent: 5455825 (1995-10-01), Lauer et al.
patent: 5471467 (1995-11-01), Johaan
patent: 5732080 (1998-03-01), Ferguson et al.
patent: 5748633 (1998-05-01), Lawler et al.
patent: 5790545 (1998-08-01), Holt et al.
patent: 5809027 (1998-09-01), Kim et al.
patent: 5991300 (1999-11-01), Tappan
patent: 6009097 (1999-12-01), Han
patent: 6201789 (2001-03-01), Witkowski et al.
“
Chuah Mooi Choo
Yue On-Ching
Cangialosi Salvatore
Eriksen Guy H.
Lucent Technologies - Inc.
LandOfFree
Method for determining label assignments for a router does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining label assignments for a router, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining label assignments for a router will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2939948