COMPRESSING SINGLY LINKED LISTS SHARING COMMON NODES FOR MULTI-DESTINATION GROUP EXPANSION

摘要

A multi-destination expansion table is stored that comprises a first database containing data representing all nodes in a singly linked list that is a superset of nodes for a plurality of multi-destination groups and a second database storing data representing multi-destination group specific arcs across one or more nodes. The singly linked list is traversed to determine how to replicate a packet for a particular multi-destination group. The packet is replicated based on interface data stored in the first database associated with the current node address. When a match is found in the second database, a next node address is determined from the second database. When a match is not found in the second database, a next node address determined from accessing the first database. Traversing of the singly linked list is terminated when the next node address is determined to be invalid or null.