Subject: Dynamic Cache Synchronization Protocol, was Re: GPL, number portability and wireless subscribers

From: "Greg Zhang" <[email-masked]>
Date: Wed, 10 Mar 1999 14:47:16 -0800

Hello, everyone!

Matt Squire wrote:
>It seems like a heirarchy could be built now (using either scsp or bgp
>approach) if each peer group/level was considered a domain, and we just
>defined filters so that at B, information coming from A didn't get sent
>down to C.   So I think one could deploy a heirarchy using static
>port-based filters, which requires some administrative work.  But I think
>Greg was after something more dynamic, where the attribute itself defined
>which ports it would go out on based on the peer/server group on each port.

Let me take the liberty to outline my ideas in this email.

What I was trying to suggest is a different way of defining domain and doing
cache synchronization in and among these domains. Rather than the
traditional AS approach as in BGP and using two different protocols in
intra domain and inter domain, we could define a multi level domain
or peer group and build a hierarchy upon them. The domains or peer
groups are identified by a 32 bit domain or peer group ids. The lowest level
nodes in the hierarchy are configured with a list peer group ids that it
belongs to. i.e.

1st level peer group ID
2nd level peer group ID
3rd level peer group ID
...

On this list, the levels are counted from bottom up. Each node will use
a neighbour discovery hello message sent out using flooding on all its
ports to discovery its neighbours. It is going to carry a small TTL value
that is greater than one, perhaps 5. This is to get pass the routers that
do not speak the protocol in between protocol speaking nodes.

The hello message will include a nodal hierarachy list with contains:

1st level peer group ID
1st level peer group leader
2nd level peer group ID
2nd level peer group leader
3rd level peer group ID
3rd level peer group leader
...

When a peer group leader is not known, its field is filled with a blank
value. On receipt of such hello message, a node is suppose to send
a hello message back using unicast. If a node does not hear back from
any neighbour after sending out its neighbour discovery hello a couple
of times, it will increase the TTL value of the message to try to reach
the neighbours in a wider area. A neighbour list can also be configured
into a node to let it comes in contact with none topologically adjacent
nodes.

Nodes belong to the same peer group on the 1st level will elect a peer
group leader (PGL). Whoever has the highest PGL priority value and
a highest IP address will become the leader. The use of priority value will
ease the job of configuration of peer group list to nodes. You only need
to configure a few node with a more complete peer group list on each
level for the whole hierarchy to build properly. The boundary nodes will
exchange hello messages. Through the hello messages, they will
discovery whether they belong to a same peer group on the 2nd level.
If so, they will each notify its peer group leader. The PGL in turn will
start to exchange hello messages to establish the group and elect its
leader. This process continues until the whole hierarchy is established.

The hello message exchange and the peer group election process is
an on going process. The formation of the peer groups and the hierarchy
will respond to network topology change such as partition or merge.

The nodal hierarchy list sent by peer group leaders on each level
will include a more complete information of the hierarchy. It gets
propagated downward at each level until all node in the hierarchy gets
a complete list of all its parents. Note that only the lowest level nodes
physical node in the network. The nodes on the upper levels are logical
nodes resides in a physical box. In theory, there is no limit on the
number of levels that a hierarchy can have.

With formation of peer groups, members can exchange packets to
synchronize their database or cache. This is done in a very SCSP
fashion. The type of information to synchronize is outside the scope
of the cache synchronization protocol. They are identified by a
protocol ids as in SCSP. The same synchronization protocol can be
used to do cache synchronization for mutiple protocols at the same
time. The difference with SCSP is that the cache synchronization
is among a hierarchy of peer groups rather than between two servers.
The protocol used among the members could be multicast, a flooding
scheme, or a broadcast within a domain. It is up to the peer group
leader to decide which mechanism to use.

Cache entries gets propagated up through the hierarchy by the peer
group leaders on each level. At PGL, the entries can get
aggregated, filtered, or just passed up with minor or no change
depend on the policies installed at PGL and some propagation
control field carried in the cache entry.

The cache entries are only propagated up through the hierarchy.
They are never propagated downward. When a look up fails in a
peer group, the request gets forwarded to its peer group leader.
The PGL will perform the look up on the next level up. The process
continues until a match is found or it fails after reaches the top level
of the hierarchy.

Each cache entry will have a originator field. At the lowest level, the
originator is a physical node identified by its IP address. At upper
levels is the lower level peer group identified by the peer group id.
It is originator's responsibility to update the entry content to keep it
valid. A peer group hello mechanism is used to monitor the
connectivity status among the members of a peer group. As long as the
connection to the originator is alive, its entries is considered valid.
This way, cache entries does not need to be refreshed periodically.
This cut down the update traffic considerably. The cache entries are
sent over the wire only when a change occurred or a new entry get
created.

To have scoping control on cache entry, the originator will
put a list of peer group ids in the cache entry. The list can
contain both vertical and horizontal peer groups in the
hierarchy. The entry only get propagated to the peer
groups in the list. A simpler but less expressive approach is
to have a simple number of levels that the entry gets
propagated up to from its current level.

The peer group is a very arbitrary collection of nodes. It is
not limited to geographical/topological adjacency. On one
level a node can belong to more than one peer group. The
policy inside the node and the originator of the cache
entries determine what information gets propagated to
which peer group. In effect, there could be multiple
hierarchies build with the protocol each carrying out
its cache synchronization in the network.

There are some nice properties with this approach including
the dynamic formation of the peer group and hierarchy, the
scalability provided for propagating both aggregatable and
unaggregatable information, and a easy mechanism to
control scope of information propagation.

I am still working on the details of the protocol. I have two immediate
applications of the protocol. First is to propagate location update
information for mobile telephone subscriber in a IP based mobile
telephone network. The second is to do IP mobility for extending
IP all the way to handset in such a network.

Since there is fair amount of overlap between my location update
need and GLP, I am presenting the design to the group. A lot of
concept here is borrowed from PNNI and SCSP. All I did was adapt
them to the IP world, add some flexibility into the design to make the
association of servers dynamic, and to make the whole thing more
scalable. I would appreciate greatly if the ideas I presented here
can be evaluated and possibly debated on its merit. I would be
grateful to any comment and input.

Best regards,

- Greg

---------
This message came from the IETF IPTEL Working Group Mailing List.