基于全球网络定位的全局负载均衡方法

1、一种基于全球网络定位的全局负载均衡方法，其特征在于：DNS服务 器根据DNS查询报文中Web客户的GNP坐标和所要解析的域名对应的具有不 同IP地址的各个镜像Web服务器的GNP坐标，计算该Web客户与各个服务器 的GNP距离，再根据该距离进行全局负载均衡处理，在距离该Web客户最近 的多个服务器的IP地址中选择一个IP地址作为DNS查询结果返回给该Web 客户。
2、根据权利要求1所述的全局负载均衡方法，其特征在于：该方法操作之 前进一步包括下列步骤：
A、修改现有的DNS查询报文格式，即在该DNS查询报文中加入准备发 出http请求的Web客户的GNP坐标；DNS服务器返回的查询结果响应报文， 不需做任何改动；
B、修改现有的DNS服务器软件，使之能够识别含有GNP坐标的DNS查 询报文和在数据库中找到每个域名所对应的各个服务器的IP地址及其GNP坐 标，完成基于GNP的全局负载均衡算法的初始化。
3、根据权利要求2所述的全局负载均衡方法，其特征在于：所述步骤A 进一步包括下列操作步骤：
A1、修改查询报文首部的定义：在标志字段增加opcode字段的值，即在 现有opcode字段定义0为标准查询、1为反向查询和2为服务器状态请求的基 础上，增加数值3为支持GNP坐标的DNS查询；
A2、在DNS查询报文中加入GNP坐标。
4、根据权利要求3所述的全局负载均衡方法，其特征在于：所述步骤A2 在DNS查询报文中加入GNP坐标的操作步骤为下述两种方法之一：
修改查询报文的问题部分：在支持GNP坐标的DNS查询报文中，除了原 有的域名的IP地址查询字段外，增加一个问题字段，并在该问题字段中写入本 主机的GNP坐标，其查询类型为Coordinate，类型值为25，表示Web客户的 GNP坐标信息，查询类为5，指GNP坐标；再在查询名内存储本主机的GNP 坐标，即按GNP坐标的格式CH S给出本主机的坐标，该式表示在N维坐标空间 S下的主机H的GNP坐标，其中N为当前GNP坐标的维数；同时将报文首部 的问题数修改为2，即将原有的问题数增加1；或
修改和定义额外信息字段：定义支持GNP坐标的DNS查询报文的额外信息 字段格式采用资源记录RR格式；其中域名为0，表示没有常规意义上的域名； 定义类型为Coordinate，类型值为25，表示Web客户的GNP坐标信息；类的值为 5，指的是GNP坐标；资源数据长度说明资源数据的数量，当该资源是GNP坐标 时，即类型字段为25时，则按GNP坐标的格式CH S给出本机的坐标，该式表示 在N维坐标空间S下的主机H的GNP坐标，其中N为当前GNP坐标的维数。
5、根据权利要求2所述的全局负载均衡方法，其特征在于：所述步骤B 进一步包括下列操作步骤：
B1、DNS服务器识别支持GNP坐标的DNS查询报文：DNS服务器读出 DNS请求报文首部标志字段中的opcode字段为3，即识别该报文为支持GNP 坐标的DNS查询报文，再在第二个问题域中读出发出查询请求的Web客户的 GNP坐标；或根据额外资源记录数，在其后的额外资源域中读出发出查询请求 的Web客户的GNP坐标；
B2、修改DNS服务器的数据库：在原有DNS数据库的基础上，将每个域 名所对应的各个镜像Web服务器的GNP坐标与其IP地址一起存储记录；DNS 服务器在更新数据时，同时更新各个IP地址对应的GNP坐标，以便在DNS服 务器进行域名解析时，得到对应于同一个域名的各个服务器的IP地址和GNP 坐标。
6、根据权利要求1所述的全局负载均衡方法，其特征在于：该方法包括下 列操作步骤：
(1)当Web客户要发出http请求时，如果此前在本主机内没有保存本主 机在空间S的GNP坐标CH S，则Web客户需要根据各路标Landmark和本主机 的距离，按照GNP算法计算本主机在空间S的GNP坐标，并保存该GNP坐标；
(2)Web客户按照修改后的DNS查询报文格式发出含有本主机GNP坐标 信息的DNS查询请求；
(3)当DNS服务器收到Web客户发出的带有GNP坐标信息的域名解析 请求后，如果该DNS服务器不支持基于GNP的全局负载均衡方法，则按普通 DNS服务器的负载均衡方法，轮循选择一个服务器的IP地址返回；如果该DNS 服务器支持基于GNP的全局负载均衡方法，则根据GNP负载均衡算法选择一 个响应该Web客户的服务器的IP地址作为该Web客户的域名解析请求结果返 回；
(4)DNS服务器按照普通DNS响应报文的格式将查询结果返回给Web 客户，以便Web客户用收到的IP地址连接Web服务器，并下载Web页面。
7、根据权利要求6所述的全局负载均衡方法，其特征在于：所述步骤(3) 中，当DNS服务器支持基于GNP的全局负载均衡方法时，进一步包括下列操 作步骤：
(31)从DNS查询报文中取出该Web客户的GNP坐标，找到所要解析的 域名对应的IP地址列表后，按照GNP算法计算该Web客户到各个IP地址所对 应的服务器的GNP距离；
(32)在与发出DNS请求的Web客户GNP距离最近的多个服务器的IP 地址中选择一个IP地址；
(33)将所选IP地址作为DNS查询报文的响应结果写入DNS响应报文， 并返回给Web客户。
8、根据权利要求7所述的全局负载均衡方法，其特征在于：所述步骤(31) 中按照GNP算法计算Web客户到各个IP地址所对应的服务器的GNP距离的 算法公式是： $d_{H1,H2}=\sqrt{{\Sigma }_{i=1}^N{(x_i-y_i)}^2},$
式中假设N维坐标空间S下的主机H1与主机H2的GNP坐标分别为：CH1 S ＝(x1，  x2，...，xN)，  CH2 S＝(y1，y2，...，yN)。
9、根据权利要求7所述的全局负载均衡方法，其特征在于：所述步骤(32) 中，在与发出DNS请求的Web客户GNP距离最近的多个服务器的IP地址中 选择一个IP地址的方法有下述两种：
选择与该Web客户的GNP距离最近的IP地址对应的服务器作为响应该 Web客户的服务器；或
先选择与该Web客户的GNP距离最近的多个IP地址，即按照距离排序最 小的若干个IP地址，再在该若干个IP地址中随机选择一个，将其对应的服务 器作为响应该Web客户的服务器。
10、根据权利要求8所述的全局负载均衡方法，其特征在于：所述选择与 Web客户的GNP距离最近的IP地址对应的镜像服务器Sj作为响应该客户Web 请求的服务器的计算公式为：j∈{1..n}，且dH，Sj＝mini∈{1..n}{dH，Si}；即j取1，2，...， n中的一个，dH，Sj是dH，S1，dH，S2，...，dH，Sn中最小的一个；其中H为Web客户， n为与所解析的域名对应的具有不同IP地址的Web服务器的总数；
所述先选择与该Web客户的GNP距离最近的多个IP地址，再在该多个IP 地址中随机选择一个作为响应该Web客户的服务器的步骤中选择与Web客户 距离最近的多个Web服务器的数量m的计算公式为：式中为向 上取整，即为取大于等于n/2的最小整数；其中n为与所解析的域名对应 的具有不同IP地址的Web服务器的总数。

技术领域\n本发明涉及一种基于全球网络定位GNP(Global Network Positioning)的全 局负载均衡方法，确切地说，涉及一种主要解决在一个域名对应着多个具有不 同IP地址的镜像Web服务器时，如何更好地选择由哪个服务器响应Web客户 请求的问题；属于负载均衡技术领域。\n背景技术\n参见图1，Web客户1(通常称为浏览器)与Web服务器2使用一个或多 个传输控制协议(TCP，Transmission Control Protocol)连接进行通信。Web浏 览时，客户端与服务器在TCP连接上采用超文本传输协议(HTTP，Hypertext Transfer Protocol)进行通信。Web客户发出http请求，Web服务器对客户端请 求进行响应，向Web客户提供Web的内容和某种形式的数据。\n参见图2，当客户需要和远端Web系统通信，如一个用户连接Web站点，在 实际和远端Web系统开始通信前，必须将Web域名转换为IP地址，这个转换由域 名服务器(DNS，Domain Name Server)来完成，因此在客户机配置中至少需 要指定一个域名服务器DNS。当Web客户向它的一个DNS服务器发出查询请求， 即一个客户端1(如浏览器)程序，产生一个统一资源定位(URL，Uniform Resource Locator，)解析请求，例如http://www.bupt.edu.cn，以DNS查询报文的 形式交给本地DNS服务器2时，该本地DNS服务器2会尽可能把该域名(即 www.bupt.edu.cn)解析成IP地址。本地DNS服务器2接受了客户机的查询时，客 户机1通常处于等待状态；该本地域名服务器2就在其域名数据库中查找所查询 域名对应的IP地址，或从比它层次级别更高的DNS服务器3得到与接收到的查询 相匹配的域名对应的IP地址。也就是说，如果客户机1所查询的域名解析结果就 在该本地域名服务器2的缓存中，可以直接得到结果；如果答案不在该本地域名 服务器2的缓存，该域名服务器2必须到其它域名服务器3查找，还可以将查询发 送到根服务器，并根据根服务器值引导所查询域的授权服务器。一旦该本地服 务器2从授权服务器得到答案，它就将答案保存在它的缓存中，并将答案提供给 客户。DNS服务器将查询结果以DNS响应报文的形式返回给客户，以便客户使 用收到的IP地址连接Web服务器并下载Web页面。DNS定义了一个用于查询和响 应的报文格式。下表是这个报文的总体格式。该报文由12字节长的首部和4个长 度可变的字段组成。\n\n在DNS的报文首部里，标识字段由客户程序设置并由服务器返回结果。客 户程序通过它来确定响应与查询是否匹配。16bit的标志字段被划分为若干子字 段，如下表所示。\n  QR   opcode   AA   TC   RD   RA   (zero)   rcode\n1  4     1   1   1   1    3      4\n其中QR是1bit字段：0表示查询报文，1表示响应报文。opcode是一个4bit 字段：通常值为0，表示标准查询，其它值为1和2，为1时，表示反向查询(即 通过IP地址查找对应的域名)；为2时，表示服务器状态请求。AA是1bit标志， 表示授权回答(authoritative answer)，说明该域名服务器是授权于该域的。TC 是1bit字段，表示可截断的(truncated)。使用用户数据报协议(UDP，User Datagram Protocol)时，它表示当应答的总长度超过512字节时，只返回前512 个字节。RD是1bit字段，表示期望递归(recursion desired)。该比特可以设置在 一个查询中，并在响应中返回。该标志告诉域名服务器必须处理这个查询，称 为递归查询。如果该比特位为0，且被请求的域名服务器没有授权回答，它就返 回一个能解答该查询的其他域名服务器列表，称为迭代查询。RA是1bit字段， 表示可用递归。如果域名服务器支持递归查询，则在响应中将该比特设置为1。 除了某些根服务器，大多数域名服务器都提供递归查询。随后的3bit字段必须为 0。rcode是一个4bit的返回码字段。通常的值为0，表示没有差错；数值为3，表 示名字差错。名字差错只有从一个授权域名服务器上返回，它表示在查询中指 定的域名不存在。随后的4个16bit字段说明最后4个变长字段中包含的条目数。 对于查询报文，问题数通常是1，而其他3项则均为0。对于应答报文，回答数至 少是1，剩下的两项可以是0或非0。\n在DNS查询报文中的查询问题部分中的每个问题的格式如下表所示，通常 只有一个问题。\n\n其中查询名是要查找的IP地址或域名，它是一个或多个标识符的序列。每 个标识符以首字节的计数值来说明随后标识符的字节长度，每个查询名都以最 后字节为0结束，长度为0的标识符是根标识符。这里的计数字节的值是0～63 的数，即标识符的最大长度仅为63。因为计数字节的最高两个比特为1，即值 192～255被用于压缩格式。该字段无需以整32bit边界结束，即无需填充字节。\n参见图3，该图说明了如何存储域名www.bupt.edu.cn。它是四个标识符的序 列，每个标识符都以首字节的计数值(分别为3、4、3、2)来说明随后标识符 的字节长度，并以最后字节为0结束该查询名。\n每个查询问题有一个查询类型，每个响应(也称资源记录)也有一个类型， 总共大约有20个不同的类型值。下表显示了其中的一些查询类型值，表中显示 的类型值中只有两个用于查询类型：A和PTR。最常用的查询类型是A，表示期 望获得查询名的IP地址。另一个查询类型是PTR，表示请求获得一个IP地址对 应的域名。\n  名字   数值   描述   A   NS   CNAME   PTR   HINPO   MX   1   2   5   12   13   15   IP地址   名字服务器   规范名称   指针记录   主机信息   邮件交换记录   AXFR   或ANY   252   255   对区域转换的请求   对所有记录的请求\n查询类通常是1，指互联网地址。某些站点也支持其他非IP地址。\n在DNS响应报文中的资源记录部分中最后的三个字段：回答字段、授权字 段和额外信息字段，均采用如下表所示的称为资源记录(RR，Resource Record) 的格式。\n\n其中域名是记录中资源数据对应的名字。它的格式和图3所示的查询名字段 格式相同。类型说明资源记录的类型码。它的值和前面介绍的查询类型值是一 样的。类通常为1，指互联网数据。生存时间字段是客户程序保留该资源记录的 秒数。资源记录通常的生存时间值为2天。资源数据长度说明资源数据的数量。 该数据的格式依赖于类型字段的值。对于类型1(A记录)资源数据是4字节的IP 地址。\n在互联网应用中有很多场合需要估计网络距离，如还回时延(round-trip delay)；又如：对应一个Web站点(如Yahoo)有多个映像服务器(S1...Sn) 可以同时为Web客户提供服务，当一台主机H要连接到该Web站点时，希望 选择连接距离该主机最近的一个映像服务器，以保证web页面传输速度，提高 http请求的响应速度，进而提高Web服务质量。这时，就需要估计网络中该主 机H与各个映像服务器之间的距离。由此可见，估计网络中端到端主机间的距 离是很有必要的。\n目前，GNP(Global Network Positioning)是估计端到端网络距离比较有效 的方法，其算法的思路是：根据网络结点之间的距离信息，将各个网络结点映 射到一个N维坐标系，使各个网络结点在这个N维坐标系中的距离(即GNP 距离)尽可能接近于各个网络结点之间的实际距离(比如可以采用结点间的还 回时延作为实际距离)。这样，就可以通过计算网络结点之间的GNP距离来估 计网络结点之间的实际距离。图4就是把网络中的四个结点放入一个三维坐标 系示意图。\n下面简要说明GNP算法估计网络中各个结点间距离的计算步骤：\n首先在网络中找出一些结点作为路标(Landmark)，把这些路标放入一个N 维坐标系，使得这些路标的坐标间的距离与它们之间的实际距离(如还回时延) 的差最小，再计算出这些路标在N维坐标系中的坐标。图5就是在GNP算法 中，将网络中三个结点L1、L2、L3作为路标放入二维坐标系的操作示意图。\n然后，将需要测量距离的普通主机放入N维坐标系。根据它们与这些路标 之间的实际距离，计算它们在该坐标系中的坐标。图6是GNP算法中参照图5中 的路标L1、L2、L3将另一台普通主机放入二维坐标系的操作示意图。\n这样，GNP算法就可以把网络上的任一结点放入N维坐标系。之后，就可 以利用两台主机的GNP坐标直接计算它们之间的GNP距离，并作为它们之间网 络距离的估计值。实验证明，直接通过GNP坐标计算得到的两台主机间的GNP 距离确实能够比较准确地反映网络中两台主机间的实际距离。如果N维坐标空 间S下的两台主机H1与主机H2的GNP坐标分别为：CH1 S＝(x1，x2，...，xN)， CH2 S＝(y1，y2，...，yN)，则它们之间的GNP距离的计算公式为： $d_{H1,H2}=\sqrt{{{\Sigma }_{i=1}^N(x_i-y_i)}^2}.$\n现在，由于Internet业务量的快速增长，Web服务器的访问者数量呈快速增 加的发展态势，例如Yahoo每天会收到数百万次的访问请求，Web服务器必须具 备提供大量并发访问服务的能力。对于提供大负载Web服务的服务器来讲， CPU、I/O等处理能力会很快成为制约访问量的瓶颈，简单地提高单台服务器的 硬件性能并不能真正解决问题，因为单台服务器的性能总是有限的。尤其是网 络请求具有突发性，可能出现某一段时间内网络访问量急剧上升的现象，从而 造成网络瓶颈。因此，必须采用多台服务器提供网络服务，并将网络请求尽量 均衡地分配给这些服务器分担，才能提供处理大量并发请求的能力。\n在负载均衡的条件下，多台服务器的地位是平等的，都可以独立为Web客 户提供服务而无须其它服务器的辅助，因此这些服务器通常称为镜像服务器。 然后通过某种负载均衡技术，将外部发送来的多个请求均匀分配到各台服务器 上，而接收到请求的服务器都独立响应客户机的请求。由于建立内容完全一致 的Web服务器并不复杂，因此负载均衡技术就成为建立一个高负载Web站点的 关键技术之一。\n从其应用的地理结构上，负载均衡有两种，分为本地负载均衡(Local Load Balance)：对本地的服务器群作负载均衡，以及全局负载均衡(Global Load Balance)：对分别放置在不同的地理位置、有不同网络结构的服务器群进行负 载均衡。其中全局负载均衡具有能实现地理位置无关性，远距离为用户提供完 全的透明服务等优点；它不仅能够避免服务器、数据中心等的单点失效，也能 避免由于网络故障引起的单点失效，还可以解决网络拥塞问题，提高服务器响 应速度，达到更好的访问质量。全局负载均衡技术主要用于在多个区域拥有自 己服务器的站点(比如Yahoo)，也可用于子公司地址分散、站点分布广、希望 通过企业内联网Intranet来达到资源统一合理分配目的的大公司。\n目前，实现全局负载均衡最常用的技术是DNS服务器(Round Robin DNS) 轮循负载均衡技术。因为基于Web服务器软件的负载均衡需要改动其软件，经 常得不偿失；而DNS轮循负载均衡技术是在Web服务器软件之外，即在DNS 系统中实现负载均衡，这样就无需修改现有Web服务器软件。DNS负载均衡技 术是通过DNS服务器中的随机名字解析来实现的，也就是在DNS服务器中为 同一个域名配置多个IP地址，在应答DNS查询时，DNS服务器对每个查询将 以DNS文件中域名记录的IP地址按顺序返回不同的解析结果，将客户端的访 问引导到不同的机器上去，使得不同的客户端访问不同的服务器，从而达到负 载均衡的目的。这种DNS负载均衡的算法是轮循均衡：将每一次来自网络的请 求轮流分配给n个服务器。这种DNS负载均衡算法的优点是简单易行，Web 服务器可以位于互联网的任意位置上。该技术已经成功应用在包括Yahoo在内 的许多知名的全球Web站点上。\n但是，这种基于简单轮循机制的DNS负载均衡技术功能比较简单，存在不 少缺点，特别突出的问题是服务器分配可能不合理。因为http服务传输的web 页面数据量较小，如果服务器离Web客户越近，越能保证web页面传输的速度， 即保证响应http请求的速度和保证Web服务的质量。然而，DNS负载均衡采 用的是简单轮循的方式，不能保证 例如，有些互联网服务提供商(ISP，Internet Service Provider)可能在美洲、欧洲、亚洲都有自己的应用服务器。采用DNS 轮循负载均衡方式，可能会让亚洲用户访问美洲的服务器，而美洲用户访问亚 洲的服务器。这样不仅降低了系统对用户的反应速度，降低系统的服务质量； 还引起不必要的跨洋网络流量，增加了ISP的通信成本。\n发明内容\n本发明的目的是提供一种基于全球网络定位GNP的全局负载均衡方法，该 方法是对现在最常用的基于DNS服务器轮循的全局负载均衡方法的改进和优 化，能够保证所选择的镜像服务器与发出请求的Web客户的距离最近或相对较 近，提高Web请求的响应速度和web页面的传输速度，进而减少不必要的网络 流量，提高Web系统的服务质量。\n本发明的目的是这样实现的：一种基于全球网络定位的全局负载均衡方法， 其特征在于：DNS服务器根据DNS查询报文中Web客户的GNP坐标和所要解 析的域名对应的具有不同IP地址的各个镜像Web服务器的GNP坐标，计算该 Web客户与各个服务器的GNP距离，再根据该距离进行全局负载均衡处理，在 距离该Web客户最近的多个服务器的IP地址中选择一个IP地址作为DNS查询 结果返回给该Web客户。\n该方法操作之前进一步包括下列步骤：\nA、修改现有的DNS查询报文格式，即在该DNS查询报文中加入准备发 出http请求的Web客户的GNP坐标；DNS服务器返回的查询结果响应报文， 不需做任何改动；\nB、修改现有的DNS服务器软件，使之能够识别含有GNP坐标的DNS查 询报文和在数据库中找到每个域名所对应的各个服务器的IP地址及其GNP坐 标，完成基于GNP的全局负载均衡算法的初始化。\n所述步骤A进一步包括下列操作步骤：\nA1、修改查询报文首部的定义：在标志字段增加opcode字段的值，即在 现有opcode字段定义0为标准查询、1为反向查询和2为服务器状态请求的基 础上，增加数值3为支持GNP坐标的DNS查询；\nA2、在DNS查询报文中加入GNP坐标。\n所述步骤A2在DNS查询报文中加入GNP坐标的操作步骤为下述两种方 法之一：\n修改查询报文的问题部分：在支持GNP坐标的DNS查询报文中，除了原 有的域名的IP地址查询字段外，增加一个问题字段，并在该问题字段中写入本 主机的GNP坐标，其查询类型为Coordinate，类型值为25，表示Web客户的 GNP坐标信息，查询类为5，指GNP坐标；再在查询名内存储本主机的GNP 坐标，即按GNP坐标的格式CH S给出本主机的坐标，该式表示在N维坐标空间 S下的主机H的GNP坐标，其中N为当前GNP坐标的维数；同时将报文首部 的问题数修改为2，即将原有的问题数增加1；或\n修改和定义额外信息字段：定义支持GNP坐标的DNS查询报文的额外信息 字段格式采用资源记录RR(Resource Record)格式；其中域名为0，表示没有 常规意义上的域名；定义类型为Coordinate，类型值为25，表示Web客户的GNP 坐标信息；类的值为5，指的是GNP坐标；资源数据长度说明资源数据的数量， 当该资源是GNP坐标时，即类型字段为25时，则按GNP坐标的格式CH S给出本 机的坐标，该式表示在N维坐标空间S下的主机H的GNP坐标，其中N为当前GNP 坐标的维数。\n所述步骤B进一步包括下列操作步骤：\nB1、DNS服务器识别支持GNP坐标的DNS查询报文：DNS服务器读出 DNS请求报文首部标志字段中的opcode字段为3，即识别该报文为支持GNP 坐标的DNS查询报文，再在第二个问题域中读出发出查询请求的Web客户的 GNP坐标；或根据额外资源记录数，在其后的额外资源域中读出发出查询请求 的Web客户的GNP坐标；\nB2、修改DNS服务器的数据库：在原有DNS数据库的基础上，将每个域 名所对应的各个镜像Web服务器的GNP坐标与其IP地址一起存储记录；DNS 服务器在更新数据时，同时更新各个IP地址对应的GNP坐标，以便在DNS服 务器进行域名解析时，得到对应于同一个域名的各个服务器的IP地址和GNP 坐标。\n该方法包括下列操作步骤：\n(1)当Web客户要发出http请求时，如果此前在本主机内没有保存本主 机在空间S的GNP坐标CH S，则Web客户需要根据各路标Landmark和本主机 的距离，按照GNP算法计算本主机在空间S的GNP坐标，并保存该GNP坐标；\n(2)Web客户按照修改后的DNS查询报文格式发出含有本主机GNP坐标 信息的DNS查询请求；\n(3)当DNS服务器收到Web客户发出的带有GNP坐标信息的域名解析 请求后，如果该DNS服务器不支持基于GNP的全局负载均衡方法，则按普通 DNS服务器的负载均衡方法，轮循选择一个服务器的IP地址返回；如果该DNS 服务器支持基于GNP的全局负载均衡方法，则根据GNP负载均衡算法选择一 个响应该Web客户的服务器的IP地址作为该Web客户的域名解析请求结果返 回；\n(4)DNS服务器按照普通DNS响应报文的格式将查询结果返回给Web 客户，以便Web客户用收到的IP地址连接Web服务器，并下载Web页面。\n所述步骤(3)中，当DNS服务器支持基于GNP的全局负载均衡方法时， 进一步包括下列操作步骤：\n(31)从DNS查询报文中取出该Web客户的GNP坐标，找到所要解析的 域名对应的IP地址列表后，按照GNP算法计算该Web客户到各个IP地址所对 应的服务器的GNP距离；\n(32)在与发出DNS请求的Web客户GNP距离最近的多个服务器的IP 地址中选择一个IP地址；\n(33)将所选IP地址作为DNS查询报文的响应结果写入DNS响应报文， 并返回给Web客户。\n所述步骤(31)中按照GNP算法计算Web客户到各个IP地址所对应的服 务器的GNP距离的算法公式是： $d_{H1,H2}=\sqrt{{{\Sigma }_{i=1}^N(x_i-y_i)}^2},$\n式中假设N维坐标空间S下的主机H1与主机H2的GNP坐标分别为：CH1 S ＝(x1，x2，...，xN)，CH2 S＝(y1，y2，...，yN)。\n所述步骤(32)中，在与发出DNS请求的Web客户GNP距离最近的多个 服务器的IP地址中选择一个IP地址的方法有下述两种：\n选择与该Web客户的GNP距离最近的IP地址对应的服务器作为响应该 Web客户的服务器；或\n先选择与该Web客户的GNP距离最近的多个IP地址，即按照距离排序最 小的若干个IP地址，再在该若干个IP地址中随机选择一个，将其对应的服务 器作为响应该Web客户的服务器。\n所述选择与Web客户的GNP距离最近的IP地址对应的镜像服务器Sj作为 响应该客户Web请求的服务器的计算公式为：j∈{1..n}，且 dH，Sj＝mini∈{1..n}{dH，Si}；即j取1，2，...，n中的一个，dH，Sj是dH，s1，dH，S2，...， dH，Sn中最小的一个；其中H为Web客户，n为与所解析域名对应的具有不同IP 地址的Web服务器的总数；\n所述先选择与该Web客户的GNP距离最近的多个IP地址，再在该多个IP 地址中随机选择一个作为响应该Web客户的服务器的步骤中选择与Web客户 距离最近的多个Web服务器的数量m的计算公式为：式中为向 上取整，即为取大于等于n/2的最小整数；其中n为与所解析的域名对应 的具有不同IP地址的Web服务器的总数。\n本发明基于全球网络定位GNP的全局负载均衡方法不是简单地轮循指定 一个服务器，而是考虑Web服务器与Web客户的相对位置因素进行负载均衡， 能够保证所选择的IP地址对应的服务器与发出请求的Web客户的距离最近或 相对较近，进而减少不必要的网络流量，保证http请求的响应速度，也保证了 Web服务的传输速度和质量，提高Web系统的服务质量。\n本发明这种考虑距离因素的基于GNP的全局负载均衡方法还可以与其它 负载均衡算法相结合，应用于其它几种全局负载均衡技术。因此，本发明具有 很好的应用前景。\n附图说明\n图1是Web服务器向Web客户提供服务的连接示意图。\n图2是DNS服务器向Web客户提供域名解析服务的过程示意图。\n图3是在本发明DNS查询报文中举例域名www.bupt.edu.cn的存储记录方 式示意图。\n图4是GNP算法中把网络中的四个结点放入一个三维坐标系示意图。\n图5(A)、(B)分别是作为路标的三个结点L1、L2、L3在网络中的相对位 置图及将其放入二维坐标系的GNP算法操作示意图。\n图6(A)、(B)分别是另一台普通主机与图5所示的三个路标L1、L2、L3 在网络中的相对位置图及将该主机放入二维坐标系的GNP算法操作示意图。\n图7是本发明DNS服务器基于GNP的全局负载均衡方法的操作步骤示意 图。\n图8是图7中的DNS服务器收到Web客户的域名解析请求后进行基于GNP 的全局负载均衡算法操作的处理流程方框图。\n具体实施方式\n本发明是一种基于全球网络定位GNP的全局负载均衡方法，也是对现有 DNS轮循负载均衡方法的改进，即将原来的轮循均衡算法改进为基于GNP的 全局负载均衡算法。该方法是由DNS服务器根据DNS查询报文中的Web客户 的GNP坐标和所要解析的域名对应的具有不同IP地址的各个镜像服务器的 GNP坐标，计算该Web客户与各个服务器的GNP距离，再根据该距离进行全 局负载均衡处理，将距离该Web客户最近或相对较近的服务器的IP地址作为 DNS查询结果返回给该Web客户。由于基于GNP算法求出的GNP距离能很好 地反映两台主机在网络上的距离(如还回时延round-trip delay)，以GNP距离 为依据选择的Web服务器能够保证所选服务器与该Web客户网络距离最近或 相对较近。为此，本发明首先需要修改现有的DNS报文格式以及DNS服务器 软件，以便能够完成对基于GNP的全局负载均衡的支持。\n由于要使DNS服务器在解析域名后选择与Web客户GNP距离最近或相对 较近的Web服务器对应的IP地址，本发明首先要在原有DNS查询报文的基础 上作一定的修改，即本发明在DNS查询报文中加入准备发出http请求的Web 客户的GNP坐标和修改报文首部的定义，DNS服务器返回的查询结果响应报 文不需做任何改动。\n其中对查询报文首部定义的修改只是在标志字段增加opcode字段的值，即 在现有opcode字段定义0为标准查询、1为反向查询和2为服务器状态请求的 基础上，增加数值3为支持GNP坐标的DNS查询报文。标志字段中的其它字 段定义不变。下表是DNS报文首部中的标志字段的组成结构。\n  QR   opcode   AA   TC   RD   RA   (zero)   rcode\n1   4     1   1   1   1   3     4\n对于在DNS查询报文中加入GNP坐标可以有两种方案：\n一种是修改查询报文的问题部分：如果是普通DNS查询报文，通常只有一 个问题。如果是支持GNP坐标的DNS查询报文，除了原有的域名的IP地址查 询字段外，需要增加一个问题字段(如下表所示)，并在该问题字段中写入本主 机的GNP坐标；其查询类型为Coordinate，类型值为25，表示Web客户的GNP 坐标信息，查询类为5，指GNP坐标。再在查询名内存储本主机的GNP坐标， 即按GNP坐标的格式CH S给出本主机的坐标，该式表示在N维坐标空间S下的 主机H的GNP坐标；例如五维空间中的GNP坐标为：5-3.01374721.120157 93.054810-6.04485212.845207，其中第一个数N是正整数，表示维数；N可 以为5、或7、或9、...；后面N个4字节浮点数为各个维坐标的值。同时要将 报文首部的问题数修改为2，即将原有问题数增加1。\n\n另一种是修改和定义额外信息字段：通常的DNS查询报文的额外资源记录 数一般为0，表示没有额外信息字段，为了加入GNP坐标信息，本发明定义支 持GNP坐标的DNS查询报文的额外信息字段的格式如下表所示：采用资源记 录RR格式；其中域名为0，表示没有常规意义上的域名；定义类型为Coordinate， 其类型值为25，表示Web客户的GNP坐标信息；类的值为5，指的是GNP坐 标；资源数据长度说明资源数据的数量，如果该资源是GNP坐标，即类型字段 为25时，则按GNP坐标的格式CH S给出本机的坐标，该式表示在N维坐标空 间S下的主机H的GNP坐标。例如：五维空间中的坐标为：5-3.013747 21.120157  93.054810-6.044852  12.845207，其中第一个数N是正整数，表示 维数，N可以为5、或7、或9、...；后面N个4字节浮点数为各个维坐标的值。\n\n此外，还要修改现有的DNS服务器软件，使之能够支持基于GNP的全局 负载均衡。具体做法是通过读出DNS请求报文首部标志字段中的opcode字段 为3，识别为支持GNP坐标的DNS查询报文，再在第二个问题域中读出发出 查询请求的Web客户的GNP坐标，或根据额外资源记录数，在其后的额外资 源域中读出发出查询请求的Web客户的GNP坐标；还要修改DNS服务器的数 据库，以完成基于GNP的全局负载均衡算法的初始化。即在原有DNS数据库 的基础上，将每个域名所对应的各镜像Web服务器的GNP坐标与其IP地址一 起记录；DNS服务器在更新数据时，要同时更新各个IP地址对应的GNP坐标。 这样，当DNS服务器进行域名解析时，能够得到对应于同一个域名的各个服务 器的IP地址和GNP坐标。\n本发明基于全球网络定位GNP的全局负载均衡方法的过程概述是：在某一 Web客户要发送http请求之前，进行域名解析时，DNS服务器先用GNP算法 求出该Web客户到所要解析域名的各个IP地址对应的Web服务器的GNP距离， 再根据该GNP距离及基于GNP的全局负载均衡算法选择一个镜像Web服务器， 将其IP地址返回给Web客户。图7简明地表述了该处理过程。\n参见图7，下面详细描述该处理过程。\n(1)当Web客户要发出http请求时，如果以前在本主机内没有保留本主 机在空间S的GNP坐标CH S，则需要按GNP的方法根据各个路标Landmark和 本主机的距离(比如用还回时延表示该距离)，计算本主机的GNP坐标，并保 存该GNP坐标。\n(2)按照修改后的DNS查询报文格式发出DNS查询请求，即在DNS查 询报文中的标志字段设置opcode字段值为3和加入本主机的GNP坐标信息。\n(3)当DNS服务器收到该Web客户的域名解析请求后，如果该DNS服 务器不支持基于GNP的全局负载均衡方法，则按普通DNS服务器的负载均衡 方法，轮循选择一个服务器的IP地址返回；如果该DNS服务器支持基于GNP 的全局负载均衡方法，则从DNS查询报文中取出Web客户的GNP坐标。因为 DNS服务器中保留了与所要解析的域名对应的多个IP地址IPS1、IPS2、...、IPSn (分别对应于镜像服务器S1、S2、...、Sn)，以及其对应的GNP坐标CS1 S、CS2 S、...、 CSn S，根据这些服务器的GNP坐标和Web客户的GNP坐标，DNS服务器计算 出该Web客户与各个Web服务器之间的GNP距离dH，S1、dH，S2、...、dH，Sn，其 中计算两个结点之间的GNP距离的公式为： $d_{H1,H2}=\sqrt{{{\Sigma }_{i=1}^N(x_i-y_i)}^2},$ 式中该两 个结点是N维坐标空间S下的两个主机H1和H2，其GNP坐标分别为：CH1 S ＝(x1，x2，...，xN)和CH2 S＝(y1，y2，...，yN)。\n(4)DNS服务器选择某一个镜像服务器的IP地址作为Web客户域名解析 查询的结果。可以有两种选择方式，一种是选择与该Web客户GNP距离最近 的镜像服务器Sj作为响应该客户Web请求的服务器：j ∈{1..n}，且 dH，Sj＝mini∈{1..n}{dH，Si}；即j取1，2，...，n中的一个，dH，Sj是dH，S1，dH，S2，...， dH，Sn中最小的一个；其中H为Web客户，n为与所解析域名对应的具有不同IP 地址的Web服务器的总数。但是，直接采用上述方式，有可能出现http请求分 配不当，即有大量同一区域的Web客户请求都按距离最近的原则分配到同一个 Web服务器，造成某个Web服务器负载较大，使得各个Web服务器负载差距 较大。此时建议选用另一种选择方式，即采用GNP距离最近与随机选择相结合 的办法：先选择与Web客户距离最近的多个Web服务器，例如m个；按照 (为向上取整，即为取大于等于n/2的最小整数，其中n 为与所解析的域名对应的具有不同IP地址的Web服务器的总数)的计算公式， 再在这m个Web服务器中随机选择一台作为响应该Web客户的服务器，将其 IP地址作为DNS服务器的域名解析结果返回给Web客户。\n(5)DNS服务器按照普通DNS响应报文的格式将查询结果返回给Web 客户，以便Web客户用收到的IP地址连接Web服务器，并下载Web页面。\n参见图8，该图是图7中的DNS服务器收到Web客户发出的带有GNP坐 标的域名解析请求后进行基于GNP的全局负载均衡算法操作的处理流程方框 图。也就是上述步骤(3)～(5)的操作流程图，这里不再赘述。\n因为Web服务的响应速度是衡量其服务质量的一个重要指标，要求响应 http请求的Web服务器与该Web客户的距离最近或相对较近，进而保证http 请求的响应速度最快，是保证Web服务质量的关键之一。所以本发明在全局负 载均衡算法中，考虑到响应http请求的Web服务器与该Web客户之间的距离 确实很有必要，而且，本发明基于GNP的全局负载均衡算法中对距离因素的考 虑可以与其它负载均衡算法相结合，进而应用于其它几种全局负载均衡技术。 例如，可以类似地将GNP坐标加入http请求消息的头部，当利用http重定向 技术进行负载均衡时，可以从http消息头部中取出GNP坐标，并结合其它负载 均衡的算法(如考虑负载等其它因素的负载均衡算法)选择一个离Web客户相 对较近的Web服务器响应http请求。