Lollipop sequence numbering

Last updated

Lollipop sequence numbering is a numbering scheme used in routing protocols. In this numbering scheme, sequence numbers start at a negative value, increase until they reach zero, then cycle through a finite set of positive numbers indefinitely. When a system is rebooted, the sequence is restarted from a negative number again. This allows recently rebooted systems to be distinguished from systems which have simply looped around their numbering space. This path can be visualized as a line with a circle at the end; hence a lollipop.

There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be considered to be examples of a primary key of a database management system table, whose table definitions require a database design.

Lollipop candy on a stick

A lollipop is a type of sugar candy usually consisting of hard candy mounted on a stick and intended for sucking or licking. Different informal terms are used in different places, including lolly, sucker, sticky-pop, etc. Lollipops are available in many flavors and shapes.

Lollipop sequence numbering was originally believed to resolve the ambiguity problem in cyclic sequence numbering schemes, and was used in OSPF version 1 for this reason. Later work showed that this was not the case, like in the ARPANET sequence bug, and OSPF version 2 replaced it with a linear numbering space, with special rules for what happens when the sequence numbers reach the end of the numbering space [1] .

Related Research Articles

Internet Protocol version 4 (IPv4) is the fourth version of the Internet Protocol (IP). It is one of the core protocols of standards-based internetworking methods in the Internet, and was the first version deployed for production in the ARPANET in 1983. It still routes most Internet traffic today, despite the ongoing deployment of a successor protocol, IPv6. IPv4 is described in IETF publication RFC 791, replacing an earlier definition.

Internet Protocol version 6 (IPv6) is the most recent version of the Internet Protocol (IP), the communications protocol that provides an identification and location system for computers on networks and routes traffic across the Internet. IPv6 was developed by the Internet Engineering Task Force (IETF) to deal with the long-anticipated problem of IPv4 address exhaustion. IPv6 is intended to replace IPv4. In December 1998, IPv6 became a Draft Standard for the IETF, who subsequently ratified it as an Internet Standard on 14 July 2017.

The Internet Protocol (IP) is the principal communications protocol in the Internet protocol suite for relaying datagrams across network boundaries. Its routing function enables internetworking, and essentially establishes the Internet.

In computer networking, the User Datagram Protocol (UDP) is one of the core members of the Internet protocol suite. The protocol was designed by David P. Reed in 1980 and formally defined in RFC 768. With UDP, computer applications can send messages, in this case referred to as datagrams, to other hosts on an Internet Protocol (IP) network. Prior communications are not required in order to set up communication channels or data paths.

Border Gateway Protocol (BGP) is a standardized exterior gateway protocol designed to exchange routing and reachability information among autonomous systems (AS) on the Internet. The protocol is classified as a path vector protocol. The Border Gateway Protocol makes routing decisions based on paths, network policies, or rule-sets configured by a network administrator and is involved in making core routing decisions.

Intermediate System to Intermediate System is a routing protocol designed to move information efficiently within a computer network, a group of physically connected computers or similar devices. It accomplishes this by determining the best route for data through a packet-switched network.

Open Shortest Path First (OSPF) is a routing protocol for Internet Protocol (IP) networks. It uses a link state routing (LSR) algorithm and falls into the group of interior gateway protocols (IGPs), operating within a single autonomous system (AS). It is defined as OSPF Version 2 in RFC 2328 (1998) for IPv4. The updates for IPv6 are specified as OSPF Version 3 in RFC 5340 (2008). OSPF supports the Classless Inter-Domain Routing (CIDR) addressing model.

The Routing Information Protocol ('RIP') is one of the oldest distance-vector routing protocols which employ the hop count as a routing metric. RIP prevents routing loops by implementing a limit on the number of hops allowed in a path from source to destination. The largest number of hops allowed for RIP is 15, which limits the size of networks that RIP can support.

Network address translation Protocol facilitating connection of one IP address space to another.

Network address translation (NAT) is a method of remapping one IP address space into another by modifying network address information in the IP header of packets while they are in transit across a traffic routing device. The technique was originally used as a shortcut to avoid the need to readdress every host when a network was moved. It has become a popular and essential tool in conserving global address space in the face of IPv4 address exhaustion. One Internet-routable IP address of a NAT gateway can be used for an entire private network.

Serial number unique code assigned for identification of a single unit

A serial number is a unique identifier assigned incrementally or sequentially to an item, to uniquely identify it.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the other being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

XORP

XORP is an open-source Internet Protocol routing software suite originally designed at the International Computer Science Institute in Berkeley, California. The name is derived from eXtensible Open Router Platform. It supports OSPF, BGP, RIP, PIM, IGMP, OLSR.

The Hazy-Sighted Link State Routing Protocol (HSLS) is a wireless mesh network routing protocol being developed by the CUWiN Foundation. This is an algorithm allowing computers communicating via digital radio in a mesh network to forward messages to computers that are out of reach of direct radio contact. Its network overhead is theoretically optimal, utilizing both proactive and reactive link-state routing to limit network updates in space and time. Its inventors believe it is a more efficient protocol to route wired networks as well. HSLS was invented by researchers at BBN Technologies.

Link State Packet (LSP) is a packet of information generated by a network router in a link state routing protocol that lists the router's neighbors. Link state packet can also be further defined as special datagrams that determine the names of and the cost or distance to any neighboring routers and associated networks. They are used to efficiently determine what the new neighbor is, if a link failure occurs, and the cost of changing a link if the need arises. LSPs are queued for transmission, and must time out at about the same time. They must be acknowledged, and can be distributed throughout the network, but cannot use the routing database.

Dynamic Multipoint Virtual Private Network (DMVPN) is a dynamic tunneling form of a virtual private network (VPN) supported on Cisco IOS-based routers, Huawei AR G3 routers and USG firewalls, and on Unix-like operating systems.

Flooding (computer networking) Simple routing algorithm sending incoming packets to all other links than the sender

Flooding is a simple computer network routing algorithm in which every incoming packet is sent through every outgoing link except the one it arrived on.

A lollipop is a confectionery product.

A routing protocol specifies how routers communicate with each other, distributing information that enables them to select routes between any two nodes on a computer network. Routers perform the "traffic directing" functions on the Internet; data packets are forwarded through the networks of the internet from router to router until they reach their destination computer. Routing algorithms determine the specific choice of route. Each router has a prior knowledge only of networks attached to it directly. A routing protocol shares this information first among immediate neighbors, and then throughout the network. This way, routers gain knowledge of the topology of the network. The ability of routing protocols to dynamically adjust to changing conditions such as disabled data lines and computers and route data around obstructions is what gives the Internet its survivability and reliability.

Route analytics is an emerging network monitoring technology specifically developed to analyze the routing protocols and structures in meshed IP Networks. Their main mode of operation is to passively listen to the Layer 3 routing protocol exchanges between routers for the purposes of network discovery, mapping, real-time monitoring and routing diagnostics.

An interior gateway protocol (IGP) is a type of protocol used for exchanging routing information between gateways within an autonomous system. This routing information can then be used to route network-layer protocols like IP.

References

  1. Jon T. Moy "Link State Advertisements (LSAs)." OSPF: Anatomy of an Internet Routing Protocol p. 77.