Fisheye State Routing

Fisheye State Routing (FSR) is a proposal for an implicit hierarchical routing protocol targeted to ad hoc networks.[1] The basic principles of FSR are shared with other proactive, link-state routing protocols. In proactive link-state protocols every network node constantly updates a topology map that makes it possible to compute the shortest path (and thus the next hop) to any destination in the network. The originality of FSR is inspired by the "fisheye" technique to reduce the size of information required to represent graphical data: The eye of a fish captures with high detail the pixels near the focal point, while the detail decreases as the distance from the focal point increases.

In routing, the fisheye approach translates into maintaining an updated information set about distance and path quality information for the immediate neighborhood of a node, against a progressively less updated information as the distance increases. Fisheye represents a valid trade-off between the accuracy of the routing function and the overhead due to the generation of control messages by the routing protocol.

FSR was never released to the public as a stand-alone routing protocol, and its specification was never finalized.[2] The base principle was included in the widely used OLSRd daemon (an open source implementation of the OLSR routing protocol[3]).

Protocol working principle

FSR is a link-state routing protocol, thus it is made of three tasks:

  1. Neighbor Discovery: every node sends an HELLO message every δ seconds to its one-hop neighbours, in order to establish and maintain neighbour relationships.
  2. Information Dissemination: every node disseminates Link State Announcements messages (LSA) every Δ seconds (with Δ > δ), that contain neighbour link information, to all other nodes in the network.
  3. Route Computation: from the information contained in the LSA messages the node can reconstruct the whole network topology and use Dijkstra's algorithm to compute the routes to any node in the network.

The peculiarity of FSR is that LSA messages are generated every Δ seconds using a sequence of distinct Time-To-Live (TTL) values. Take as an example the sequence 1, 3, 8, 64, the 1-hop neighbours receive the LSA every Δs, so they have the most updated information. 2-hop neighbours receive the LSA with TTL 3, 8, 24. Nodes at a distance from 4 to 8 hops receive only the LSA with TTL 8 and 64. All the others receive only the LSA with TTL 64. As a consequence every node has progressively less updated information on the network topology as the distance increases.

The protocol exploits the fact that when a packet moves from a source to a destination, the nodes encountered on the shortest path have an increasingly precise topology information about the topological position of the destination (as their distance to the destination decreases), so the loss of accuracy in the shortest path computation from the source node is compensated along the path to the destination.

FSR thus decreases the overall quantity of information spread in the network, since LSA are not sent with a fixed maximum TTL.

Drawbacks

One of the typical issues with link-state protocols is that when a node or link breaks, temporary loops can be created. This is due to the fact that HELLO messages are sent with a higher frequency than LSA messages, so if a node fails, its neighbors sense the broken link way before the other nodes. They immediately recompute their routing tables, which can conflict with the routing table of the other nodes, and a loop can be created. This can happen when two nodes have information with a different age and thus they compute their routing tables on two different network topologies. FSR does this by design, it introduces areas in the network with potentially different information sets, so it increases the probability of creating temporary loops.[4]

References

Read other articles:

Lukisan William Temple Franklin oleh John Trumbull. Minyak di atas kanvas. 1790-1791. William Temple Franklin Jr, dikenal sebagai Temple Franklin, (22 Februari 1760, di London – 25 Mei 1823, di Paris) merupakan seorang diplomat Amerika dan spekulan lahan yasan. Dia terkenal karena keterlibatannya dengan misi diplomatik Amerika di Prancis selama Perang Revolusi Amerika Serikat. Dimulai pada usia 16, ia menjabat sebagai sekretaris kakeknya Benjamin Franklin, yang bernegosiasi dan menyetujui A...

 

American politician For the man wrongfully convicted of murder, see Joseph Burrows. From 1882's Public Men of To-Day Joseph Henry Burrows (May 15, 1840 – April 28, 1914) was a U.S. Representative from Missouri. Born in Manchester, England, Burrows immigrated to the United States with his parents, who settled in Quincy, Illinois. He attended the common schools at Quincy, Illinois, and Keokuk, Iowa. He engaged in mercantile pursuits and later in agricultural pursuits. He moved to Cainsville, ...

 

Venezuelan footballer (born 1993) In this Spanish name, the first or paternal surname is Ángel and the second or maternal family name is Romero. Wilker Angel Ángel with FC Terek in 2017Personal informationFull name Wilker José Ángel Romero[1]Date of birth (1993-03-18) 18 March 1993 (age 31)[2]Place of birth Valera, Venezuela[1]Height 1.90 m (6 ft 3 in)[3]Position(s) DefenderTeam informationCurrent team CriciúmaSenior career*Year...

River in BelizeMacalMacal River in BelizeLocationCountryBelizePhysical characteristicsSource  • locationMaya Mountains • elevation953 m (3,127 ft) (Cooma Cairn) Mouth  • locationBelize RiverLength320 km (200 mi)Basin size1,492 km2 (576 sq mi) The Macal River is a river running through Cayo District in western Belize. Sites along the river include the ancient Mayan town of Cahal Pech and the Beliz...

 

1980 Massachusetts Democratic presidential primary ← 1976 March 4, 1980 1984 → ← NHVT →112 pledged delegates to the 1980 Democratic National Convention   Candidate Ted Kennedy Jimmy Carter Home state Massachusetts Georgia Delegate count 78 34 Popular vote 590,404 260,391 Percentage 65.07% 28.70% Elections in Massachusetts General 1942 1944 1946 1948 1950 1952 1954 1956 1958 1960 1962 1964 1966 1970 1974 1978 1982 1986 1990 1994 ...

 

Сибирский горный козёл Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:СинапсидыКла�...

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна  Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

 

Сельское поселение России (МО 2-го уровня)Новотитаровское сельское поселение Флаг[d] Герб 45°14′09″ с. ш. 38°58′16″ в. д.HGЯO Страна  Россия Субъект РФ Краснодарский край Район Динской Включает 4 населённых пункта Адм. центр Новотитаровская Глава сельского пос�...

 

土库曼斯坦总统土库曼斯坦国徽土库曼斯坦总统旗現任谢尔达尔·别尔德穆哈梅多夫自2022年3月19日官邸阿什哈巴德总统府(Oguzkhan Presidential Palace)機關所在地阿什哈巴德任命者直接选举任期7年,可连选连任首任萨帕尔穆拉特·尼亚佐夫设立1991年10月27日 土库曼斯坦土库曼斯坦政府与政治 国家政府 土库曼斯坦宪法 国旗 国徽 国歌 立法機關(英语:National Council of Turkmenistan) ...

「アプリケーション」はこの項目へ転送されています。英語の意味については「wikt:応用」、「wikt:application」をご覧ください。 この記事には複数の問題があります。改善やノートページでの議論にご協力ください。 出典がまったく示されていないか不十分です。内容に関する文献や情報源が必要です。(2018年4月) 古い情報を更新する必要があります。(2021年3月)出...

 

Artikel ini membutuhkan rujukan tambahan agar kualitasnya dapat dipastikan. Mohon bantu kami mengembangkan artikel ini dengan cara menambahkan rujukan ke sumber tepercaya. Pernyataan tak bersumber bisa saja dipertentangkan dan dihapus.Cari sumber: Pers mahasiswa – berita · surat kabar · buku · cendekiawan · JSTOR Sebuah surat kabar siswa yang terbit di Amerika Serikat tahun 1978 Pers mahasiswa (disingkat persma) adalah entitas media yang dikelola oleh ...

 

سلطان المغرب مولاي اليزيد مولاي اليزيد سلطان المغرب فترة الحكم1790 - 1792م تاريخ التتويج 18 شعبان 1204هـ معلومات شخصية الاسم الكامل اليزيد بن محمد بن عبد الله بن إسماعيل بن الشريف الميلاد 1750مفاس  الوفاة 23 جمادى الثانية 1206هـ 16 يناير 1792م.بالقرب من زكورة على حاشية واد تانسيفت. مكا...

Bessie dan Robert Vonnoh, 1930 Robert William Vonnoh (17 September 1858 – 28 Desember 1933) adalah seorang pelukis Impresionis Amerika yang dikenal karena potret dan lanskapnya. Dia bepergian secara ekstensif antara Pantai Timur Amerika dan Prancis, lebih khusus lagi koloni seniman Grez-sur-Loing. Biografi Robert William Vonnoh lahir pada 17 September 1858 di Hartford, Connecticut. Ia belajar di Boston di Massachusetts Normal Art School sekarang disebut Massachusetts College o...

 

Juice produced from apples Filtered and unfiltered apple juice Clarified apple juice, from which pectin and starch have been removed, in a plastic bottle Apple juice is a fruit juice made by the maceration and pressing of an apple. The resulting expelled juice may be further treated by enzymatic and centrifugal clarification to remove the starch and pectin, which holds fine particulate in suspension, and then pasteurized for packaging in glass, metal, or aseptic processing system containers, ...

 

This article is about the pop-art artist. For the horror art artist, see Clive Barker. Clive BarkerBorn1940 (age 83–84)Luton, Bedfordshire, EnglandKnown forSculptureNotable workSplash,[1] 1967 Rio - Homage to Marlon Brando,[2] 1968 Homage to Soutine,[3] 1969Skull, Gas Mask,[4] 1973 German Head ’42,[5] 1974Sir Peter Thomas Blake,[6] 1983 Fridge,[7] 1999MovementPop art, Surrealism Clive Barker (born 1940) is a British pop...

Voce principale: Giochi olimpici invernali. XIX Giochi olimpici invernali(EN) Light The Fire Within(traduzione: Accendi il fuoco dentro)Città ospitanteSalt Lake City, Stati Uniti d'America Paesi partecipanti77 (vedi sotto) Atleti partecipanti2.399 (1.513 - 886 ) Competizioni78 in 7 sport Cerimonia apertura8 febbraio 2002 Cerimonia chiusura24 febbraio 2002 Aperti daGeorge W. Bush Giuramento atletiJim Shea Giuramento giudiciAllen Church Ultimo tedoforola squadra del Miracolo sul ghiaccio Stad...

 

جامعة مونتريال Université de Montréal شعار جامعة مونتريال الشعار (باللاتينية: Fide splendet et scientia)‏[1]  معلومات التأسيس 1878 (منذ 146 سنة) المنحة المالية 276.490 مليون $C النوع عامة الميزانية 1.05 مليار $C الكليات 15 الموقع الجغرافي إحداثيات 45°30′15″N 73°36′52″W / 45.50414°N 73.61433°W / 45.50414; -...

 

圣克鲁斯迪米纳斯Santa Cruz de Minas市镇圣克鲁斯迪米纳斯在巴西的位置坐标:21°07′12″S 44°13′22″W / 21.12°S 44.2228°W / -21.12; -44.2228国家巴西州米纳斯吉拉斯州面积 • 总计2.859 平方公里(1.104 平方英里)海拔930 公尺(3,050 英尺)人口 • 總計7,347人 • 密度2,570人/平方公里(6,656人/平方英里) 圣克鲁斯迪米纳斯(葡萄牙�...

Town in Hertfordshire, England Human settlement in EnglandWareRiverside gazebosWareLocation within HertfordshirePopulation18,799 (Parish, 2011 Census)[1]OS grid referenceTL 358143Civil parishWareDistrictEast HertfordshireShire countyHertfordshireRegionEastCountryEnglandSovereign stateUnited KingdomPost townWAREPostcode districtSG12Dialling code01920PoliceHertfordshireFireHertfordshireAmbulanceEast of England UK ParliamentHertford and Stortford L...

 

Telephone numbers in NetherlandsMap of telephone codesLocationCountryNetherlandsContinentEuropeTypeClosedNSN length9Format0xx xxxxxxx / 0xxx xxxxxx (geographical) 06 xxxxxxxx (mobile)Access codesCountry code+31International access00Long-distance0 Telephone numbers in the Netherlands are administered by the Ministry of Economic Affairs, Agriculture and Innovation of the Netherlands. The telephone numbering plan may be grouped into three general categories: geographical numbers, non-geographic...