| Sonstiges: |
- Nachgewiesen in: USPTO Patent Grants
- Sprachen: English
- Patent Number: 11855,874
- Publication Date: December 26, 2023
- Appl. No: 17/392854
- Application Filed: August 03, 2021
- Assignees: ARISTA NETWORKS, INC. (Santa Clara, CA, US)
- Claim: 1. A method for reverse path forwarding (RPF) selection by a network device connected to a network, the method comprising: receiving an advertisement message from each of a plurality of neighbor devices within the network; parsing the advertisement message to determine a color identification (ID) of each of the neighbor devices, wherein the color ID is associated with a topology of the neighbor devices; and selecting, from among the neighbor devices, a RPF device based on the color ID of each of the neighbor devices by: applying a hash function to each of the color IDs to generate a set of hash values, wherein a target color ID corresponds to a color ID that generated the highest hash value among the set of hash values; determining that the color ID of the first neighbor device and the color ID of a second neighbor device among the neighbor devices match the target color ID; selecting, based on the determining, the RPF device from among the first neighbor device and the second neighbor device by applying a second hash function to using a first device ID of the first neighbor device and a second device ID of the second neighbor device; applying a second hash function to each of the first device ID and the second device ID to generate a second set of hash values, wherein the first device ID generated a highest hash value in the second set of hash values, wherein the first device ID is different from the second device ID; determining that the first device ID matches the first neighbor device; and transmitting a path establishment request to the first neighbor device.
- Claim: 2. The method of claim 1 , wherein the path establishment request is a (S, G) join request, and wherein input to the hash function comprises S, G, and one of the color IDs.
- Claim: 3. The method of claim 1 , wherein the path establishment request is a (*, G) join request, and wherein input to the hash function comprises rendezvous point (RP) address, G, and one of the color IDs, and wherein input to the second function comprises the RP address, the G, and one of the first device ID or the second device ID.
- Claim: 4. The method of claim 1 , wherein the method further comprises: determining that the first device ID matches the second device ID; and selecting, based on determining that the first device ID matches the second device ID, the RPF device from among the first neighbor device and the second neighbor device using interface IDs associated with interfaces between the network device and each of the first neighbor device and the second neighbor device, wherein the interface IDs are preconfigured and stored in a memory of the network device.
- Claim: 5. The method of claim 4 , wherein selecting the RPF device using the interface IDs comprises: applying the second hash function to each of the interface IDs to generate a second set of hash values; selecting, as a target interface ID and based on applying the second hash function, an interface ID of the interface IDs that generated the highest hash value among the second set of hash values; determining that the second neighbor device includes the target interface ID; and transmitting the path establishment request to the first neighbor device.
- Claim: 6. The method of claim 1 , wherein parsing the advertisement messages to determine the color ID of each of the neighbor devices comprises: parsing each of the advertisement messages for an authentication value; determining whether the authentication value of each of the advertisement messages matches a preset value; and parsing, by the determining, only the advertisement messages with the authentication value that matches the preset value.
- Claim: 7. A network device connected to a network comprising: a memory; and a processor coupled to the memory, wherein the processor is configured to: receive an advertisement message from each of a plurality of neighbor devices within the network; parse the advertisement message to determine a color identification (ID) of each of the neighbor devices and store the color IDs of all of the neighbor devices in the storage, wherein the color ID is associated with a topology of the neighbor devices; and select a neighbor device from among the neighbor devices as a RPF device based on the color ID of each of the neighbor devices by: applying a hash function to each of the color IDs to generate a set of hash values, wherein a target color ID corresponds to a color ID that generated the highest hash value among the set of hash values; determining that the color ID of the first neighbor device and the color ID of a second neighbor device among the neighbor devices match the target color ID; selecting, based on the determining, the RPF device from among the first neighbor device and the second neighbor device by applying a second hash function to using a first device ID of the first neighbor device and a second device ID of the second neighbor device; applying a second hash function to each of the first device ID and the second device ID to generate a second set of hash values, wherein the first device ID generated a highest hash value in the second set of hash values, wherein the first device ID is different from the second device ID; determining that the first device ID matches the first neighbor device; and transmitting a path establishment request to the first neighbor device.
- Claim: 8. The network device of claim 7 , wherein the path establishment request is a (S, G) join request, and wherein input to the hash function comprises S, G, and one of the color IDs.
- Claim: 9. The network device of claim 8 , wherein input to the second function comprises S, G, and one of the first device ID or the second device ID.
- Claim: 10. The network device of claim 7 , wherein the processor is further configured to: determine that the first device ID matches the second device ID; and select, based on determining that the first device ID matches the second device ID; the RPF device from among the first neighbor device and the second neighbor device using interface IDs associated with interfaces between the network device and each of the first neighbor device and the second neighbor device, wherein the interface IDs are preconfigured and stored in the memory of the network device, and wherein all of the interface IDs are unique.
- Claim: 11. The network device of claim 10 , wherein selecting the RPF device using the interface IDs comprises: applying the second hash function to each of the interface IDs to generate a second set of hash values; selecting, as a target interface ID and based on applying the second hash function, an interface ID of the interface IDs that generated the highest hash value among the second set of hash values; determining that the second neighbor device includes the target interface ID; and transmitting the path establishment request to the second neighbor device.
- Claim: 12. The network device of claim 7 , wherein parsing the advertisement messages to determine the color identification ID of each of the neighbor devices comprises: parsing each of the advertisement messages for an authentication value; determining whether the authentication value of each of the advertisement messages matches a preset value; and parsing, by the determining, only the advertisement messages with the authentication value that matches the preset value.
- Claim: 13. The network device of claim 7 , wherein the path establishment request is a (*, G) join request, and wherein input to the hash function comprises rendezvous point (RP) address, G, and one of the color IDs, and wherein input to the second function comprises the RP address, the G, and one of the first device ID or the second device ID.
- Patent References Cited: 6553028 April 2003 Tang et al. ; 8090805 January 2012 Chawla ; 11271816 March 2022 Reehil ; 20070097895 May 2007 Keshavarzian ; 20080062891 March 2008 Van der Merwe ; 20180063723 March 2018 Sanderovich ; 20190036717 January 2019 Kebler ; 20220029911 January 2022 Zhang
- Other References: Fenner et. al., “Protocol Independent Multicast—Sparse Mode (PIM-SM) : Protocol Specification (Revised)”, Request for Comments (RFC) 7761 (Mar. 2016) 137 pages. cited by applicant ; International Search Report and Written Opinion issued for International PCT Application No. PCT/US2022/037993, dated Oct. 10, 2022, 12 pages. cited by applicant
- Primary Examiner: Wong, Xavier S
- Attorney, Agent or Firm: Sprinkle IP Law Group
|
