Back to results
US 5,471,467 AGranted
Routing logic means and method for distributing a packet among network nodes
AssigneeAlcatel
InventorCharles F. M. Johann
Life of this patent
Estimating the term…
Abstract
A routing logic system and methodology for adaptive and distributed routing in packet switching networks makes an accurate routing choice needing only minimal signalling overhead. This is achieved by combining only local delay information with less dynamic topological information, such as the hop distance to the destination node, into a third cost value and making the routing decision based on this third cost value. This is a first portion of a possible path, the remaining second portion being accounted for via the hop distance represented by it.
Claims51
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, where X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path, said first portion comprising an arbitrarily selectable number of said packet switching nodes;
- for each of said plurality of possible partial paths, determining a second cost value equal to an estimated transfer cost, different from said transmission delay, over a second portion of said possible path;
- and
- combining said first and second cost values to choose said selected partial path based on said combination, wherein said step of combining said first and second cost values comprises determining a third cost value by combining a weighed value of a first relative value and a second relative value, wherein said first relative value is determined by dividing said first cost value by the mean value of said first cost value taken over said first portion of all of said plurality of possible partial paths, and wherein said second relative value is determined by dividing said second cost value by the mean value of second cost value taken over said second portion for all of said plurality of possible partial paths, and wherein said choosing step comprises choosing said selected partial path having a minimal third cost value.
4 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, wherein X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path;
- for each of said plurality of possible partial paths, determining a second cost value, different from said estimated transmission delay, over a second portion of said possible path;
- and
- combining said first and second cost values to choose said selected partial path based on said combination, wherein said step of combining said first and second cost values comprises determining a third cost value by combining a weighed value of a first relative value and a second relative value, wherein said first relative value is determined by dividing said first cost value by the mean value of said first cost value taken over said first portion of all of said plurality of possible paths, and wherein said second relative value is determined by dividing said second cost value by the mean value of second cost value taken over said second portion of all of said plurality of possible partial paths, and wherein said choosing step comprises choosing said selected partial path having a minimal third cost value.
4 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, wherein X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path, wherein said step of determining a first cost value over a first portion of said possible path comprises determining said first cost value over Y nodes and their interconnecting links, wherein Y is a positive integer;
- for each of said plurality of possible partial paths, determining a second cost value equal to an estimated transfer cost, different from said estimated transmission delay, over a second portion of said possible path, wherein said step of determining a second cost value equal to an estimated transfer cost over a second portion of said possible path comprises determining a second cost value over a second portion comprising all nodes and links of said possible path not comprised in said first portion;
- and
- combining said first and second cost values to choose said selected partial path based on said combination, wherein said step of combining said first and second cost values comprises determining a third cost value by combining a weighed value of a first relative value and a second relative value, wherein said first relative value is determined by dividing said first cost value by the mean value of said first cost value taken over said first portion of all of said plurality of possible partial paths, and wherein said second relative value is determined by dividing said second cost value by the mean value of second cost value taken over said second portion of all of said plurality of possible partial paths;
- and wherein said choosing step comprises choosing said selected partial path having a minimal third cost value.
5 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, wherein X is a positive integer, wherein identifying a plurality of possible partial paths comprising X of said other packet switching nodes and their respective interconnecting links comprises identifying a plurality of possible partial paths comprising one of said other packet switching nodes and their respective interconnecting links;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path, wherein said step of determining a first cost value over a first portion of said possible path comprises determining said first cost value over Y nodes and their interconnecting links, wherein said step of determining said cost value over Y nodes comprises determining said first cost value over one node, wherein Y is a positive integer;
- for each of said plurality of possible partial paths, determining a second cost value, different from said estimated transmission delay, over a second portion of said possible path, wherein said step of determining a second cost value over a second portion of said possible path comprises determining a second cost value over a second portion comprising all nodes and links of said possible path not comprised in said first portion;
- and
- combining said first and second cost values to choose said selected partial path based on said combination, wherein said step of combining said first and second cost values comprises determining a third cost value by combining a weighed value of a first relative value and a second relative value, wherein said first relative value is determined by dividing said first cost value by the mean value of said first cost value taken over said first portion of all of said plurality of possible partial paths, and wherein said second relative value is determined by dividing said second cost value by the mean value of second cost value taken over said second portion of all of said plurality of possible partial paths;
- and wherein said choosing step comprises choosing said selected partial path having a minimal third cost value.
5 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, wherein X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path;
- for each of said plurality of possible partial paths, determining a second cost value equal, different from said estimated transmission delay, over a second portion of said possible path;
- and
- combining said first and second cost values to choose said selected partial path based on said combination;
- wherein each of said partial paths has an end node, and wherein said packet includes a credit counter with a value CC which is initialized upon entering said network wherein CC is a positive integer, and wherein said step of choosing a selected partial path from said plurality of possible partial paths comprises choosing only from partial paths for which the minimum number N of nodes from the end node of said partial path to said destination node and the minimum number M of nodes from said predetermined node to said destination node satisfies the expression:
- M+CC>=X+N, wherein each of N and M is a positive integer;
- and further comprising the step of increasing said credit counter value with a value M-(N+X) at the end node of said chosen partial path.
7 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, where X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path, said first portion comprising an arbitrarily selectable number of said packet switching nodes;
- for each of said plurality of possible partial paths, determining a second cost value equal to an estimated transfer cost, different from said transmission delay, over a second portion of said possible path;
- and
- combining said first and second cost values to choose said selected partial path based on said combination, wherein said step of determining a first cost value over a first portion of said possible path comprises determining said first cost value over Y nodes and their interconnecting links, wherein Y is a positive integer, and wherein said step of determining a second cost value equal to an estimated transfer cost over a second portion of said possible path comprises determining a second cost value over a second portion comprising all nodes and links of said possible path not comprised in said first portion;
- wherein said step of combining said first and second cost values comprises determining a third cost value by combining a weighed value of a first relative value and a second relative value, wherein said first relative value is determined by dividing said first cost value by the mean value of said first cost value taken over said first portion all of said plurality of possible partial paths, and wherein said second relative value is determined by dividing said second cost value by the mean value of second cost value taken over said second portion for all of said plurality of possible partial path,
- and wherein said choosing step comprises choosing said selected partial path having a minimal third cost value.
6 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, where X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path, said first portion comprising an arbitrarily selectable number of said packet switching nodes;
- for each of said plurality of possible partial paths, determining a second cost value equal to an estimated transfer cost, different from said transmission delay, over a second portion of said possible path;
- and
- combining said first and second cost values to choose said selected partial path based on said combination,
- wherein said step of determining a first cost value over a first portion of said possible path comprises determining said first cost value over Y nodes and their interconnecting links, wherein Y is a positive integer, and wherein said step of determining a second cost value equal to an estimated transfer cost over a second portion of said possible path comprises determining a second cost value over a second portion comprising all nodes and links of said possible path not comprised in said first portion;
- and
- wherein identifying a plurality of possible partial paths comprising X of said other packet switching nodes and their respective interconnecting links comprises identifying a plurality of possible partial paths comprising one of said other packet switching nodes and their respective interconnecting links, and wherein said step of determining said cost value over Y nodes comprises determining said first cost value over one node;
- wherein said step of choosing a selected partial path comprises, for each partial path, choosing only from the possible path corresponding to each said partial path having a minimal second cost value taken over the second cost values of all possible paths corresponding to each said partial path;
- wherein said step of combining said first and second cost values comprises determining a third cost value by combining a weighed value of a first relative value and a second relative value, wherein said first relative value is determined by dividing said first cost value by the mean value of said first cost value taken over said first portion of all of said plurality of possible partial paths, and wherein said second relative value is determined by dividing said second cost value by the mean value of second cost value taken over said second portion for all of said plurality of possible partial paths, and wherein said choosing step comprises choosing said selected partial path having a minimal third cost value.
9 more elements
A method of routing a packet from a predetermined node to a destination node along a switching network comprising a plurality of packet switching nodes interconnected by respective links, comprising the steps of:
- identifying a plurality of possible partial paths wherein each of said possible partial paths originates from said predetermined node and comprises X of said other packet switching nodes and their respective interconnecting links, where X is a positive integer;
- and
- choosing a selected partial path from said plurality of possible partial paths, wherein said choosing step further comprises at least the steps of:
- for each of said plurality of possible partial paths, determining a first cost value equal to an estimated transmission delay over a first portion of a possible path, said possible path connecting said predetermined node with said destination node and including said possible partial path, said first portion comprising an arbitrarily selectable number of said packet switching nodes;
- for each of said plurality of possible partial paths, determining a second cost value equal to an estimated transfer cost, different from said transmission delay, over a second portion of said possible path;
- combining said first and second cost values to choose said selected partial path based on said combination;
- and
- wherein each of said partial paths has an end node, and wherein said packet includes a credit counter with a value, CC, which is initialized upon entering said network, wherein CC is a positive integer, and wherein said step of choosing a selected partial path from said plurality of possible partial paths comprises choosing only from partial paths for which the minimum number N of nodes from the end node of said partial path to said destination node and the minimum number M of nodes from said predetermined node to said destination node satisfies the expression:
- M+CC>=X+N, wherein each of N and M is a positive integer.
6 more elements
Dependencies are inferred from the claim text.