Explicit route and multicast tree setup using label distribution

• US 6,374,303 B1
• Filed: 11/12/1998
• Issued: 04/16/2002
• Est. Priority Date: 11/17/1997
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Wang, Zheng, Gray, Eric W., Armitage, Grenville John
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): CALDWELL, ANDREW T
• Application Number:
  US09/190,307
• Time in Patent Office: 1,251 Days
• Field of Search: 709/238, 709/242, 370/390, 370/408, 710/131
• US Class Current: 709/242
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

What is disclosed is an arrangement of field of label augmented, multi-protocol routing of data packets in a network utilizing fixed length labels that are negotiated between adjacent label routing routers in the network. Portions of each routing label may be assigned by both upstream and downstream routers in the network. Routing labels are used in lieu of conventional address headers to route data packets through said network; and by using routing labels the routers have more flexibility in routing data packets through said network and can use network links between routers that normally carry less traffic.

Claims

1. A method of increasing the efficiency of routing data packets between multiple routers in a network by adding a simple routing label to data packets being routed through said routers, said routing label being used to route said data packets between adjacent routers in said network that can handle said routing labels as well as conventional address labels that are attached to said data packets, said method comprising the steps of:

determining at each of said routers that can handle routing labels which adjacent routers in said network can place and process said routing labels on said data packets;

specifying at a first router of said routers that can handle routing labels, if required, a first portion of said routing label to be bound to and used to route each data packet that is originating at or passing through said first router to an adjacent one of said routers that handle routing labels;

sending said first portion of said routing label originating at said first router to said adjacent one of said routers that can handle routing labels to request a first label bind thereat;

specifying at one of said adjacent one of said routers, if required, a second portion of said routing label to be bound to and used to route each data packet that is originating at or passing through said first router and being directed to said adjacent one of said label routing routers;

sending said second portion of said routing label originating at said adjacent one of said label routing routers to said first router to be inserted into said routing label and used to route said data packet to said adjacent one of said label routing routers; and

said routing labels being used by said adjacent label routing routers in lieu of conventional address headers to route data packets through said network; and

by using said routing labels said last mentioned routers have more flexibility in routing data packets through said network and can use network links between said last mentioned routers that normally carry less traffic.

2. The method in accordance with claim 1 further comprising the steps of:

responding at an adjacent one of said label routing routers to said first portion of a routing label sent from said first router as a request for a label bind from another of said label routing routers that is not adjacent to said first router, but is adjacent to said adjacent one of said label routing routers, by forwarding said label bind request to said another of said label routing routers that is not adjacent to said first label routing router; and

generating the second portion of said routing label at said another of said label routing routers that is not adjacent to said first label routing router and returning it via said adjacent label routing router to said first label routing router.

3. The method in accordance with claim 2 further comprising the steps of:

periodically sending a notification message from each of said routing label routers to all adjacent routing label routers and waiting for a reply from same indicating that they can handle routing label marked data packets; and

removing routing labels at each of said routing label routers from data packets being routed to a specific, adjacent label router after a plurality of periodic notification messages are sent to said specific router and said reply is not received therefrom.

4. The method in accordance with claim 3 further comprising the step of sending a first teardown message from said first router to all adjacent routers to cease using routing labels when said first router will not process routing labels on data packets received from said adjacent routers.

5. The method in accordance with claim 4 further comprising the steps of:

sending a second teardown message from one of said label routing routers to an adjacent one of said label routing routers when a routing label originally sent from said adjacent one of said label routing routers to said one of said label routing routers is no longer required; and

sending an acknowledgment from said adjacent one of said label routing routers that received said second teardown message to said one of said label routing routers responsive to said second teardown message.

6. The method in accordance with claim 5 further comprising the steps of:

checking at each of said label routing routers each routing label and label bind request received from an adjacent one of said label routing routers to determine if said last mentioned routing label is the same as previously used; and

returning a first error message to the one of said label routing routers from which said routing label and label bind request is received if the routing label is the same as previously used.

7. The method in accordance with claim 6 further comprising the steps of:

removing said routing label attached to a stream of data packets at said first label routing router, at an adjacent one of said label routing router which assigned said last mentioned routing label to said first label routing router, before the stream of data packets travels on to another label routing router that is not adjacent to said first label routing router; and

adding a different routing label onto said last mentioned stream of data packets received at said adjacent one of said label routing routers to replace the routing label removed thereat, said different routing label having been assigned by another label routing router adjacent to said last mentioned adjacent label routing router, but not adjacent to said first label routing router, and associated with routing labels assigned by said adjacent one of said label routing routers to said first label routing router and subsequently received.

8. The invention in accordance with claim 1 further comprising the steps of:

determining at a label routing router that has received a request from an adjacent label routing router to forward data packets to more than one other adjacent label routing router in a multicast distribution of said last mentioned data packets, which other adjacent label routing routers are to be included in the label requests and binds for those other adjacent label routing routers in order to forward the multicast data packets thereto;

binding routing labels to said last mentioned multicast data packets for routing same to label routing routers that are included in the multicast distribution of said last mentioned data packets; and

sending said multicast data packets to said adjacent one of said routers that are included in the multicast distribution of said last mentioned data packets.

9. The invention in accordance with claim 1 further comprising the steps of:

receiving data packets at said first label routing router that are to be multicast via multiple ones of said adjacent, label routing routers;

binding appropriate labels to said multicast data packets at said first label routing router;

sending said multicast data packets with said appropriate routing labels bound thereto to all label routing routers adjacent to said first label routing router; and

deciding at each of said last mentioned adjacent label routing routers if that router is part of the multicast distribution, forwarding said multicast data packets if the decision is yes, and not forwarding said multicast data packets if the decision is no.