US6295296B1 — Use of a single data structure for label forwardi…

Claim 1

Independent Claim 220 words

A label-switching router including: A) reception circuitry that receives incoming communications packets that comprise: i) network-layer datagrams including respective network-layer destination addresses; and ii) outer headers including link-layer headers, the outer header of each of at least some of the incoming packets additionally including at least one shim-header stack entry; B) a forwarding information base containing a plurality of forwarding entries, each of which is associated with a respective destination and specifies for the respective destination a link-layer header and a stack-entry sequence of zero or more shim-header stack entries containing respective labels, the stack-entry sequences associated with some destinations being empty, the stack-entry sequences associated with other destinations consisting of at least one stack entry; C) an output-packet assembler that constructs an output packet for each of a forwardable plurality of incoming packets, each of at least some of whose outer headers include at least one shim-header stack entry, the output-packet assembler constructing each such output packet by fetching a link-layer header and stack-entry sequence associated by the forwarding information base with the incoming packet's destination independently of the number of shim-header stack entries in the incoming packet's outer header and replacing therewith the part of the incoming packet's outer header down through its top shim-header stack entry; and D) output circuitry for transmitting the outgoing packets thus constructed.

Claim 2

Dependent Claim 220 words

A label-switching router including: A) reception circuitry that receives incoming communications packets that comprise: i) network-layer datagrams including respective network-layer destination addresses; and ii) outer headers including link-layer headers, the outer header of each of at least some of the incoming packets additionally including at least one shim-header stack entry; B) a forwarding information base containing a plurality of forwarding entries, each of which is associated with a respective destination and specifies for the respective destination a link-layer header and a stack-entry sequence of zero or more shim-header stack entries containing respective labels, the stack-entry sequences associated with some destinations being empty, the stack-entry sequences associated with other destinations consisting of at least one stack entry; C) an output-packet assembler that constructs an output packet for each of a forwardable plurality of incoming packets, each of at least some of whose outer headers include at least one shim-header stack entry, the output-packet assembler constructing each such output packet by fetching a link-layer header and stack-entry sequence associated by the forwarding information base with the incoming packet's destination independently of the number of shim-header stack entries in the incoming packet's outer header and replacing therewith the part of the incoming packet's outer header down through its top shim-header stack entry; and D) output circuitry for transmitting the outgoing packets thus constructed.

Claim 3

Dependent Claim 29 words

A router as defined in claim 1 wherein the outer header of each of at least some of the forwardable plurality of incoming packets includes no shim-header stack entry.

Claim 4

Dependent Claim 38 words

A router as defined in claim 2 wherein each forwarding entry specifies the link-layer header and stack-entry sequence by pointing to a data structure that contains the concatenation of the link-layer header value and the shim-header stack-entry sequence.

Claim 5

Dependent Claim 169 words

A router as defined in claims 3 wherein; A) the forwarding information base comprises: i) a prefix-based forwarding table, each of whose entries includes a network-layer-address prefix of the destinations with which that entry is associated; and ii) a label-based forwarding table, each of whose entries includes a label that the router associates with a network-layer-address prefix of the destinations with which that entry is associated; B) if an input packet's header includes a top shim-header stack entry that contains a label in an entry in the label-based forwarding table, the output-packet assembler uses that entry to fetch the link-layer header and stack-entry sequence with which it constructs the output packet for that input packet; and C) if an input packet's header does not include a top shim-header stack entry whose label is in the label-based forwarding table, the output-packet assembler uses an entry in the prefix-based forwarding table to fetch the link-layer header value and stack-entry sequence with which it constructs the output packet for that input packet.

Claim 6

Dependent Claim 85 words

A router as defined in claim 4 wherein: A) each shim-header stack entry includes a class-of-service field; and B) the output-packet assembler is operable in at least one mode of operation in which it assembles an output packet by placing the class-of-service field's contents from the top shim-header stack entry of the incoming packet for which that output packet is being assembled into each shim-header stack entry of the fetched stack-sequence if that input packet and the fetched stack-entry sequence both include shim-header stack entries.

Claim 7

Dependent Claim 90 words

A router as defined in claim 5 wherein: A) each shim-header stack entry includes a time-to-live field; and B) the output-packet assembler is operable in at least one mode of operation in which it assembles an output packet by placing into each shim-header stack entry of the fetched stack-entry sequence a time-to-live count whose value depends on the time-to-live count from a shim-header stack entry of the incoming packet for which that output packet is being assembled if that input packet and fetched stack-entry sequence both include shim-header stack entries.

Claim 8

Dependent Claim 223 words

For operating a label-switching router, a method that includes: A) receiving at the router incoming communications packets that comprise: i) a network-layer datagrams including respective network-layer destination addresses; and ii) outer headers including link-layer headers, the outer header of each of at least some of the incoming packets additionally including at least one shim-header stack entry; B) maintaining in the router a forwarding information base containing a plurality of forwarding entries, each of which is associated with a respective destination and specifies for the respective destination a link-layer header and a stack-entry sequence of zero or more shim-header stack entries containing respective labels, the stack-entry sequences associated with some destinations being empty, the stack-entry sequences associated with other destinations consisting of at least stack entry; C) constructing an output packet for each of a forwardable plurality of incoming packets, each of at least some of whose outer headers include at least one shim-header stack entry, each such output packet being constructed by fetching a link-layer header and stack-entry sequence associated by the forwarding information base with the incoming packet's destination independently of the number of shim-header stack entries in the incoming packet's outer header and replacing therewith the part of the incoming packet's outer header down through its top shim-header stack entry; and D) transmitting from the router the outgoing packets thus constructed.

Claim 9

Dependent Claim 223 words

For operating a label-switching router, a method that includes: A) receiving at the router incoming communications packets that comprise: i) a network-layer datagrams including respective network-layer destination addresses; and ii) outer headers including link-layer headers, the outer header of each of at least some of the incoming packets additionally including at least one shim-header stack entry; B) maintaining in the router a forwarding information base containing a plurality of forwarding entries, each of which is associated with a respective destination and specifies for the respective destination a link-layer header and a stack-entry sequence of zero or more shim-header stack entries containing respective labels, the stack-entry sequences associated with some destinations being empty, the stack-entry sequences associated with other destinations consisting of at least stack entry; C) constructing an output packet for each of a forwardable plurality of incoming packets, each of at least some of whose outer headers include at least one shim-header stack entry, each such output packet being constructed by fetching a link-layer header and stack-entry sequence associated by the forwarding information base with the incoming packet's destination independently of the number of shim-header stack entries in the incoming packet's outer header and replacing therewith the part of the incoming packet's outer header down through its top shim-header stack entry; and D) transmitting from the router the outgoing packets thus constructed.

Claim 10

Dependent Claim 29 words

A method as defined in claim 7 wherein the outer header of each of at least some of the forwardable plurality of incoming packets includes no shim-header stack entry.

Claim 11

Dependent Claim 38 words

A method as defined in claim 8 wherein each forwarding entry specifies the link-layer header and stack-entry sequence by pointing to a data structure that contains the concatenation of the link-layer header value and the shim-header stack-entry sequence.

Claim 12

Dependent Claim 173 words

A method as defined in claim 9 wherein: A) the forwarding information base comprises: i) a prefix-based forwarding table, each of whose entries includes a network-layer-address prefix of the destinations with which that entry is associated; and ii) a label-based forwarding table, each of whose entries includes a label that the router associates with a network-layer-address prefix of the destinations with which that entry is associated; B) if an input packet's header includes a top shim-header stack entry that contains a label in an entry in the label-based forwarding table, the output-packet is assembled by using that entry to fetch the link-layer header and stack-entry sequence with which the output packet for that input packet is constructed; and C) if an input packet's header does not include a top shim-header stack entry whose label is in the label-based forwarding table, the output-packet is assembled by using an entry in the prefix-based forwarding table to fetch the link-layer header value and stack-entry sequence with which it constructs the output packet for that input packet.

Claim 13

Dependent Claim 83 words

A method as defined in claim 10 wherein: A) each shim-header stack entry includes a class-of-service field; and B) the method includes at lease one mode of operation in which an output packet is assembled by placing the class-of-service field's contents from the top shim-header stack entry of the incoming packet for which that output packet is being assembled in each shim-header stack entry of the fetched stack-entry sequence if that input packet and the fetched stack-entry sequence both include shim-header stack entries.

Claim 14

Dependent Claim 88 words

A method as defined in claim 11 wherein: A) each shim-header stack entry includes a time-to-live field; and B) the method includes at least one mode of operation in which an output packet is assembled by placing into each shim-header stack entry of the fetched stack-entry sequence a time-to-live count whose value depends on the time-to live count from a shim-header stack entry of the incoming packet for which that output packet is being assembled if that input packet and fetched stack-entry sequence both include shim-header stack entries.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-09-24	2005-03-26	2005-09-25	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-09-24	2009-03-26	2009-09-25	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-09-24	2013-03-26	2013-09-25	$7700.00	Window Closed / Lapsed

Use of a single data structure for label forwarding and imposition

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag