Synchronization mechanism for link state packet routing
First Claim
1. A method of providing loop free routing of data packets in a network having a plurality of switches, routing messages for communicating network topology information between said switches, each of said switches having a routing database for storing said network topology information and routing path information used in forwarding packets, a plurality of links connecting said switches and a plurality of channels connecting said switches to said links, comprising the steps of:
- receiving by a first one of said plurality of switches a routing message identifying new network topology information and said new network topology information differing from the network topology information currently contained in said routing database of said first switch;
incorporating said new network topology information into said routing database of said first switch and changing routing path information based thereon; and
notifying each one of said plurality of switches adjacent to said first switch that said new network topology information has been received by said first switch and used to change routing path information;
temporarily discarding data packets received by said first switch whose routing paths are affected by said new network topology information;
transmitting said routing message received by said first switch to said plurality of switches;
notifying said first switch by each of said plurality of adjacent switches that said routing message identifying said new network topology information is stored in each of said routing databases of said plurality of adjacent switches and used to change routing path information; and
discontinuing said discarding of data packets whose routing paths were affected by said new network topology information by said first switch after said notification from all of said plurality of adjacent switches.
6 Assignments
0 Petitions
Accused Products
Abstract
A method of providing loop free and shortest path routing of data packets in a network having a plurality of switches, routing messages for communicating network topology information between the switches, a plurality of links connecting the switches and a plurality of channels connecting the switches to the links. The loop free routing of data packets is achieved through modifications to known link state packet (LSP) routing protocols and permits each switch to inform adjacent switches in the network of the information in the switch'"'"'s database used to compute forwarding tables. A switch uses a received LSP to compute a forwarding table and informs neighboring switches on attached links of the routing change. The switch discards any subsequent data packets whose path would be affected by the changed routing information. The discarding of data packets continues until the switch receives notification from each adjacent switch affected by the changed routing information that all affected routing paths have been recalculated and the forwarding table of each affected switch has been updated. Thus, while adjacent switches temporarily contain inconsistent LSP databases and possibly inconsistent forwarding tables, the looping of data packets is prevented. Shortest path routing for data packets from a source endnode to a destination endnode is achieved by assuring that the first switch to forward the packet is on the shortest path to the packet'"'"'s destination endnode. A source endnode transmits a data packet with an appropriate destination header and the determination of the actual routing path is performed transparently to endnodes. A data packet reaches its destination endnode by following the shortest path possible based on the network topology as represented in the database of the first switch that forwards it.
-
Citations
25 Claims
-
1. A method of providing loop free routing of data packets in a network having a plurality of switches, routing messages for communicating network topology information between said switches, each of said switches having a routing database for storing said network topology information and routing path information used in forwarding packets, a plurality of links connecting said switches and a plurality of channels connecting said switches to said links, comprising the steps of:
-
receiving by a first one of said plurality of switches a routing message identifying new network topology information and said new network topology information differing from the network topology information currently contained in said routing database of said first switch; incorporating said new network topology information into said routing database of said first switch and changing routing path information based thereon; and notifying each one of said plurality of switches adjacent to said first switch that said new network topology information has been received by said first switch and used to change routing path information; temporarily discarding data packets received by said first switch whose routing paths are affected by said new network topology information; transmitting said routing message received by said first switch to said plurality of switches; notifying said first switch by each of said plurality of adjacent switches that said routing message identifying said new network topology information is stored in each of said routing databases of said plurality of adjacent switches and used to change routing path information; and discontinuing said discarding of data packets whose routing paths were affected by said new network topology information by said first switch after said notification from all of said plurality of adjacent switches. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A method of providing loop free routing of data packets in a network having a plurality of switches, routing messages for communicating network topology information between said switches, each of said switches having a routing database with a forwarding table including for each destination node in the network a pick-up bit and a hold down bit for each channel attached to the switch for storing said network topology information and routing path information used in forwarding packets, a plurality of links connecting said switches and a plurality of channels connecting said switches to said links, comprising the steps of:
-
receiving a data packet having an address of the destination node through one of said plurality of channels at one of said plurality of switches; determining if the address of the destination node included in the header of the data packet corresponds to a destination node contained in said forwarding table of said switch; discarding said data packet if no forwarding table entry exists for said destination node and said channel combination; accessing the forwarding table if a forwarding table entry exists for said destination node and said channel combination; determining if each channel in said channel combination is "fully-up"; discarding said data packet if said hold down bit in said forwarding table for said channel and destination node combination is asserted true; discarding said data packet if said pick-up bit for said channel and destination node combination is asserted false; discarding said data packet if none of the forwarding channels for said destination node is "fully-up"; transmitting said data packet through a forwarding channel in said forwarding table if said data packet is not discarded in the previous steps.
-
-
24. A method of providing shortest path routing of data packets in a network having a plurality of switches routing messages for communicating network topology information between said switches, each of said switches having a routing database with a forwarding table for storing said network topology information and routing path information used in forwarding packets, a plurality of links connecting said switches and a plurality of channels connecting said switches to said links, comprising the steps of:
-
each of said plurality of switches receiving said routing messages and calculating the shortest path from said respective switch to each possible destination in said network; storing said shortest path information in said forwarding table of said database of each of said respective switches; transmitting a data packet having an address of a destination end node onto one of said links; selecting one of said plurality of switches attached to said link that is part of the shortest path for said data packet to said destination end node thereby assuring that the first one of said switches to receive said data packet is part of the shortest route to said destination end node; receiving said data packet by said selected switch; forwarding said data packet to said destination end node by said selected switch. - View Dependent Claims (25)
-
Specification